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?

Match 3 Game algorithm Part 2 - How to detect there is a match?

With the game element terminology, we are ready to jump into the core of the game - Matches detection. It is the most fundamental yet critical puzzle.

So, the question: Provided a matrix of 8x8 consisting of random items, how to detect if there is a match?

And here comes the 1^st statement (from androidgamify blogspot :) )

Statement 1:
- Every match (vertical or horizontal) is detected at the node located at the smallest n^th of tile.

What does that mean?

For example, the picture below shows a matrix with a number of matches. (Assume that you design your match-3 game in such a way that there could be matches at the initial stage)

From the observation, there is a horizontal match of the green nodes located at the tile 8^th, 9^th and 10^th, and a vertical match of the blue nodes located at the tile 35^th, 43^th, 51^th. (Just focus on these two first).

Based on the statement, while scanning the matrix nodes 1 by 1, the green match has to be detected at the 8^th, while the blue match is to be detected at the 35^th. With this systematic checking, we can effectively avoid redundancy.

Hence, generally speaking we can deduce the matching algorithm as below:
To detect the vertical matching, we only need to scan the nodes which are from the row 0^th to 5^th.

And to detect the horizontal matching, the nodes to be scanned are from the column 0^th to 5^th.

These make sense, considering the fact that only at the green nodes we are able to detect the matching of the specified orientation.

Here's the pseudo-code:
a) Vertical matching

- foreach node n^th
  if it is at more than 5^th row, skip
  else check if n^th equal to (n+8)^th, (n+2*8)^th, (n+3*8)^th, (n+4*8)^th to determine how many nodes in  the matching.

b) Horizontal matching

- foreach node n^th
  if it is at more than 5^th column, skip
  else check if n^th equal to (n+1)^th, (n+2)^th, (n+3)^th, (n+4)^th to determine how many nodes in  the matching.

Coming up next: How to detect if there is no more match?

Match 3 Game algorithm Part 1 - Game elements terminology and analogy

Generally, a Match 3 Game consists of a matrix of nodes with the dimension M x N. Here i prefer a square one (M x M), specifically 8 x 8.

Terminology:
a) Tile: The location at which the 'node' resides. In a matrix of M x M, each tile is representable by a number from 0 to (M x M - 1), at i^th row and j^th column.
b) Node: The item of the matching. In the Candy Crush Saga, it is analogous to the candy.
c) Matches: The matching of 3 to 5 nodes, could be horizontal or vertical, but not diagonal.

* To conveniently setup the Match 3 Game, I use colors as the type to differentiate the nodes. Similar to the tile number, i will start counting my row and column from 0 to (M-1).

For example, the picture shows a matrix of 8 x 8 - consisting of 64 tiles.
 The crossed tile:
a) resides at 1^st row, 1^st column. OR
b) belongs to the 9^th tile.

Apart from that, there are a number of matches observed. For example, a matches of 5 blue squares at 33^th, 34^th, 35^th, 36^th, 37^th tiles.

Coming up next: How to detect a match?

How to create a match 3 Android Game like Candy Crush Saga?

As mentioned before, the Candy Crush Saga, with the basic concept of the Match 3 game, stands out to be an extraordinarily successful game.

Then, instinctively, you will ask yourselves, "Can I become similarly successful if i make another Match 3 game?" And the most importantly, what is the basic algorithm behind the Match 3 game that powers the Candy Crush Saga? By understanding and constructing those skeletons, you may design your own attractive graphics, sound effects, and animations to package your game.

To your delight, for the next couple of blog posts, the contents will touch about the algorithm of the Match 3 game. Curiosity makes me learn to create this kind of game as well :) . After some research from the search engines, I came out with my own solution (ok, + reference) which I wish you can find it useful for your basic understanding.

No fuzzy codes. It is mainly about the algorithm, with intuitive picture description and lines of pseudo-code.

To summarize, I break down the Match 3 Game algorithm into several parts:

a) Match 3 Game algorithm Part 1 - Game elements terminology and analogy

- A quick understanding of how I define the game elements. It will help a lot before you read the others.

b) Match 3 Game algorithm Part 2 - How to detect if there is a match?

- Basically it is the core part of the game. No third-party framework or library. Everything is from scratch.

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

- An important checking to see whether the game can proceed or not.

d) Match 3 Game algorithm Part 4 - How to enable the user interaction?

- There are a number of approaches. Here I simply use the index difference, with an exception handling.

e) Match 3 Game algorithm Part 5 - Miscellaneous (Special Combinations)

- Include some interesting parts which make the game more impressive and fun.

f) Match 3 Game algorithm Part 6 - A real Android Match 3 Game demo

- The whole tutorial is not convincing without a real game demo. However, the graphics are not emphasized. Yay! It is now in the Google Play Store - Match 3 Pop Saga

Kindly drop a feedback if you find any typo.

Gentle reminder: This is truly an original and a useful blog

"To err is human, to forgive divine".
Wait, what if the culprit is a robot? or precisely, the blog crawlers?

Last Sunday night, on a routine surfing of my "Android Gamify" blogspot to plan which topic should come next, all of a sudden, i was returned with a horrifying message:

"Blog has been removed"

Flabbergasted, my mind turned blank for seconds before gaining consciousness.

"What?" "Why?"

These are the questions flashing through my mind. Immediately, i logged into my email, realizing that my blogspot has been marked as "SPAM" by the automation system.

This is hilarious. The blog is my personal diary of my Android Games development. Every single article is originally written and proofread. How does the system define it as "SPAM"?

Without a second thought, I made an appeal, while praying everything will be restored. Unlike other services, blogger doesn't offer a Live chat. I really wished to have an immediate face to face session arguing, discussing, clarifying, convincing, or whatever action to recover my posts. That night, was a completely sleepless night...

On the next day, i kept checking emails and entering the blog again. Only in the afternoon I found that the entire blog site has been restored. And the blogger staff admitted that it was a MISTAKE.

Heaving a sigh of relief, I told myself that, to prevent such a disaster in the future, it is so crucial for us to consistently "backup" our posts (which is actually a feature available  in the blogger). I almost lost the motivation to continue blogging, until i found that it came alive again.

And i hope you can learn from this lesson as well.