Tile pair matching algorithm

Question

I'm trying to make a tile matching game. User can select a pair of tiles from a square grid, and if they match, both are removed from the grid.

Tiles are matched if:

• they are of the same type (many types of tiles are in the grid) AND
• they can be connected in the grid (either adjacent, or has a clear path of empty spaces between them in the grid)

I would like to scan the grid in advance and find the currently matching pairs (desirably with the path that connects them). Thus I can:

• give hint to users if they're stuck in finding a pair
• detect a situation when no more pairs can be matched (so the tiles will be reordered)

Ideally during the scan each tile pair of the same type should be taken and checked for matching. Is there any algorithm/technique I can use in here to obtain an optimized approach in finding the connecting paths?
Also, is there anything I should take care of while initializing the grid (currently just random assignment) so as to ensure at least some tiles are adjacent in the beginning (and that I won't have to reorder them too much during the game) ?

Answer 1

Question 1

A few details that might need clarification...

---

1) Are tiles considered to be a match if they aren't at the extremities of a clear path? E.g:

 ############
 ###        #
 # ###O#### #
 #  ######O #
 #  ####### #
 ###  ## ####

2) What about diagonals, are they considered adjacent? E.g:

 ############
 ###        #
 ########## #
 #   #O#### #
 ####O##### #
 ########  ##

3) Can there be more than one pair of the same type on the grid, or just one?

---

Either way the solution to your problem will be fairly similar, so I'll assume all three are true for this explanation (I'll use C# as example). Read on for the full set of ideas...

Implementation

Part 1 - Storing and look up

After you finish filling your grid with tiles, you should scan each tile and group tiles of each type together to make it easier to lookup. I'll use a Dictionary, like so:

Dictionary<TileType, List<Tile>> tilesRegistry;

By the way I'll consider a Tile to have this structure:

class Tile
{
    int x, y;
    TileType type;
}

And as you go over each tile in the board, you'll register it on the dictionary doing something similar to:

void RegisterTile(Tile tile)
{
    if(!tilesRegistry.Contains(tile.type))
    {
        tilesRegistry[tile.type] = new List<Point>();
    }
    tilesRegistry[tile.type].Add(tile);
}

Using this Dictionary you can easily find all tiles of any type on the board. For instance, if given one tile, you'd like to find if there's a match you could do:

Tile FindMatch(Tile tile)
{
    List<Tile> tiles = tilesRegistry[tile.Type];
    foreach(Tile t in tiles)
    {
        if(t == tile) continue;
        if(AdjacentTiles(t, tile) || ConnectedTiles(t, tile)) 
        {
            return t;
        }
    }
    return null;
}

I suppose you can figure out other uses for this registry to fulfill your needs.

Part 2 - Matching tiles and pathfinding

The other relevant detail of this implementation is how to create the AdjacentTiles and ConnectedTiles methods.

The AdjacentTiles method should be pretty obvious, just compare the X and Y coordinates of both tiles. The tricky one is ConnectedTiles.

Are you familiar with any pathfinding algorithm, such as A* (which I learned from this resource)?

Since your matching algorithm needs to find tiles connected by a clear path, your best course of action will probably be to use A*.

By treating the board as a sort of game map, with empty cells being considered as open, and other cells being blocked tiles (except for the ones of the tile type you're currently searching), you should be able to easily find the path between two tiles using A*.

Ideally you'll want to encapsulate it so that you may do:

List<Point> GetPath(Tile from, Tile to) {}

And it will return you the path (if any) between both cells.

Question 2

The solution to your second quest seems overly obvious. Start by adding a few pairs directly in adjacent positions on purpose. Then fill the remaining gaps randomly.

Answer 2

To add to David Gouveia's answer.

Path finding is not strictly necessary. Adding to the tile structure as defined by David.

class Tile
{
    int x, y;
    TileType type;
    List empty_set; //reference to empty-tile set
}

And the following list:

List<List<Tile>> all_empty_sets;

The following three concepts are implemented into the setEmpty() method for tiles (ie when a pair is confirmed, both tiles are set as empty).

• When a tile is declared empty, and it is not adjacent to other empty tiles, it can simply be added to a new array, which is added to the list.

• When a tile is declared empty, and is adjacent to one other empty tile, the newly declared empty tile is added to the adjacent tiles empty_set.

• When a tile is declared empty, and is adjacent to several other empty tiles (not necessarily connected), the adjacent empty sets are joined (via a Union). The union then replaces all set references in the affected tiles (via t.setEmptySet(union)).

My attempt at these rules, is shown in my attempt at C# below:

List<List<Tile>> adj_sets = new List<List<Tile>>();
foreach(Tile t in tiles) {
    if(t == tile) continue;
    if(areAdjacentTiles(t, tile) && !t.isEmpty()) {
        if (!adj_sets.Contains(t.getEmptySet())) {
            adj_sets.add(t.getEmptySet());
            empty_set = t.getEmptySet(); // for the adj_sets.Count() == 1 case
        }
    }
}
if (adj_sets.Count == 0) {
    empty_set = new List<Tile>(); // set our empty set
    empty_set.add(this); // add this tile
    all_empty_sets.add(empty_set); // add to the global list
} else {
    if (adj_sets.Count > 1) {
        List<Tile> union = new List<Tile>();

        foreach(List<Tile> l in adj_sets) {
            union = union.Union(l);
            all_empty_sets.remove(l); // remove from the global list
        }

        foreach(Tile t in union) {
            t.setEmptySet(union);
        }

        union.add(this); // add this tile to the resultant set
        empty_set = union; // set our empty set
        all_empty_sets.add(union); // add to the global list
    }
}

And then, in ConnectedTiles(Tile t1, Tile t2), it is as simple as:

for (Tile ti in t1.adjacentTiles()) {
    for (Tile tj in t2.adjacentTiles()) {
        if (ti.getEmptySet() == tj.getEmptySet()) {
            return true;
        }
    }
}
return false;

Albeit, you will need to make a method adjacentTiles() which returns a set of tiles that are classified as adjacent tiles (ie, if you classify a empty square that is diagonal away, as connected, then it must be in this list, but it must also be in the logic for areAdjacentTiles(t, tile)).

NOTE: I have renamed Davids AdjacentTiles(t1, t2) function to areAdjacentTiles(t1, t2), for the sake of clarity.