Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I'm making a game with elements of a match-3 puzzler (such as Columns, Bejeweled or Tetris Attack). I don't know where to begin creating an efficient algorithm for matching and clearing.

My assumptions:

  • 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.

Where do I go from here?

share|improve this question

1 Answer 1

up vote 3 down vote accepted

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.

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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