# Best logic to create and drop new gems in a Match-3 game

In a simple match-3 game, with a square gems matrix creating and dropping new gems is fairly simple: when needed I generate those gems above the matrix and then I make them fall into the main matrix simulating that common fall-from-the-ceiling behavior.

Let's now imagine I have a matrix with some rock-type gems, the ones that will never move from their position, and I have cleared an entire column via a "powerful" gem. I have something like this:

OOO OOO
OOO OOO
OOO OOO
OOO OOO
OOX XOO
OO   OO
O     O
OOOOOOO


Here O is a normal gem, and X is a rock gem, that is fixed in the matrix and will not move from its original position.

When the new gems flow into this matrix, they will eventually move to the left or to the right to fill that big empty space, but each one will be dropped into the same column.

I'm wondering what the best way to drop those new gems is. I clearly cannot simply make them move from the top of the screen directly to their final position (as in the previous case), since the would move diagonally across the other gems (too bad).

I'd like to know what's the easiest and most flexible way to compute and the configure the path that each gem will have to follow.

• ..I don't think I've seen a match-3 game that would automatically drop gems into the spaces on left or right? Just straight down. – Trevor Powell Mar 25 '14 at 2:03
• All the games that have those X gems will do it. Candy Crush, Jelly Splash and similar already do this. Is like having a "physical" flux of gems. Like pouring water into the matrix. – marzapower Mar 25 '14 at 10:21
• Usually the first tile drops to the bottom of the empty column, but the others, once reached this one, will eventually flow to the right or to the left, as if they were in a hourglass. – marzapower Mar 25 '14 at 10:22
• If I understood you right, you'd like to achieve something similar to the falling rocks in Boulder Dash? – Mario Mar 29 '14 at 10:16

Without ever having implemented this...

First you will have to control every step of the new gems on their way to their final place. Or in other words, move your sprites only on field on your grid and then calculate their next field.

Now generate new gems and drop them into that column. On each step you check if the gem can fall further down. If not check if there is a free space left or right of the gem the new one landed on. Move the gem to one of that free spaces alternating between left and right.

That should fill up the entire field.

• Agreed. I'll rephrase in my words : you should simulate step-by-step the fall of gems. At each step gems can move only one case a time, depending on the surrounding cases. Then at a step you can move a gem laterally if it cannot move downwards. – Lærne Apr 1 '14 at 11:48

There is an algorithm called BFS (Breadth-first_search).

You can apply this algorithm on each empty cell that has a fixed gem above it, to find the nearest top where you can drop a gem and you can also modify the algorithm to build the shortest path to use it in the animation.

The algorithm will try to move in zigzag if it is the shortest path, but you can solve that by making all gems above a fixed are also fixed while searching.

Or you can search for the nearest normal gem, that doesn't has a fixed gem above it and move it to the empty place that has a fixed gem above it.