In part 1 we defined our simple game building blocks and mechanics and observed that even simple levels could quickly generate complexity due to the exponential growth of possible game states. Since it’s important to guarantee that each level is at least correct and solvable according to our rules, we will try to define a way to verify all these states in our generator. We also tried to implement our game states relationship as a standard breadth-first tree and observed that:

This gives us some ideas on how we can revise this tree to improve our analysis.

Let’s review the rules of correctness for a level, according to the 3 medals that can be earned by the player:

We can define a preliminary level rating, from 0 to 3 stars, depending on how many of the above constraints we respect. Each constraint is checked only if the previous one has a positive result, otherwise, the level is discarded (not really but we will see this later).

Only levels rated 3 stars are suitable for the final game set.

Strategy refinement, “reversing” the tree

With all our previous considerations we can determine that a node doesn’t really care about his 4 children, most of its attention is focused on his parent nodes.

So let’s remove the child nodes but keep the parent node. We also add a Depth field that will be useful for solution length tracking.

// A node contains information about board configuration and relations to other nodes
class Node {
      int Value;       //encodes our pieces’ layout and board score
      NodeState State; //max-combo, ok or dead-end?
      Node[4] Child;   //the states originating from the next 4 moves
      int Index;       //generating move (none, up, right, down, left) 
                       //                 -1     0   1      2     3
      Node Parent;     //state before last move, used to traverse our solution
      Int Depth;       //how many moves it took to reach this node
}

As for each new node we need to make sure there is no pre-existing duplicate node, we can supplement our tree class with a separate Dictionary (which should benefit from retrieval-by-key speed close to O(1) as it’s implemented as a Generic type of Hash Table) that can retrieve our node base on the integer encoded value. In the end, this will contain only unique states.

//in our tree class
Dictionary <int, Node> uniqueNodes = new Dictionary();

We start from an existing root state, which is unique, let’s initialize our node and add it to the list:

//create a new node from a value generated by some external method
Root = new Node(value) {
      Value = value;
      State = DeadEnd     //we do not know if we can reach a solution yet
      Parent = null;      //root state has no parent
      Index = -1;        //root didn’t originate from a move
      Depth = 0;         //initial state
}

uniqueNodes.Add(root.Value, root); //root.value is our key

Now let’s simulate our loop of generating a node, check it, and store it if unique, starting from our root node and see how can we further improve our nodes and tree to simplify our task;

We use a non-recursive queue implementation because we know we can be dealing with an enormous number of nodes (our function call stack really didn’t like recursion for millions of nodes)

Queue<Node> queue = new Queue<Node>;   //queue for breadth-first generation
queue.Enqueue(root);                   //we start from our root
 
//the loop
while (queue.Count > 0 ) {      
      Node currentNode = row.Dequeue();      //Get next node in queue.
 
      for (int index = 0; index < 4; index++) { 
            //Given the current parent node and the move, we get the resulting
             //child node value, encoding our game state
             int value = CreateValueFromMove(currentNode, index);
 
             //creation similar to root node but with additional parent and index
             //initialization as now we are generating from an existing node
             Node node = new Node(value) {
                Value = value;     
                State = DeadEnd       //we do not know if we can reach a solution
                Parent = CurrentNode; //set the parent for solution traversal
                Index = index;        //we track the originating move
                Depth = currentNode.Depth + 1;
             }
...
             //we check for winning condition
             If (WinCondition(value)) {
                   EndBranch(value); //Win case, terminate this branch
 
             } 
             else if (!uniqueNodes.ContainsKey(value)) {  //check duplication
                   AddDuplicate(value); //Duplicate case, handle it
             } 
             else { 
                   AddUniqueNode(node); //Unique node case
             }
      } 
}

Let’s examine all our cases’ details, to find out why this idea of a parent-focused tree can help us solve both the winning condition upward propagation and the duplicate node management.

Unique node case

this node state has not been encountered before so we have to add it to our “tree” and save it as unique. This case is the simplest of the 3:

void AddUniqueNode(Node node) {        
      uniques.Add(node.Value, node); //add it to our dictionary, node.Value as key
      queue.Enqueue(node); //enqueue it to continue our generation from this as root
} 

Being in the queue, the generator will continue to generate this unique node 4 children in a later pass as expected.

Win case

void EndBranch(int value) {            
   If IsMaxcombo(value) //check if our win state has the max combo
       currentNode.PropagatestatetoRoot(NodeState.Ok);
   else
       currentNode.PropagateStateToRoot(NodeState.Maxcombo);
}

Depending on the winning condition, we propagate back to our root the correct state, while collecting the reversed steps to reach this winning node. Once we reach our root, we save the solution.

In our level 1-1 example, after our generation reaches the first winning node from S3 (with a Max Combo as both skiddy disappear at the same time), all the nodes highlighted in green will have their corresponding States set to MaxCombo, the others are still all DeadEnds.

Duplicate case

When we encounter a new node which is a duplicate of a previously encountered node, we cannot simply add it to the queue as this will create an infinite loop in our generation, yet we can’t completely discard as this internal loop is necessary to correctly propagate winning conditions to all nodes, otherwise we’ll end up having some false DeadEnds leftover nodes.

This is not visible in level 1-1 because all branches lead to a winning so let’s use a variation to show this situation:

S2 can only generate an S4 duplicate going left. Without special consideration, after we discard this duplicate, S2 will remain in DeadEnd state because there are no additional children leading to a winning state.

This is the case where our reversed tree comes into play. Let’s first add another field to our node, an additional list of secondary parent nodes. We will add here all the nodes that generate child which are duplicates of this node and as a result can be considered as additional parents of this node.

// A node contains information about board configuration and relations to other nodes
class Node {
      int Value;         //encodes our pieces’ layout and board score
      NodeState State;   //max-combo, ok or dead-end?
      Node[4] Child;     //the states originating from the next 4 moves
      int Index;         //generating moves(none, up, right, down, left)
                         //                 -1     0   1      2     3
      Node Parent;       //state before last move, used to traverse our solution
      Int Depth;         //how many moves it took to reach this node
      List<Node> Parents; //secondary parents from node duplication
}

This is why we call this a “reversed tree”, because without child but with the secondary parents, the relationship between our nodes is expressed like the following example for level 1-1

Node relationship expressed as a “reversed tree”, there is no need to represent win nodes.

Note: it’s possible also for our root node to receive some secondary parents during generation, in level 1-1 it just doesn’t happen.

Now when we encounter a duplicated node that we do not enqueue, we find the original existing node in our unique nodes dictionary, then we add the current parent node to the secondary parents of the original node. In level 1-1 above, S1 has S0 has an original parent, but when we reach its duplicate from S3, we just add S3 in s1 parents list. We do the same when we reach S3 from S1.

In pseudo-code:

void AddDuplicate(int value) {
      Node node = uniques[value];      //find the original node in our dictionary
      node.InsertParent(currentNode);  //add the new parent as a secondary
      ...
}

And, in case the original node state is already set to Ok or MaxCombo from a previous win, we immediately propagate this condition from the current parent up to the root, because the duplication of a node which is part of a solution, automatically creates a secondary path to the same winning node, as a longer but still valid solution.

void AddDuplicate(int value) {
      Node node = uniques[value];      //find the original node in our dictionary
      node.InsertParent(currentNode);  //add the new parent as a secondary
      if (node.State != Deadend) {     //the node is already part of a solution
         currentnode.PropagatestatetoRoot(node.State); //propagate to this parent
      }
}

This is visible also in level 1-1

When we reach the winning state from S3 going Down, we already know S1 is a parent, as it was duplicated before going right. With state propagation, we already know S1 is not a DeadEnd even before analyzing any of its children as now:

S0 -> Right -> S1 -> Left -> S3 -> Down -> Win is a valid, although longer, alternative solution.

In this variation, After S4 generates a winning state going down, propagation will correctly flag S2 as it was inserted as an additional parent in S4’s list.

After covering the 3 cases, when our generation queue runs out of nodes it means the tree is complete and all the unique nodes are in our dictionary.

Due to propagation all states are correctly set and now we can verify that there are no DeadEnds simply enumerating through our dictionary and exiting as soon as we found the first:

//in our tree class
bool HasDeadEnds() {
  foreach (KeyValuePair<int, Node> p in Uniques) { //enumerate through dict.
    Node node = p.Value;
    if (node.State == NodeState.DEADEND) { //if we have a Deadend
       return true; //early positive exit
    }
    return false;
}

If we have even a single DeadEnd the level is not valid, because from that node state it’s not possible to reach an end with or without max combo.

While generating, we also have verified our first rule of correctness: 1 -it must have no dead ends.

Even better, as we already collected all the solution while propagating our states, we can easily check if we have at least a solution with and without the MaxCombo, either flagging while collecting them or checking the solution lists, as to immediately verify rule n.2: it must be solvable with and without the max-combo.

And by checking their length, we also verify condition n.3: a solution without combo cannot be shorter than the one with the combo.

At this point, we can assign our first 3 stars rating for the level.

Additional refinements

Considering how we are using our state information and how this is propagated from a node to his parent up to the root, we can see that we only care to propagate states to DeadEnd nodes, as other nodes are already part of a solution.

This allows, in case of duplication, to skip parent insertions for node that are not in dead end states:

void AddDuplicate(int value) {
      Node node = uniques[value]; //find the original node in our dictionary
      If (currentNode.state == DeadEnd)
             node.InsertParent(currentNode); //add the new parent as a secondary
      if (node.State != Deadend) { //the node is already part of a solution
         currentnode.PropagatestatetoRoot(node.State); //propagate to this parent
      }
}

As another improvement, our InsertParent(Node node) implementation should take care that the parent is not already present in the list and use a fast way to insert retrieve elements, eg: a sorted list with binary search insertion or similar. Once a parent receives states propagation, it can be removed from the parent's list as no further processing will be necessary.

Finally, solution reconstruction is a separate process from the generation/analysis and in Skiddy’s case, it’s implemented in a separate thread just saving all the winning nodes’ parents in a list.

In our node class

//We can change this method back to its original form
void PropagateStateToRoot(NodeState state) {
      State = state;
      Parent.PropagateState(state); //recursively call this on parent node
}

And modify our tree class EndBranch method

//but add this In our tree when we reach a winning state
void EndBranch(Node node) {            
      WinningNodes.Add(node); //This list will be consumed by another thread where we
            //willtraverse back to our root, rebuilding a solution and adding it to
            //the solutions list 
      If IsMaxcombo(node.Value) //check if our win state has the max combo
            currentNode.PropagatestatetoRoot(NodeState.Ok);
      else
            currentNode.PropagateStateToRoot(NodeState.Maxcombo);
}

In conclusion, after this revised approach to our nodes generation, we can determine if a level is correct and how it rates according to our 3 rules.

Watching our unique dictionary after Level1-1 analysis, with details of root node [0], S3[3] and S8 [8] with everything discussed so far. Every node has its state correctly set.

But a correct level is in no way a guarantee of good, fun level. Is it possible to add additional rules and automatic checks that can relate to a level’s quality?

We will explore this in part 3.

Disclaimer: As a first experience in designing/programming a video game, we are aware our methods might not be the best but they served the purpose and aided the design and the code to evolve and complement each other.  If readers have questions or suggestions regarding the subject matter and how to improve it, we at BigBangPixel would sincerely like to discuss it, so write us at [email protected]

License: Skiddy and all related assets including levels and editors are Copyright 2012 by BigBangPixel and all rights are reserved. The information published in this article can be used by anyone for non-assignable, non-transferable, non-commercial use or educational purposes.  Any other use, including any redistribution in

whole or in part, requires explicit, written permission from BigBangPixel.