Detect shapes in match-3

Get help using Construct 2

Post » Thu Jun 27, 2013 11:51 am

Hi guys,

so, the question is how to detect typical shapes like "T", "L", "+" etc. in a match three game. Right now I'm using a flood fill algorithm for finding all connected tokens of the same colour (scaling up an invisible sprite, checking the neighbors, moving to the next neighbor of the same colour). I think, I have to filter the result of a flood fill some how.
B
45
S
11
G
4
Posts: 515
Reputation: 7,389

Post » Thu Jun 27, 2013 1:46 pm

are you making the tokens or is the user or what
B
40
S
11
G
7
Posts: 514
Reputation: 9,626

Post » Thu Jun 27, 2013 3:05 pm

Take a look at rexrainbows matcher plugin, it's probably the easiest way to go.
B
24
S
9
G
7
Posts: 756
Reputation: 7,292

Post » Thu Jun 27, 2013 3:08 pm

I'll try to explain again:

Let's take Bejeweled as an example. When you swap gems in Bejeweled, tokens of the same colour are getting matched (destroyed) if they are positioned in a certain shapes, like a row of three, four, "T", "L","+" shapes. Detecting a row of tokens is not a problem, but how to detect more complex shapes?

This plugin is using a board plugin for detecting shapes, which will not work in my project. xoros2013-06-27 15:10:50
B
45
S
11
G
4
Posts: 515
Reputation: 7,389

Post » Thu Jun 27, 2013 3:39 pm

Well, first of all, let's try not to test all the grid all the time. If your gameplay is based on switching 2 tiles (like most match 3 are), you should "just" test those 2 for shapes. In 2 steps then, first detect all the same color tiles, then detect if the current group makes a shape.

1/ detect all the same tiles, it depends how you store your grid. I'll suppose you have an 3 dimensional array for it (X,Y for the grid, Z for the tile type/color). Best way to detect every tile would then be a recursive function, selecting currentTile, flaging it with a Boolean (so it's not re-analysed), and comparing its color to the 4 adjacent tiles. Run the function on every detected tile then, and collect an array of (tileX,tileY) during this function.
You should then have something like this (let's say we detect a L shape) :
[(5,5),(6,5),(5,4),(5,3)]

2/ detecting the shape from the tile array returned
First of all, find Xmin and Ymin in the array, and then substract it to every couple, so you have something like this for the current example :
[(0,2),(1,2),(0,1),(0,0)]
Next thing is a function that tests if a matrix contains an certain shape. A shape is described by another matrix, just like the previous one. The test is done by comparing if every couple of the shape is also set in the matrix to test. If the matrix to test is bigger than the shape matrix, you will have to test it multiple times with all the offsets possibles so all the matrix is tested.
Don't go rotate the matrix or anything to test all the possible L orientations, just call again this test function with other shapes representing the L shape in multiple orientations.

Repeat the 2/ with all the shapes you want to test, and you should be done.

This seems really... heavy to code in C2. I personally would use a plugin for this if I did it.
B
17
S
8
G
4
Posts: 461
Reputation: 6,097

Post » Thu Jun 27, 2013 3:53 pm

@Guizmus - thanks for your suggestion. Actually I don't use any arrays for storing tokens. Instead I use an invisible sprite for all the calculations - it calculates much faster and is more flexible, than using arrays. For example a standard "flood fill" algorithm is done on while loop by scaling an invisible sprite up and moving it through all neighbor tiles of the same colour and marking them. So the first step is done.

May be detecting a shape should work similar to the invisible sprite approach, like there's an invisible cross-shape (which contains all the possible shapes) and I move it through all the connected tokens and check what tokens are overlapping.
B
45
S
11
G
4
Posts: 515
Reputation: 7,389

Post » Thu Jun 27, 2013 4:03 pm

@xoros
Invisible sprite is a nice way too, you are right. More C2 friendly. A little less CPU friendly maybe, as the arrays in V8 are really fast.

Though, the invisible sprite is a lot easier to manipulate, to rotate for multiple shape test for example.
If, like you suggest, you create a "test Sprite" for each shape you want to test, and move it/rotate it everywhere possible within the flood generated shape, and test if the test shape is included in the flood shape at every step, you should be good too.
Only difficulties are :
- testing ALL possibilities. You'll have to use the basic tile size to minimize the possibilities.
- testing if all of the testing shape is included in a minimum of events, because this test can be done a lot of times in a row...
For simple shapes, other algorithm can be used, maybe more CPU friendly, but I don't see another method for testing any imaginable shape you want to create.
B
17
S
8
G
4
Posts: 461
Reputation: 6,097

Post » Wed Oct 22, 2014 1:20 am

@xoros - How did you implement your "flood fill" algorithm? I'm working on a match 3 (ish) game that has the potential of having some pretty big matches ( >10) and haven't been able to figure out how to get the match part working. I can find a match on a single row or column, but like you, I need to be able to search in all directions for each match.
B
10
S
1
Posts: 67
Reputation: 909

Post » Wed Oct 22, 2014 8:56 am

@iwontnamemyself - you can do it with recursive function, by checking neighbors of the same color. I made an example capx for you:
https://www.dropbox.com/s/b1i42zwtl4qfh76/floodfill.capx?dl=0

But detecting custom shapes and doing other match3 magic like collapsing etc is a bit more complicated, may be you can use board series of plugins by rexrainbow.
B
45
S
11
G
4
Posts: 515
Reputation: 7,389

Post » Wed Oct 22, 2014 9:08 am

@xoros

You could use rex_slg_movement plugin for flood fill, if you are using my board system.
Here is a sample, which I made for @iwontnamemyself before.
B
107
S
25
G
242
Posts: 4,387
Reputation: 136,966

Next

Return to How do I....?

Who is online

Users browsing this forum: Ajbael, DolyGamesCosmos, lukezero, RoaringPixels, Solomon and 9 guests