Detect shapes in match-3

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.

are you making the tokens or is the user or what

Take a look at rexrainbows matcher plugin, it's probably the easiest way to go.

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.

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.

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.

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.

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.

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.

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.

xoros - thank you for the example. I'll give it a shot.

rexrainbow - I tried using your slg movement plugin, but I don't understand it at all and I haven't been able to figure out how to get it to work for me in my game. I'm actually working on 2 versions of my game; 1 with your plugins and 1 without. Whenever I get stuck, I switch to the other project to see if I can figure it out and then switch back to the other one. ...if that makes sense. lol

iwontnamemyself

What conditions in your case for picking?

iwontnamemyself

xoros

Here is a sample which will show the order of flood fill for picking the same color. Follow the logical position of checking tiles log in console.