Swap things and match recognition

#1 @Isaac, there is a Memory Card tutorial, which would most likely be close to a '3 match' concept -- unless your doing a 'gem' style match -- This tutorial is on the TGB TDN Pages


In either event, a quick and dirty explanation is this --

You have presumably a number of items on the screen

The end-user clicks an item to start a match ... (memory match concept)
OR
The end-user interacts with the screen in some manner, which starts a 'match search' (gem concept)

You then perform your generic match code, starting with either the interacted item (memory) or from the top of the grid (gem) and follow through checking all possible directions --


If you have

****O***
***O****
**O*****

You would check the first "*"
Part of this check would include "peeking" at the "*" to the right, as well as the one below it, and to the right of the one below it (all 3 possible directions for this "*")

If any of them are the same as the current one being checked, you perform a "match check" on them as well, in the same manner as your performing the match check on the "current" --

You store a reference to the current, and to the one that matches it, and then continue to store references to additional matches -- given the following:

O***
*O**
**O*
****

You would find the "O" in the top-left, then check the "*" to the right, and the "*" below it, then the "O" to the right of the "*" below it -- you store a reference to the current "O" (top-left) and then to the second "O", and then when you perform your check to find the third "O" your game logic will tell it what possible directions it can look in -- in a simple "3 in a row" concept, you would require the third match to exist in the same direction as the second, so you would pass a parameter to the "checkMatch" function telling it the only valid match for the current match reference is in the "SW" direction -- if a match is found, and your logic for a match consists of "3 or more", then you flag the reference set as "match" and then look at the fourth row to determine if the next row down, "SW" direction, is a match, if so ... keep matching so you "grab them all", if not "complete match" (perform what ever logic you do -- in a gem game for example, the match removes the 'gems' and then does the search all over again to see if that match affected the screen and created more matches)


Hope that helps -- if not, be more specific with your reply

#2 Thanks David, that helps. I will try the memory tutorial before ask anything else ;)

#3 Unfortunately that tutorial is outdated. I have to study other updated stuff before try to understand outdated stuff :(

#4 @Isaac -- if you ask more target specific questions, you'll probably get more specific answers --

#5 @David -- I want to learn how to program a three match just like in a gem style game. I believe that is something that's very hard to learn or make for people that doesn't have a team, at least for me, that's why a tutorial on the matter will be great. But I guess that I'm asking too much because there is a lot of things to do before try to accomplish that... so I go to the docs and forum threads. ;)

#6 Hi David, forgive me if some of this is obvious, but in reading through your matching logic for a gem-type match search I had a couple of questions.

In terms of 'construction' would you make the game board (grid) an array of some sort, a tilemap or something else?

Would you necessarily need to search the entire screen for matches, or would you limit it somehow?

Thanks, I find this a very interesting concept that could be used in lots of ways.

- Don

#7 For the general logic, you have a number of ways to approach the matter -- you can create your tiles and apply 'customData' to them, such as that all tiles that 'match' have the same customData -- as TorqueScript is type-less and numbers and words are treated as the same thing, I do not think that using numeric values would increase search performance, but it's always best to assume numerics are faster unless you know otherwise.

As for the search ... in a game like Bejewelled, you would search the entire grid, over and over, and over again until you ran out of matches -- every tile has to be searched, and the search should (depending on game logic, and visual appeal) start from scratch each time a match is completed --

I believe the general 'logic' for bejeweled follows this, where say you have the following:

ABCD
ACCC
ABDD
BCDD

You would first find the 'A' (top-left) match (two tiles below), remove them, then replace them with new tiles -- we'll assume the new tiles do not cause any additional matches, k?

Now, we find the 'CCC' match in the second row ... we remove them, move all the tiles above down one row, then fill the missing tiles (assume again, no additional matches are generated by the new tiles)

This will then create a new match, causing 'DDD' (bottom right) ... and we then remove those tiles, move the rest down, then replace them --

For a game with bejewel's basic 'logic', we would scan the tile-layer repeatedly, until we stop finding matches ...

You can 'pause' general gameplay (user interactions) by setting some sort of a 'search in progress' flag, that is checked for at the start of the tilelayer::onMouseDown event (or whatever triggers your user-interaction for the tile-map)

Storing the data in the tile-layer allows for an 'easy to code' search to take place, but may not necessarily be the best approach for performance, especially if your scanning over hundreds of things (in the case of bejeweled, I think it's like what ... 30-60 gems on screen at a time? Thats not too bad ... scanning and replacing 20 matches can be done in the blink of an eye -- without special 'match' animations, of course)

If your looking for a performance boost, it'd be best to store a reference to your tiles custom-data in an array (you can make it multidimensional if you want, or just do some fun math)

For example, if you have a "grid" that is 8x8

ABCDEFGH
HGFDSABV
AVBGFDSS
ABCDFGEH
ABCDFGEH
ABCDFGEH
ABCDFGEH

You could store the 64 tiles 'customdata' in a single dimension array:

$tiles[0] = "A";
$tiles[1] = "B";
...
$tiles[63] = "H";

You could then determine matches quickly with the following math:

Tile 0,0 = 0
Tile 0,1 = 1
Tile 1,0 = 8
Tile 2,0 = 16
Tile 3,3 = 26

To find the next row, just add 8 to the current row --

Here's a coded example:

%tile = %this.pickTile(%worldPosition); // returns "4 5";
%x = getWord(%tile, 0);
%y = getWord(%tile, 1);
%idx = %x * 8 + %y - 1;

Now -- in the example grid above, all 8 columns in the last 4 rows create a '4-part match'

Given that our 'match' search algorithm is at 4,0 (5th row, 1st column == "A")

We know that checking 'above' is useless, since if a match from 'above' were made, it would have been caught by an earlier iteration of our 'search' algorithm, so we simply have to look in the next possible directions -- (using bejeweled logic here)

%x = 4;
%y = 0;
%idx = ((%x * 8) + %y) - 1;
if($tiles[%idx] $= $tiles[%idx + 1]) match(%idx, 1);
else if($tiles[%idx] $= $tiles[%idx + 8]) match(%idx, 8);

Now, this assumes we have a function called "match()" which takes two-parameters, the "start tile" and "offset tile" that match -- this "match" function would then have some logic, and would be able to determine by using the difference of %startTile and %offsetIdx, like so;

function match(%startTile, %offsetIdx)
{
  if($tiles[%startTile] $= $tiles[%startTile + (%offsetIdx * 2)])
  {
    // special 'found a 3-way match' logic goes here
  }
  else
  {
    return false;
  }
}

Now -- this is by no means a "Tutorial" on how to do matching games -- and it's not even really a thorough explaination of how to find a match -- but this should definately give you both a good starting point --

Oh and, remember one thing, I love testing new games ... *hint hint*

Zoul Creations - Owner
Gear Worx Productions - Coder, Scripter, Etc

#8 Wow -- ok ... haha, I didn't realize I wrote that much, haha ... I posted that on my website, zoulcreations.com for later use -- might turn it into a TDN Article at some point ...

#9 Wow David! That explanation is very neat! Thanks, I will explore with this :)

#10 @Isaac, thanks -- hope it was clear enough

#11 @ David: not clear enough for me -I have been working with TGB since last late december- but is a good point to understand better. A very good point because I was forgotting the arrays!

#12 @Isaac -- feel free to ask questions, If I am to turn it into a TDN Article, I need to make sure it makes absolute sense ... hehe ;)

#13 LOL - I have that 'problem' with my posts on occasion, too!

I agree with Isaac, the explanation definitely makes the logic clearer and points out a lot of nuances - such as finishing checking a 'chain' before moving on.

Along those lines, I imagine it would make sense to have a mechanism for flagging a tile as checked with each scan pass, so that you don't repeat the scan when you get to the next row.

Of course, if you had a flag for whether or not the tile has changed due to a match, new piece or player input, then maybe you could speed things up by only checking changed tiles. I.e. a full scan when the board is first set and then only scan what changes.

Fun stuff - this motivates me to wrap some thigns up so I can move on to this!

Thanks again, David!

#14 Hey :)

A TDN Article/Tutorial would be AWESOME for all those people that just like me, are more hobbyst than true developers...

AWESOME!

Thanks David ;)

Sorry, that was not a question:

Fisrt question -and sorry if it sounds stupid-:

What can I set up an array to work with this three match logic?

#15 @Don, there is no use for a 'checked' flag, as tiles will be checked numerous times, to validate them as matches to other tiles -- as the match algorithm is linear (0-64) you'll never check a tile more then it has to be checked -- unless you repeat the loop due to a match being found, at which point, all your tiles have to be re-validated

However, I think I see your logic in the 'flag' -- if a match is found, and new tiles are introduced, only perform a 'match check' on the newly created tiles, then continue your search from that point on -- this could easily be done by having two-arrays ... or perhaps an array, and a list -- in your "addNewTile()" method you could add the tiles "index" to a global list (multi-word string) and then also record somewhere the location of the match you just created -- then only validate the tiles in the list, then start your search from the last match tile + 1 --

So ... if you had:

ABCD
AABB
ABCC

And "AAA" created a match (first row), you'd record the "last tile" as being "0", and add "0 5 9 13" to the list -- you'd then check "0 5 9 13", then continue your linear search starting at "1" again --- and yes, I know, this is a bad example, because it's fairly recursive, haha --

In this case, you would wind-up checking 5, 9 and 13 over again -- unless they were flagged as "searched" already -- however, due to the nature of TorqueScript and how it's handled internally -- this search concept would not really provide any additional performance.

If your working with a small set of tiles, say for example less-then 100 -- you would almost certainly not find any noticeable performance gain by doing this, and may wind up complicating your code and making it hard to maintain for future upgrades.

Also, I'd like to note -- in the concept of Bejeweled, if you have:

AAAB
ABCD
ABED
ADBE

You actually have two-matches that 'should' (according to the game logic), be triggered at once -- One is the "AAA" on the top row, and the other is the "AAAA" down the left-column --

The previously mentioned linear search, would find the first "AAA", then replace it ... and you would then be left with another "AAA" at that point, in the event the tile at 0,0 is not an "A" after being replaced --

This would mess up the point system, as 4-gem matches are worth more -- to by-pass this, you could extend your linear search concept a bit, and allow it to work "for you" in this matter -- finding the first "AAA" match, then ... create a new linear search, and have it focus on the three-tiles it contains -- to search out additional matches -- lots of added work is involved in doing this --

Oh and ... back to the "flag" and "search from last tile" concept, in the event your replacing all the tiles -- and your linear search only looks "forward", you would really have to start from 0,0 again ... or make your search have the ability to "look back" --

Hope this doesn't add to any confusion, ;)

#16 @Isaac -- your question didn't make any sense, sorry -- can you rephrase it ? :)

#17 @David: Sorry for that!

I have to go now. I will bother you later with a true focused question ;)

I'm sending now my feedback on DynoMemory...

Good night

#18 @Isaac, oh -- thanks -- it's just something I whipped together in a couple hours for my son, but I was thinking of releasing it as a public "free" game -- and am looking for input as to the UI, Game Play, etc -- and, the lack of score tracking was intentionally, and is already on my todo-list for the public release (I don't like keeping score with my kids, cause they get upset when they lose -- but others seem to want it, so it's gonna be added as an 'option' -- disabled by default)

#19 Hrm -- well, someone msg'd me on AIM about my "approach" and how it is too complicated -- I just want to summarize real quick, the methods I explained here are by no means "my own", and they were literally pulled out of thin air when I read the thread --

I might also add, each game has it's own logic, and that logic should in turn drive the methodology in which you search for your "matches", the person who msg'd me made the following comment:

Quote:
Anonymous: As with any programming project, there are numerous ways to do anything, but I think you're making it a tad too complex :)
Anonymous: it becomes much easier to digest if you simply check for all the horizontal matches, then check for all the vertical matches
Anonymous: then do something with your "queue" of matches
Anonymous: I took your approach when I started my match 3 game a few weeks back, and quickly discovered the difficulty in implementation

I took there screenname out, cause I assume they'd of posted here if they wanted to be public about it --

Either way -- he makes a good point, but the point is only valid for "some" searches, and not all --

Either way, my method explains a more complex system, this may be "true", but it also explains a bit more then just "how to search for matches" ... hope there's a lesson in there somewhere ... enjoy.

#20 @David: It is in fact a complicated approach, however it is also a robust approach in my opinion in the sense that it might allow you to play with your match rules a bit more. The thing that comes to mind with the other suggested approach is the possibility of taking some tiles out of play due to being in a set unless you have a check in for that.

Of course, now that I've typed it, perhaps doubling up is what you'd want in your rules. I.e. in the most current example you have a 3 across and 4 down - is that 2 matches or one large match?

I could see two ways beyond what you mentioned, and each is ultimately a design choice. One thought is a regular 3 match (horizontal) and then a 'bonus' 4 match (vertical); the other thought would be a 'bonus' 4 match with a modifier for having a total of 6 tiles.

(As I was about to hit 'submit' another variation came to mind - you could also only ever take the single longest chain. That might make for an interesting twist, too.)

RE: a 'checked' flag for tiles. That's a good point, I can see where it could start to cause headaches with toggling the flag and when to validate, etc. As you point out, unless the field is huge it shouldn't be to terrible to scan the whole thing.

Finally, I suppose you could arrange the scripts so that each scanning method builds on itself. If a horizontal scan hits 2 tiles together, it immediately starts a vertical scan from those tiles.

Well, at any rate, I won't know what approach is best for my project until I start scripting, and I can't do that until I finish up some other stuff. =) Until then, let the theories and coffee flow!