Match 3 Game algorithm Part 3 - How to determine whether there is no more match?

From the previous post, we learnt that to detect if there is a match in the match 3 game matrix, we could scan the nodes 1 by 1, each with the vertical and the horizontal direction.

Then, it must be natural to think that, if to do the opposite: "How to determine whether there is no more match?", we could simply apply the same concept, couldn't we?

To some extent, it is true that we could perform the similar technique. However, we haven't really defined the problem yet. Precisely, the puzzle to be solved is: "How to check whether there is no match, EVEN THOUGH after the players have made all the possible moves?" In other word, a match 3 game deadlock, in which the game couldn't proceed due to no more possible match.

There we go, with the condition added, the problem is way more troublesome than expected, and that's the reason i separated this topic.

Before the start of the algorithm, it would be better to have a look at some scenarios:

The picture shows a matrix with an extreme case such that, if the node of 35^th and 36^th (horizontal exchange) is exchanged, it could lead to the most matches (Here, let's just consider a match of 3 nodes only):
a) node 19^th - vertical black
b) node 20^th - vertical red
c) node 27^th - vertical black
d) node 28^th - vertical red
e) node 33^rd - horizontal black
f) node 35^th - vertical black
g) node 36^th - vertical red, and horizontal red

With this understanding, it enlightens us on another statement:

Statement 2:
- For a horizontal exchange node of (n^th) and (n+1)^th, a matching detection algorithm is necessarily to be executed on the nodes:
a)  (n-2*8)^th vertical
b)  (n+1 - 2*8)^th vertical
c)  (n-8)^th vertical
d) (n+1 - 8)^th vertical
e) (n-2)^th horizontal
f) (n)^th vertical
g) (n+1)^th vertical, horizontal

Similarly, this applies to the vertical nodes exchange as well:

 The picture shows that, if the node 35^th is exchanged with the node 43^th, it will trigger the matches:
a) node 19^th - vertical black
b) node 33^rd - horizontal black
c) node 34^th - horizontal black
d) node 35^th - horizontal black
e) node 41^st - horizontal red
f) node 42^nd - horizontal red
g) node 43^rd - horizontal red, vertical red

Hence, not surprisingly, we have our 3^rd statement:

Statement 3:
- For a vertical exchange node of (n^th) and (n+8)^th, a matching detection algorithm is necessarily to be executed on the nodes:
a)  (n-2*8)^th vertical
b)  (n-2)^th horizontal
c)  (n-1)^th horizontal
d) (n)^th horizontal
e) (n-2 + 8)^th horizontal
f) (n-1 + 8)^th vertical
g) (n + 8)^th vertical, horizontal

Cool. Now we can apply the algorithm based on the statements. Here's the pseudo-code:

- foreach node n^th
 manually exchange the node with (n+1)^th, perform matching detection algorithm, 
 manually exchange the node with (n+8)^th, perform matching detection algorithm.
 

 The pseudo code is as brief as possible. The thing to point out is that, although each could be exchanged in 4 directions (up, down, left, right), we only consider "right", and "down" while scanning each node. Again, this systematic checking avoids redundancy effectively.

There are several situations in which you could deploy the algorithm:
a) At the initial stage - when the game starts, you could check if the matrix encounters a deadlock or not
b) After the player have made a move - to check if the interaction is effective or not
c) After the items regenerated and have fallen down - to check if the fallen items would form some matches or not.

Coming up next: How to enable the user interaction?