Recently, I've been trying to make a simple Match-3 game. As the core worked, I tried to expand it by adding blocking fields and diagonal movement. This has proven more difficult than I thought.

For those who don't know the game mechanics - the essence of the game is a rectangular array filled with items (usually 5 or 6 types), Three or more items of the same kind in a vertical or horizontal line create a match, which gets removed from the game. The items on the top fall down to fill the empty space. The empty cells on the top get refilled with more randomly generated items.

It all works fine when all cells are filled with items and gravity makes them fall only vertically. After adding cells that block the movement, this no longer works, because cells below will never be filled. For example:

1 2 3 4 5 1 2 3
2 3 4 5 1 2 3 4
3 4 5 # 2 3 4 5
4 5 1 0 3 4 5 1
5 1 2 0 4 5 1 2
1 2 3 0 5 1 2 3
2 3 4 0 1 2 3 4
3 4 5 0 2 3 4 5

(where 0 means an empty field and # is a block)

The solution here is moving items diagonally to empty spaces that can't normally be filled in any other way. Unfortunately, I tried several times from the scratch and I were unable to make an algorithm working as intended. Items either fall dawn diagonally when they shouldn't, or don't fill any empty spaces. The most promising one moved everything where it should go, but failed in another way:

moves = 0
do {
	foreach (cell in array) {
		if (cell_value == 0)
			list.Add(cell)
	}
	foreach (cell in list) {
		if (cell is on the top)
			continue;
		x = cell.x
		y = cell.y
		if (array[x,y-1] > 0) //if the cell above is not empty or a block...
			Move(array[x, y-1], cell)
		else if (array[x,y-1] == -1) { //the cell above is a block, this cell will never be filled...
			if (array[x-1,y-1] > 0) //check upper-left cell
				Move (array[x-1,y-1], cell)
			else if (array[x+1,y-1] > 0) //check upper-right cell
				Move (array[x+1,y-1], cell)
		}	
		if (moved)
			moves++
	}
}
while (moves > 0)

It kinda works... except it doesn't really care about the order of items falling. It's pretty egregious on boards like this:

# # 3 4 5 1 # #
# 3 4 5 1 2 3 #
3 4 5 1 2 3 4 5
4 5 1 2 3 4 5 1
5 1 2 3 4 5 1 2
1 2 3 4 5 1 2 3
2 3 4 5 1 2 3 4
3 4 5 6 2 3 4 5

It frequently happens that some fields diagonally poach items from other fields, which makes the result weird:

First iteration:

# # 1 2 3 4 # #
# 0 0 0 0 0 0 #
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

Second iteration:

# # 0 0 0 0 # #
# 0 1 2 3 0 4 #
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

Third iteration:

# # 0 0 0 0 # #
# 0 0 0 0 0 0 #
0 0 1 2 3 0 0 4
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

I should probably sort the list, but couldn't find the right criterion. Any ideas how to improve this algorithm? Or am I overthinking it and there is a better way to do this?

I've played several games with blocking squares.

The two answers I've seen is to drop tiles in from the same place where new tiles flow from normally, or to flow blocks around from the sides.

For the first, if you normally drop from the top, it can work to still drop them from the top, they just animate in over the top of everything else. In one game where time was critical this served as a slight penalty because it took time to slowly move them in. Players avoided the area, and consequently it was made more valuable and also more costly in time.

In some where they flow from the side, there were variations. An arrow/cut-out that showed the direction of the flow as part of the block. Alternate from either side. If you go that route, figure out a sane rule that you can build gameplay from, like allowing a player to set the direction, or not do that to add a challenge.

What about something such that when an object lands on a second stationary object and there is nothing to the left or right of the stationary object, then the first object takes the space to the left or right of the stationary object?

What about something such that when an object lands on a second stationary object and there is nothing to the left or right of the stationary object, then the first object takes the space to the left or right of the stationary object?

Not in the current version of the algorithm, though my initial plan also involved horizontal movement.

I've played several games with blocking squares.

The two answers I've seen is to drop tiles in from the same place where new tiles flow from normally, or to flow blocks around from the sides.

For the first, if you normally drop from the top, it can work to still drop them from the top, they just animate in over the top of everything else. In one game where time was critical this served as a slight penalty because it took time to slowly move them in. Players avoided the area, and consequently it was made more valuable and also more costly in time.

In some where they flow from the side, there were variations. An arrow/cut-out that showed the direction of the flow as part of the block. Alternate from either side. If you go that route, figure out a sane rule that you can build gameplay from, like allowing a player to set the direction, or not do that to add a challenge.

The way it should work is that, after encountering a single blocking field, the item should go around it using the shortest possible path.

Right now, the algorithm works by finding all empty fields and making them suck the nearest item in. They should first try to grab the item directly on top of them. If they will never be able to get one because of a blocking field on the top, they should try to grab one diagonally. Unfortunately, it works quite too well and sometimes an empty cell just under a block grabs its item before a neighbor. Ideally, all diagonal movement should happen after vertical one.

After some tinkering, I finally found a solution. It appears that this version of the algorithm can be improved by splitting it into two iterations. First only vertical movement should be performed, then we can fill the rest of the zeros diagonally. Of course, we still need to check if the field can't be filled vertically (if the block directly over the empty one is a block).

This is not the end, however. We need to track if an item has already been moved - either by flagging it individually or making an another array where we mark fields where an item was moved. Otherwise we'll end up with situation when some of the items move too quickly or get diagonally poached.

Similarly you can introduce horizontal movement, but this creates a problem when some items move back and forth if there is a free space next to them.

I'll try to update the algorithm when I'm not on cellphone.

BTW: The previous version of the algorithm has an error - moves has to be set inside do... while... loop, otherwise it will always be positive until overflowing.