# Efficient algorithm for match-3 block detection and clearing?

So I'm making a game with elements of a match-3 puzzler (e.g. Columns, Bejeweled, Tetris Attack). However, I don't know where to begin in terms of creating an algorithm that lets me detect matches and clear them efficiently.

These are the assumptions about my game;

• Blocks of a like color can be matched horizontally, vertically, or diagonally in sets of at least 3.
• Blocks are held within a grid. They do not move horizontally.
• However, blocks do move vertically due to gravity.
• This is an action game, therefore we have to check up on the grid each frame.
• Due to the design of my game, however, we only need to check for matches if at least one block was falling in the previous frame.

Any tips? I'm using Python and PyGame.

-

When a block moves, add it to a list that needs checking.

When you check a block remove it from the list.

First, decide if lines of 4+ count and if not, which set of 3 takes precedence in a row of 4.

Have your algorithm check in 4 directions instead of 8. (Horizontal, Vertical, and 2 diagonal)

Assuming you first check horizontally and allow matches of 4:

• Look at the block to the left. If it matches increase the # of matched blocks from 1 to 2.

• Keep looking left until you find a block that does not match or the edge of your playing area.

• Then, look to the right and continue adding in the same manner until you find an unmatched block.

• If the number of matched blocks from both directions is greater than 3, then mark the blocks for deletion/exploding.

• Repeat for the other 3 directions.

• Delete all of the blocks marked for deletion.

-
Beautiful! Thanks! How do programmers come up with these sorts of things? –  JesseTG Aug 20 '12 at 23:50