Matching Algoritm

0 favourites
  • 13 posts
  • Hello! I'm working on a Diamond Dash type matching algorithm. Right now it works 95% of the time, all of the time (lol).

    The idea behind it is simple. Once a game piece is placed, check the game pieces around it, starting at 0 degrees working its way counter clockwise. Once a match is found, check pieces around that game piece. If no matches are found, retrace steps and check pieces that have not been checked.

    Please take a look at it, feel free to use the algorithm and comment any bugs that are rendering it unuseful 5% of the time!

    Thnx!

    https://www.dropbox.com/s/9q0eadso2xvv3 ... .capx?dl=1

    PS: Cannot attach capx to post for some reason...

  • How about this?

    https://copy.com/nVYGNNmNa3zVGOlg

    btw, you exchanging of pieces is flawed, since it is possible to overlap multiple empties.

  • Thanks mindfaQ. I haven't been able to see your capx because i need to download the beta version of C2, but could you please elaborate on how my exchanging of pieces is flawed? It would be a great help for the future!

  • isn't it easier to store every piece in an 2d-array and when its replaced u check its neighbour cells or do I missunderstand it?

  • probably. there are many ways pf going about this. i know of at least 3 ways.

  • When you drop a piece, you check for overlapping empty sprites. Since those have a collision size of 10 x 10 boxes and your game piece a collision box for 42 x 42 pixels, there are places, where your gamepiece overlaps multiple empty sprites. In that case, two or even three of the empty sprites are destroyed and only one is created -> you end up with empty spaces in your grid.

    After your overlapping condition, you could add "pick nearest empty" or (even better) compare two values: distance(gamepiece.x, gamepiece.y, empty.x, empty.y) < gamepiece.width - empty.width * 2

    This way you will end up with only one empty picked, and in the case of the distance expression, you also get some snapping back, when the game piece is in the middle of two empty pieces and when it is not sure if the user wanted the piece to drop on empty 1 or empty 2.

    And here the checking function I would have done (although I would probably input the piece information into an array and iterate over that):

    It's a bit simpler imo, you have a queue of pieces to check (starting with the exchanged piece), this looks at the pieces around it and finds pieces that have not been looked at (queued) before (status = 0); those pieces are added to the queue. When the queue is empty, you've found all adjacent pieces of the same color.

    Of course you can pack these 4 events of looking around into each direction into a for loop, but while it saves space in the event sheet, I don't think it will be faster at execution, since calculations won't get less.

  • thanks man. you're awesome!

  • I added some further explainations.

  • My approach for matching puzzle swap that utilize flood-fill

  • Try Construct 3

    Develop games in your browser. Powerful, performant & highly capable.

    Try Now Construct 3 users don't see these ads
  • thanks man. ill check it out.

  • mindfaQ: your code works great! there's one problem tho. you can easily replicate it. put two pieces of the same color together (only 2) and then do the same for 2 pieces of a different color. the four of them will be counted as a match, and they shouldn't be. i'm trying to fix it, but i'm only making it worse. any help is appreciated!

    i believe i can fix it if i reset all of the pieces' status to 0 after matches are checked. i'll repost if it works.

  • My approach for matching puzzle swap that utilize flood-fill

    alextro

    Just had a look at your code and trying to reverse it. I want the blocks to be destroyed if neighbour blocks are of different colors.

    Example: Instead of 3 red blocks being destroyed on matched, it will be red, purple, blue destroyed on matched. Hope it makes sense.

    I set invert: Animation frame = Self.AnimationFrame but it doesn't seem to work.

  • That would be unusual gameplay, but can be done by counting animation frame. For example red=0, purple=1, blue=2. Say first pick is purple, so we store the animation frame value to variable "pick_color". Then we add 1 for second pick that will equal to 2 which is blue. Third pick will return value 3, so set variable "pick_color" %3 everytick to loop the value back to 0.

    Anyway you may found auto-match interesting:

Jump to:
Active Users
There are 1 visitors browsing this topic (0 users and 1 guests)