As we start working on our first full-length game, Gemlight Alchemy, I find myself revisiting problems I faced in Farmageddon, and looking for better ways of solving them.

For instance, Group finding.

Both of these games are grid-puzzler games.  In Farmageddon, when you harvest a plant, it checks all its neighboring plants to find the full group of contiguous (next to each other) squares including the one clicked that shared the same type and level.  This is a very easy distinction to make visually, but marginally more difficult from within a computer program.  In Gemlight, the user will be combining groups of elements of the same level to form recipes, so I need to detect the full group of contiguous squares with the same level every time a new element is placed on the board, and react when that group has four or more elements.

How I solved this in Farmageddon:

The field in farmageddon is populated with a 2-dimensional array of FieldElements.  This is a class that contains all of the logic for how that square behaves during gameplay.  One of the values associated with this class is a dictionary of neighbors.  This is populated just after the element itself and contains four FieldElement values: above, below, right, and left.  If a given square does not have one of these neighbors, either because it is a border square, or because it is up against an in-game border (such as the stream in level 2), the value for that neighbor is nilPlants, are also a class, and instances of this class have a type, and a stage (i.e. mature radish = {type: ‘radish’, stage:3}).  Whenever a Plant is created, it is associated with a FieldElement.  When a Plant whose stage is equal to 3 is clicked, a function is called to recursively search through its neighbors to see if they matched its type and stage.  What I mean by this is that I wrote a function that would check a given square to see if it its neighbors had a Plant of stage 3 and the right type, and would call itself on each neighbor that did.

According to wikipedia, Recursion means this:  “Recursion in computer science is a method where the solution to a problem depends on solutions to smaller instances of the same problem”.   The simplest example of this is with a factorial function.

def factorial(number)
{
    if (number==0) then
    {
        return 1
    }
    else
    {
        return number*factorial(number-1)
    }
}

Here, the final value “returned” is, in fact, the factorial of that number as 5=5*(4!)=5*(4*(3!)) = 5*(4*(3*(2!))) = 5*4*3*2*1.
In my case, what was “returned” was a list of all of the matching squares. The logic for that search was something like this:

class plant
{
  def onClick()
  {
    if (self.stage == 3)
    {
      self.search([])
    }
  }
  def search(found_bunch)
  {
    self.checked = true
    for each neighbor in my_neighbors
    {
      if (neighbor.contents is a plant) and (neighbor.type == self.type) and (neighbor.stage == 3) and (neighbor.checked == false) then
      {
        found_bunch = found_bunch + neighbor.search(found_bunch)
      }
    }
    return found_bunch
  }
}

Breaking down what this is doing:
Our user clicks on a mature radish. As discussed earlier, this is a

  • Plant
    • with a type of “radish” and a stage of 3
      • that is associated with a FieldElement
        • which corresponds to a tile in the game grid/field.

    This Plant has an onClick function that is called whenever it is clicked on by the user. Because its stage is equal to (==) 3, it will call its search() function. The search() function takes a list as a single argument, and to initialize it, we pass in an empty list. This function will check each of this Plant‘s neighbors and see if that neighbor also contains a Plant of type “radish” and stage 3. I also have a checked value that prevents us from searching the same square twice. For each neighbor that matches, I add neighbor.search(found_bunch) onto the end of found_bunch. What this does in practice is add any of that neighbor’s neighbors that also match.. and any of their neighbors, and so on.

    This will, in fact, return the full group of stage 3 radishes.

    For Gemlight, I did something different. This time, I built a separate ComboHunter class to do this hunting for me. Whenever a tile is clicked on, an instance of this class is created.
    This class looks something like this:

    class ComboHunter
    {
        boardElement origin # this is set as the "clicked square" that instantiates this class
        boardElement[] found_combo
        string[] searched
        string[] recipe
    
        def search(square)
        {
            add (the name of that boardElement) to (self.searched[])
            if (that element contains an object of the same tier as the one in self.origin) then
            { 
                add (this square) to (self.found_combo)
                if (self.recipe doesn't already contain this square's type) then
                {
                    add (this square's type) to (self.recipe)
                }
            }
            Vector3 neighbors = [a list of 3d locations of the neighbors of square]
            for (each neighbor in neighbors)
            {
                if ((there is a boardElement at that location) and  
                    (that boardElement contains an element of the appropriate tier) and
                    (the name of that boardElement is not in self.searched[])) then
                {
                    search(neighbor)
                }
            }
        }
    }
    

    The ComboHunter is initialized with an origin value that points to the Clicked boardElement. It then traverses through the neighboring squares in much the same way as the search algorithm in Farmageddon. The key difference is in the way that the data related to the search is encapsulated. In Farmageddon, the search function was defined as part of the Plant class. The search is initiated but the origin Plant’s Click() event function, and the information about the search results is returned to that click function. This time, by pulling out the search feature into a whole new class (my ComboHunter), I remove the necessity for the objects to even know they are being searched.
    I like this better because for a number of reasons:

    • One of these is that it removes that checked value, which I had to make sure to set back to false as soon as the search was over (a couple of annoying bugs spawned from this).
    • It is also a little cleaner to me to have an outside entity looking at all of the tiles searching for these combos than to have the tiles themselves communicate with each other to find the combo. Part of this is that I tend to anthropomorphize my code a bit, and this feels more like someone looking at a group of sheep and attempting to find a pattern among them, while the other was like a group of sheep being asked to communicate with each other to somehow determine their groupings… Sheep shouldn’t know anything about that, and neither should Plants or boardElements. :-p
    • And finally… a little because when I thought of the name ComboHunter, I immediately thought of a little monster popping into existence when a tile is clicked and stomping around the board eating up combos… :-)

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>