Having trouble with match-3 colored blocks on grid (like bejewled). Greedy algorithm, so close but not working

Development Programming & Scripting Blueprint
, , ,
1

Hello, I’m trying to figure out how a match-3 type of game like columns, bejeweled, etc…

I have a dynamically generated grid which is also included in a matrix. I can traverse left or right, up or down. The problem is that I have no idea how to go left+up, left+down, right+up, right+down, etc… So that it snakes around for all matching colors.

There is an old project called unrealmatch3 but unfortunately i can’t open it’s C++ files to see how they did it. The youtube video doesn’t really go over how that part works but explains how everything is laid out instead.

I have done a lot of googling and can’t figure out the specifics and what turned out to be a fun weekend project ended up irritating my little brain. I know I have to do this recursively but trying to make this work in BP is a pain.

So if I have a macro of Scan left, Scan Right, Scan Up, Scan down which adds the discovered location of the same-colored neighboring block, how do I keep doing it recursively using what it has discovered? This sounds like a simple algorithm problem that is taught in school but I never been so I’m trying to understand. Sorry for the dumb question.

I provided an image to help illustrate what I’m trying to achieve

connect 3 example
connect 3 example1265×662 131 KB

Edit note: Changed title to make it more legible.

2

Create a set of tiles-found. This could be a set-of-coordinate, or a set-of-tile-object.
Create a list of tiles-to-visit.
Run a function that looks something like:

Set<Coord> VisitAllTiles(Coord start, Map<Coord, Tile> const &board) {
    List<Coord> ToVisit;
    Set<Coord> Found;
    Color toMatch = board[start].Color;
    ToVisit.Add(start);
    Found.Add(start);
    while (!ToVisit.Empty()) {
        Coord next = ToVisit.PopFront();
        if (!board.Contains(next)) {
            continue; // outside bounds
        }
        if (board[next].Color != toMatch) {
            continue; // wrong color
        }
        if (Found.Contains(next)) {
            continue; // already got this one
        }
        // win! found new connected tile of right color
        Found.Add(next);
        // remember to visit all the neighbors
        ToVisit.Add(LeftOne(next));
        ToVisit.Add(RightOne(next));
        ToVisit.Add(UpOne(next));
        ToVisit.Add(DownOne(next));
    }
    return Found;
}

This will traverse all neighbors and check whether they have the right color, and finally return the set of all connected cells that have the same color. You can then figure out what to do with that – are there enough of them; do you remove/explode them; and so on.

Note that I used generic container names for List, Set and Map as well as the Coord and Tile data structures – this illustrates the breadth-first search algorithm, and you can transliterate it to Unreal C++ with TMap<> and friends if you want, or Blueprint, or whatever else you need.

3

Thank you for your detailed response! I had quite the long day and will have to give what you said a go tomorrow probably. I hardly can keep my eyes open :stuck_out_tongue:

I don’t know C++ but it seems similar enough to javascript or PHP. I’m not sure what (Coord) means but i’m guessing it’s just the coordinate variable and for the other is a split variable where Map is coordinate and the tile as it would appear in the blueprint.

Again, super tired, will look into it in more detail tomorrow thanks again!

Edit: Using arrow brackets will make text disappear in the post apparently