1
\$\begingroup\$

Taking Candy Crush as an example:

enter image description here

In a Match-3 game, how would you figure out which nearby tiles are 1 move away from creating a match?

Do you basically have to do it by trial-and-error on every single possible moves (behind-the-scenes) to see which resulting matches it would create?

\$\endgroup\$
3
\$\begingroup\$

One way would indeed be to try out the four possible moves for every tile (or rather the ones that have recently moved) and check for matches, then store them as hints. You wouldn't need to do this as often as you might think (especially if you only do it for tiles that have moved); you would only need to swap every tile twice since the one next to it would overlap its two other swaps. Like this:

Swaps

Another way would be to check the surrounding tiles without simulating anything in the background. The best way to do that would be as follows.

Say you have a tile that just moved (center). Focus only on its color and the tiles that are occupied in this diagram:

Tiles to check

Here are all possible matches for the four possible moves (6 blue, 6 red, 4 green):

All possible matches

However, you don't need to check for all of these. What you have is a decision tree; all you need to check are if the orange ones match your center tile. If they do, then you proceed to check the secondary ones. Here's a diagram that connects the orange tiles to their secondary tiles (notice how you only need to do four checks for the green matches and not 8 since the other 4 are the same):

Secondary tiles

Depending on what kind of data structure you store tile data in, these checks can be extremely fast to the point where you don't really need to do any significant optimization. I personally can't think of any other shortcuts.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.