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

Sorry for the late. The release date for the Match 3 Game as stated last time might be delayed a bit.

HORRAY! The Match 3 Pop Saga is now available in the Google Play Store Now!

After several weeks of hard work, i have finally come out with a 'sample' of the Match 3 Game, with the Candy Crush Saga as the main reference, and the algorithms stated previously. (The "Saga" is imitated to gain some SEO points, hopefully... oops)

However, different from the Candy Crush, my Match 3 Pop Saga only has a total of 9 stages. Furthermore, it includes a bit of RPG elements: Level up. Basically, the more you play (popping more balloons), the higher levels you are. And the higher levels will reward you a higher score per pop (and time too!). Interesting huh? :)

Note that it is a balloon, not a colorful Easter egg.
I am not a graphic designer. The pictures are obtained from devianart.

Something to note is that, the 'striped candy' now is a glowing balloon (right, simple animation), while the 'wrapped candy' is something like this (bordered):

The maximum level in the Match 3 Pop Saga is 15 (which i think you won't need that for completing all the stages with 3 stars).

Finally, thanks for trying this game. Feel free to drop some feedback, either on the game flow, or the game experiences~

Match 3 Game Algorithm Part 5 - Miscellaneous (Special Combinations)

By following the algorithms stated here, I believe you almost get the ideas of how a Match 3 game would look like in terms of logic. A little naive (as i didn't use any built in library or framework, or referring to the popular flood fill algorithm). But since it is from scratch, it has the flexibility of any customization. Furthermore, based on those solid understanding, you would be able to add more variations in your game.

Performance-wise, as long as you have followed the statements strictly, we could ensure a decent working solution. (I will demo a working one in the future post)

In this post, particularly, i would like to recap a number of features on the Candy Crush Saga that make the Match 3 game much more interesting - Special Candy Combinations, as stated below:

a) Color Bomb - formed by a match involving 5 candies in a uni-direction

b) Striped Candy - formed by a match involving 4 candies in a uni-direction

c) Wrapped Candy - formed by a match involving 5 candies in a "T", "+" or "L" shape.


Technically speaking, to detect these special candy combinations, it isn't that hard since we could make some checking in the results of the matching detection algorithm.

For example, in the picture above, after the node of 35^th is exchanged with the 43^rd, we would obtain a match of 5 nodes (33^rd, 34^th, 35^th, 36^th and 37^th) according to the 1st statement.

However, the problem does not just end here. Since we are going to 'generate' the special 'candy' (item) ourselves, you might further pose some questions:

Q1: How to determine at where does the special candy reside?
Q2: How to enable those special effects formed by the special candies matches?

To answer the Q1, you would need to take some efforts remembering the index of the nodes touched by the player. If it takes place through random falling, you may take the smallest index of the matches to be the index of the special candy.

In the case of Q2, on the other hand, it is likely more complicated that we have to look into the special combinations one by one.

Consider the nodes exchange of Color Bomb:
a) 1 Color Bomb with 1 normal node
    Effect: All the nodes which are identical to the normal node will explode.
b) 1 Color Bomb with 1 Color Bomb
    Effect: All the nodes in the matrix explode.
c) 1 Color Bomb with 1 Striped Candy
    Effect: All the nodes having the same color become stripped candies and explode.
d) 1 Color Bomb with 1 Wrapped Candy
    Effect: All the nodes having the same color explode. And then, all the nodes with a random color explode.

Apart from that, we have to consider the exchange of Striped candy and Wrapped candy:
a) 1 Striped Candy with 1 Striped Candy
   Effect: Both Striped Candies explode
b) 1 Striped Candy with 1 Wrapped Candy
   Effect: Both candies explode, along with 3x3 matrix crossing both horizontally and vertically
c) 1 Wrapped Candy with 1 Wrapped Candy
   Effect: Both candies explode, along with 5x5 matrix surrounding both candies.

No pseudo-code? I believe with the basic algorithms in the previous posts, you would be able to construct the logic here. In case you really want, please leave a message here and i would update this :)

Note:
In my Match 3 game, i don't care about the orientation of the striped candy. Instead, i randomly explode either a horizontal or a vertical line.

Next: A real Android Match 3 Game Demo

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

Until now, we manage to come out with a fundamental match 3 game with the matches detection and a deadlock detection. So far so good :)

But the thing is, something is still missing: user interaction. This is the crucial part that lets the players get hooked on the game. The players are required to make some moves to proceed with the games, either through forming more matches, or completing some special missions. (In the case of the candy crush, the missions are forming matches to clear the jelly, or achieving a threshold score with minimum moves, and etc)

Here, the basic user interaction tutorial would be: move the nodes/items, either horizontally or vertically.

At first sight, this is pretty straightforward. In fact, since the each node/item in my match 3 game is coupled with an integer index, it isn't hard to make a rule such that, if the first node touched is a neighbor of the second, both the nodes are exchangeable, and hence we could perform some matching detection algorithm.

For example, the picture shows a matrix of 8x8. At the nodes indexed at 10^th, 17^th, 18^th, 19^th and 26^th, it is easily observed that, the node of 18^th can be only exchanged with its neighbor which has the absolute index difference of 1 or 8. With this understanding, we could conveniently generalize the algorithm...

However, let's consider 1 more case:

Here, the node indexed 15^th, despite being able to exchange with the node 7^th, 14^th, 23^rd, it is unable to interact with the node 16^th (because they are not directly connected). Therefore, this special case has to be addressed in our algorithm, which is stated in the next statement:

Statement 4:
- Two nodes are exchangeable, provided that their absolute index difference is 1 or 8, AND if one of them is in the column 0^th or 7^th, the other one is NOT in the column 7^th or 0^th.

Forgive my poor explanation in the last part. It simply means that, the node in the column 0^th cannot be exchanged with the one in the column 7^th.

Coming up next: Miscellaneous (Special Combinations)

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.