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

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?

• Much better than the original question thanks. Do remember that editing the original question instead of reposting is the preferred action in these situations. Jan 15, 2014 at 20:24
• @Byte56 Thanks. I will remember that next time. Jan 15, 2014 at 22:25

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