8
\$\begingroup\$

I am trying to write a match-three puzzle game like 'call of Atlantis' myself. The most important algorithm is to find out all possible match-three possibilities. Is there any open source projects that can be referenced? Or any keywords to the algorithm? I am trying to look for a faster algorithm to calculate all possibilities.

Rules:

  • Diagonals don't count.
  • The size is 8x8

Thanks.

\$\endgroup\$
3
  • \$\begingroup\$ Do you mean a 8x8 grid of tiles, each different, and you match 3 in a line to do something? Like Bejeweled? EDIT: Found a link..yes, it looks similar to Bejeweled. \$\endgroup\$ Commented Aug 11, 2010 at 18:16
  • \$\begingroup\$ Another issue is after match 3 objects in a row and eliminates them, is it necessary to rescan all grids or just partial? \$\endgroup\$
    – Stan
    Commented Aug 11, 2010 at 23:49
  • 1
    \$\begingroup\$ Since you have time enough (you'll be playing some sort of animation when you remove the match) you'll have ample time to rescan the whole grid. (I know, I implemented it the way I wrote below). \$\endgroup\$
    – Kaj
    Commented Aug 12, 2010 at 1:15

5 Answers 5

20
\$\begingroup\$

I helped port one of these games to a handheld platform. Looking back at their AI code for finding potentials: yipe, it's complicated, brutish (quadruply nested loop, calls itself recursively occasionally, etc), and it doesn't appear at all cache-friendly at first glance.

(Some of that complexity comes from trying to evaluate the strength of the move in context: valuing longer chains higher, looking for combos, etc...)

But it doesn't really need to be "optimal"; we didn't even touch the code when we ported it. It never showed up on the profiler.

Looking at it now, even at one 32 bit word per cell (and I think they actually used a byte per cell), the entire board will fit in a minuscule L1 cache, and you can do many excess reads on stuff that's cached without impacting framerate too much. Especially since you only need to do this whole process once each time the board configuration changes. (A big-theta hovering around n^2 isn't that horribly bad with a very low n, not to mention the small multiplier given the cached memory.)

That having been said: for amusement, let's attempt to parallelize the problem. Starting with bitwise operations.

Assume you have a bitmask representing all of the pieces (we'll call them stones) in a row that are of one particular type (we'll use colors to distinguish types). We'll start only looking at red stones, and worry about the cost of calculating the bitmask later.

// Let's assume top right indexing.
// (The assumption is not necessary, --
//    it just makes the left-shift and right-shift operators 
//    look like they're pointing in the correct direction.)

// this is for row 2
col index  76543210
color      BRRGYRBR // blue, red, red, green, yellow, ...
"red" bits 01100101

We're looking for the series that need just one swap to become a series of 3. Courtesy Kaj, this is one of three combinations, basically: XoX, oXX, or XXo where X is a matching stone and o is something else.

(This idea is borrowed from the marvelous Hacker's Delight book; see also the fxtbook if such things delight you.)

// using c-style bitwise operators:
// & is "and"
// ^ is "xor"
// | is "or"
// << and >> are arithmetic (non-sign-extending) shifts

redBitsThisRow = redBitsRows[2]

// find the start of an XoX sequence
startOfXoXSequence = redBitsThisRow & (redBitsThisRow << 2);
// for our example, this will be 00000100

// find any two stones together in a row
startOfXXSequence = redBitsThisRow & (redBitsThisRow << 1);
// for our example, this will be 01000000

It's more useful to know the positions of the missing stones, not the start of the XX or XoX sequence:

// give us any sequences that might want a stone from the left
missingLeftStone = startOfXXSequence << 1;
// for our example, this will be 10000000

// give us any sequences that might want a stone from the right
missingRightStone = startOfXXSequence >> 2;
// for our example, this will be 00010000

// give us any sequences that might want a stone from the top or bottom
missingTopOrBottomStone = missingRightStone | missingLeftStone | (startOfXoXSequence >> 1)
// for our example, this will be 10010010

(About 1 load and 9 ALU instructions -- 5 shifts, 2 ors, 2 ands -- with a dreadful CPU that doesn't include an inline shifter. On many architectures these shifts might be free.)

Can we fill these missing places?

// look to the left, current row
leftMatches = redBitsThisRow & (missingLeftStone << 1)

// look to the right, current row
rightMatches = redBitsThisRow & (missingRightStone >> 1)

// look on the row above
topMatches = redBitsRow[1] & missingTopOrBottomStone

// look on the row below
bottomMatches = redBitsRow[3] & missingTopOrBottomStone

(Another 2 loads and 6 ALU instructions -- 4 ands, 2 shifts -- with a bad CPU. Note that row 0 and row 7 may give you trouble -- you can choose to branch around these calculations, or avoid the branch by allocating space for two extra rows, one before 0 and one after 7, and leave them zeroed out.)

Now we have several "matches" vars that indicate the position of a stone that can be swapped in to make a match.

This assumes a "count trailing zeros" intrinsic or very cheap inline method:

swapType = RIGHT_TO_LEFT;
matches = leftMatches;
while ( (colIdx = ctz(matches)) < WORD_BITS ) {
   // rowIdx is 2 in our examples above
   workingSwaps.insert( SwapInfo(rowIdx, colIdx, swapType) );
   // note that this SwapInfo construction could do some more advanced logic:
   //   run the swap on a temporary board and see how much score it accumulates
   //   assign some sort of value based on preferring one type of match to another, etc

   matches = matches ^ (1<<colIdx); // clear the match, so we can loop to the next
}
// repeat for LEFT_TO_RIGHT with rightMatches
// repeat for TOP_TO_BOTTOM with topMatches
// repeat for BOTTOM_TO_TOP with bottomMatches

Note that none of this bit logic should break down in little-endian vs big-endian environments. It gets much more tricky for boards wider than your machine word size. (You could experiment with something like std::bitset for this.)

What about columns? It may be easiest just to have two copies of the table, one stored in row-order and one stored in column-order. If you have getters and setters wrapping board access, this should be trivial. I don't mind keeping two arrays up to date, after all a set becomes rowArray[y][x] = newType; colArray[x][y] = newType; and that's simple.

...but managing rowBits[color][row] and colBits[color][col] becomes obnoxious.

However, as a quick aside, if you do have rowBits and colBits, you can run the same code with rowBits pointing at colBits instead. Pseudocode, assuming board width = board height = 8 in this case...

foreach color in colors {
    foreach bits in rowBits, colBits {
        foreach row in 0..7 { // row is actually col the second time through
            // find starts, as above but in bits[row]
            // find missings, as above
            // generate matches, as above but in bits[row-1], bits[row], and bits[row+1]
            // loop across bits in each matches var,
            //    evaluate and/or collect them, again as above
        }
    }
}

What if we don't want the bother with converting a nice 2D array into bits? With an 8x8 board, 8 bits per cell, and a 64-bit-capable processor, we might be able to get away with it: 8 cells = 8 bytes = 64 bits. We're locked to our board width, now, but this seems promising.

Assume "0" is reserved, stones begin at 1 and go to NUM_STONE_TYPES inclusive.

startOfXXSequence = rowBytes ^ (rowBytes << (8*1))
// now all bytes that are 0x00 are the start of a XX sequence

startOfXoXSequence = rowBytes ^ (rowBytes << (8*2))
// all bytes that are 0x00 are the start of a XoX sequence

Note this doesn't need one pass per color. In BRBRBRGY we'll get a startOfXoXSequence that might be something like 0x00 00 00 00 aa bb cc dd -- the top four bytes will be zero, indicating a possible sequence starts there.

It's getting late, so I'll leave off here and possibly come back later -- you can continue along this vein with xors and "detect first zero byte" tricks, or you could look into some integer SIMD extensions.

\$\endgroup\$
5
  • \$\begingroup\$ Love the bit math implementation (I'm a performance freak) :o) However for an 8x8 grid it's really not needed. I had the blatantly naive implementation above running happily at 60fps while it was at the same time scraping a graphics window of the game running to read the actual input from. \$\endgroup\$
    – Kaj
    Commented Aug 12, 2010 at 2:43
  • \$\begingroup\$ @Kaj: yeah, I don't disagree =) I should probably have been more clear about that up front. Even the giant function with the quadruply-nested for loop that would occasionally call itself recursively in the code I mentioned ran just fine on the limited platform we ported it to. It's called very infrequently, and has a tiny data set to traverse. \$\endgroup\$
    – leander
    Commented Aug 12, 2010 at 3:55
  • \$\begingroup\$ +1 for awesome in-depth-ness and proper crediting though :op \$\endgroup\$
    – Kaj
    Commented Aug 12, 2010 at 4:29
  • \$\begingroup\$ I love like this answer is practical in the beginning, but it doesn't stop there and dives into the academical later... \$\endgroup\$ Commented Dec 9, 2013 at 11:55
  • \$\begingroup\$ For an increased performance, you can precalculate leftMatches, rightMatches, missingTopOrBottomStone for every possible combination on the row / column. The required bits for storing the calculations would be columns * 3 * (2 ^ columns). 2 ^ columns are possibilities, and columns * 3 are the bits required for all 3 calculations. \$\endgroup\$
    – Veehmot
    Commented Aug 5, 2014 at 16:51
9
\$\begingroup\$

You're overthinking the problem. In a single line of 8, there are 6 possible positions for a match-3, so for the whole 8x8 board there are only 96 possible match-3s. Checking 96 possibilities uses an insignificant amount of CPU time. You're probably using thousands times more clock cycles just drawing one frame.

If you're looking for swap-two-adjacent moves that can make match 3s... For each possible position, if there are already 2 pieces that match, there are at most 3 possible swaps that can make a match 3. For one line, there are at most 23 moves to consider, and for the whole board there are 112 moves to consider. Checking 112 moves is also an insignificant amount of CPU time.

\$\endgroup\$
0
7
\$\begingroup\$

There's only a few combinations that can make a match. X.X with one below or above the center (and rotated 90 degrees), and xx. with one to the right or top of the '.' (and the rotated and mirrored on both axes variants. So that makes for 14 different search patterns that need to match a (max 4x3) grid against the 8x8 grid. I'd just brute force and slide the pattern along the 8x8 grid and check if the places where there's an x are the same. If so it's a set that can create a triple.
So basically (for example) slide

. . . .
xx.x
. . . .
or (anotheher example)
. x .
x . .
. x .

across the board - if all three x positions have the same icon it's a possible move.
And that times 14 for all possible moves.

\$\endgroup\$
3
  • 2
    \$\begingroup\$ This is the only answer that seems to find the actual valid moves, as opposed to just looking for existing runs of three. \$\endgroup\$
    – JasonD
    Commented Aug 11, 2010 at 22:46
  • 1
    \$\begingroup\$ Ohhh I misunderstood the question. As I seem apt to do lately. :-\ \$\endgroup\$
    – Ricket
    Commented Aug 12, 2010 at 0:27
  • \$\begingroup\$ Don't be hard on yourself for trying to help! The question was kinda open to both interpretations. \$\endgroup\$
    – Kaj
    Commented Aug 12, 2010 at 6:17
2
\$\begingroup\$

If speed is really an issue, I would say to try something like:

  • Iterate the whole grid, starting from top left.

  • At every point on the grid until and including the 6th column, check one tile right, and down (you do not need to check left and up because you've done this)

  • As you hit the 7th column, only check down. (There is no room for 3 along when there's only 2 columns)

  • If they match, then try checking one more tile along/down. If they don't, move to the next tile along.

  • When you finish the 8th column, move down a row.

But for an 8x8 grid, there isn't much optimization needed. An easier form would be (similar):

  • Iterate the whole grid, starting from top left.

    • At every point on the grid until and including the 6th column, check one tile right, and down (you do not need to check left and up because you've done this)

    • If they match, then try checking one more tile along/down. If they don't, move to the next tile along. Handle out-of-board errors as 'not the same'.

    • When you finish the 8th column, move down a row.

This would allow much simpler code in the for loop, since you do not have an if structure with some code on one side, and slightly tweaked code below it.

\$\endgroup\$
2
\$\begingroup\$

It's not very pretty or elegant, but I wrote a match-3 game in JavaScript. Source code on GitHub, you view the match-3 logic right in your web browser: https://github.com/richtaur/bombada/blob/master/htdocs/js/match3.js#L184

\$\endgroup\$
1

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .