Calculating unique ID number from a set of bitmasked tiles

Question

I'm writing a match3-style game where you as player need to match tiles with three or more of the same type.

I'm thinking what is the best method to recognize the shapes without writing a monstrosity of switch/if-else statements. Because in my game the player should be able to match many different shapes that consist of at least 3 or more vertical and/or horizontal shapes, for example ...

###

#
#
#

#
#
###

###
 #
 #

 #
###
 #

##
##
##

And any variation of these (the last one is a block). I'm currently using a floodfill algorithm that not only find all the connected tiles but also assigns a bitmask depending on if and what connections the tile has to its surrounding tiles (it's based on the bitmasking explained here.

Here is the relevant code part for this (Unity, C#):

    internal const int BITMASK_NONE = 0;
    internal const int BITMASK_TOP = 1;
    internal const int BITMASK_RIGHT = 2;
    internal const int BITMASK_BOTTOM = 4;
    internal const int BITMASK_LEFT = 8;

    internal const int BITMASK_CORNER_TOP_RIGHT = 3;
    internal const int BITMASK_CORNER_BOTTOM_RIGHT = 6;
    internal const int BITMASK_CORNER_TOP_LEFT = 9;
    internal const int BITMASK_CORNER_BOTTOM_LEFT = 12;

    internal const int BITMASK_THREEWAY_TOP = 11;
    internal const int BITMASK_THREEWAY_RIGHT = 7;
    internal const int BITMASK_THREEWAY_BOTTOM = 14;
    internal const int BITMASK_THREEWAY_LEFT = 13;

    internal const int BITMASK_VERTICAL_LINE = 5;
    internal const int BITMASK_HORIZONTAL_LINE = 10;

    internal const int BITMASK_CROSS = 15;


    private Dictionary<int, GridCell> FindConnectedCells(GridCell cell)
    {
        var connectedCells = new Dictionary<int, GridCell>(size);

        cell.isFlagged = true;

        _cellStack.Clear();
        _cellStack.Push(cell);

        while (_cellStack.Count > 0)
        {
            cell = _cellStack.Pop();

            /* Assign bitmask to cell. */
            if (cell.Equals(cell.top)) cell.bitmask |= BITMASK_TOP;
            if (cell.Equals(cell.bottom)) cell.bitmask |= BITMASK_BOTTOM;
            if (cell.Equals(cell.right)) cell.bitmask |= BITMASK_RIGHT;
            if (cell.Equals(cell.left)) cell.bitmask |= BITMASK_LEFT;

            connectedCells.Add(cell.id, cell);

            if (FlagMatchingCell(cell, cell.top)) _cellStack.Push(cell.top);
            if (FlagMatchingCell(cell, cell.bottom)) _cellStack.Push(cell.bottom);
            if (FlagMatchingCell(cell, cell.right)) _cellStack.Push(cell.right);
            if (FlagMatchingCell(cell, cell.left)) _cellStack.Push(cell.left);
        }

        return connectedCells;
    }

This uses a stack-based flood-fill. In any case every tile (or cell) ends of with a specific bitmask value between 1 and 15 and I want to calculate a unique number from these and a couple of other numbers (e.g. how many tiles are in the shape, how many horizontal/vertical tiles it has, etc.) but so far I haven't managed to calculate it to produce really unique numbers. Every now and then it comes up with different shapes that have the same calculated number.

Another problem with this approach is that it can't detect whether all tiles of the shape are valid or not. Consider this shape:

 #
****

It should be recognized only as a shape of four horizontal tiles but it would also include that additional tile on top.

So my question is: What is another good approach for recognizing all these different shapes? Basically the idea of calculating a unique number for every shape doesn't seem so bad because it seems very elegant but there is then still the problem with the odd shapes like above.

UPDATE:

Possible solution to calculate unique number ID for each possible variation (Code in Swift because written in Playground for faster testing):

import Cocoa
import Foundation

var d:[Int:Int] = [:]

func calc(n:Int)
{
    var s = ""
    for i in 1 ... 15
    {
        let result = i * (i + (i * n * n))
        s += "\(result)  "
        if let _ = d[result] { print("\t\t\tAlready exists: \(result)") }
        else { d[result] = result   }
    }
    print("(\(n)) \(s)");
}

for tileCount in 3 ... 30
{
    calc(tileCount)
}

Output:

(3) 10  40  90  160  250  360  490  640  810  1000  1210  1440  1690  1960  2250  
(4) 17  68  153  272  425  612  833  1088  1377  1700  2057  2448  2873  3332  3825  
(5) 26  104  234  416  650  936  1274  1664  2106  2600  3146  3744  4394  5096  5850  
(6) 37  148  333  592  925  1332  1813  2368  2997  3700  4477  5328  6253  7252  8325  
(7) 50  200  450  800  1250  1800  2450  3200  4050  5000  6050  7200  8450  9800  11250  
(8) 65  260  585  1040  1625  2340  3185  4160  5265  6500  7865  9360  10985  12740  14625  
(9) 82  328  738  1312  2050  2952  4018  5248  6642  8200  9922  11808  13858  16072  18450  
(10) 101  404  909  1616  2525  3636  4949  6464  8181  10100  12221  14544  17069  19796  22725  
(11) 122  488  1098  1952  3050  4392  5978  7808  9882  12200  14762  17568  20618  23912  27450  
(12) 145  580  1305  2320  3625  5220  7105  9280  11745  14500  17545  20880  24505  28420  32625  
(13) 170  680  1530  2720  4250  6120  8330  10880  13770  17000  20570  24480  28730  33320  38250  
(14) 197  788  1773  3152  4925  7092  9653  12608  15957  19700  23837  28368  33293  38612  44325  
(15) 226  904  2034  3616  5650  8136  11074  14464  18306  22600  27346  32544  38194  44296  50850  
(16) 257  1028  2313  4112  6425  9252  12593  16448  20817  25700  31097  37008  43433  50372  57825  
(17) 290  1160  2610  4640  7250  10440  14210  18560  23490  29000  35090  41760  49010  56840  65250  
(18) 325  1300  2925  5200  8125  11700  15925  20800  26325  32500  39325  46800  54925  63700  73125  
(19) 362  1448  3258  5792  9050  13032  17738  23168  29322  36200  43802  52128  61178  70952  81450  
(20) 401  1604  3609  6416  10025  14436  19649  25664  32481  40100  48521  57744  67769  78596  90225  
(21) 442  1768  3978  7072  11050  15912  21658  28288  35802  44200  53482  63648  74698  86632  99450  
(22) 485  1940  4365  7760  12125  17460  23765  31040  39285  48500  58685  69840  81965  95060  109125  
(23) 530  2120  4770  8480  13250  19080  25970  33920  42930  53000  64130  76320  89570  103880  119250  
(24) 577  2308  5193  9232  14425  20772  28273  36928  46737  57700  69817  83088  97513  113092  129825  
(25) 626  2504  5634  10016  15650  22536  30674  40064  50706  62600  75746  90144  105794  122696  140850  
(26) 677  2708  6093  10832  16925  24372  33173  43328  54837  67700  81917  97488  114413  132692  152325  
(27) 730  2920  6570  11680  18250  26280  35770  46720  59130  73000  88330  105120  123370  143080  164250  
(28) 785  3140  7065  12560  19625  28260  38465  50240  63585  78500  94985  113040  132665  153860  176625  
(29) 842  3368  7578  13472  21050  30312  41258  53888  68202  84200  101882  121248  142298  165032  189450  
(30) 901  3604  8109  14416  22525  32436  44149  57664  72981  90100  109021  129744  152269  176596  202725  

Answer 1

Up to about an 8x8 grid, it makes sense to index your shapes as a simple bitboard:

1. Find your whole connected shape via flood fill, as you do now. Record the leftmost column and topmost row encountered

2. Initialize your ID to a 64-bit unsigned integer value of 0

3. For each cell in your shape, use an OR operator to set one bit in your ID, like so:

   bit = (cellColumn - leftmostColumn) + (cellRow - topmostRow) * 8
   ID |= (1 << bit)
   

At the end you'll have an integer that's unique to this shape, and insensitive to translation. (It's still sensitive to rotations & flips though. To merge those, you can choose the orientation with the minimal / maximal integer value as "canonical")

This can get impractical if your shapes get bigger though. If we wanted to store a line of 16 cells in a row or column or any other arrangement using a square bitboard like this, we'd need 256 bits, using 16 bits per cell!

---

If your shapes can get large like this, but are generally sparse (lines and Ls, not big blocks usually), you can take a different approach that doesn't assume a fixed-size bounding box for your shapes:

1. Initialize your ID to 0 / an empty bit stream.

2. Start at the leftmost cell of the top row of your shape, facing right

3. Begin a depth-first search from this cell, visiting each other cell in the shape. Make sure your search checks its neighbours in a deterministic order (the order is arbitrary, as are the bit codes below, just be consistent)

4. Each time the depth first search steps forward into a new cell, or backtracks to a previous cell, append some bits to your ID:

   • When you go forward (progressing in same direction as the last movement), write the bits 11

   • When your search takes a right turn, write the bits 10

   • When your search takes a left turn, write the bits 01

   • When you backtrack, write the bits 00

Concatenating all of these bits together, you now have a bit string that's unique to the particular polyomino shape traversed (given your particular search sequence). You can reconstruct the shape from its ID just by playing back the "dance steps" encoded in the bit string.

The trouble with this method is that it can produce bit strings which are quite long. Run length encoding can help significantly, but you may pay between 2-8 bits per cell in the shape (a + junction can be entered & backtracked to 3 times). Still better than very sparse use of a large bitboard, but not competitive for smaller/denser shapes.

Answer 2

One way you could do this is to set a specific tag for each type of tile within the Inspector View of each tile in Unity3D. Then you could write code for it, a simple example being:

void OnTriggerEnter()
{
   if (tag == "redTileGroup")
  {
     // do something
  } 
}