Match-3 algorithm to fill empty space left from removing matches

Question

I am currently creating a match 3 game.

I am at the point where I have objects dropping down in the column when only one item is removed. So if an item is removed, the above item moves into its old position etc.

The problem I am having now is that when more than one item is removed from a column, the items in that column only drop down to the first item that was removed. Instead of filling in both items that were removed it just drops down to fill in the first one.

So basically, if two(or more) items are removed from a column the second, third, fourth, etc positions are left blank.

The way I am designing my game is I am using units of 1. So each item takes up 1 unit by x and 1 unit by y. This means that I can position the items like in a grid, at 0x1, 0x2, etc.

What kind of algorithm could I use to move multiple items down to fill the empty space?

Answer 1

Here's a simple algorithm that'll do what you want:

For each column
  Find the lowest empty position
     While that position is empty, move every item above it down by 1
  Repeat until there are no empty positions

In code that might look like:

for(Column c : columns)
   continue = true; //assume there's an empty so we can look for it
   while(continue)
      emptyPosition = getLowestEmpty(c);
      if(emptyPosition == null) //no empties found
          continue = false;
          break;
      while(positionIsEmpty(emptyPosition.column, emptyPosition.row)) 
          //while the position is empty, move everything above it down
          moveDownItemsAbovePosition(emptyPosition)

where getLowestEmpty(c) would be something like:

getLowestEmpty(Column c)
   for(Row r in c.rows) //assuming bottom to top
      if(positionIsEmpty(c, r))//check if the position is empty
         return position(c,r)//if it is, we've found the bottom most empty
   return null //we didn't find any empties