Forum :: Game Development :: Match 3+ algorithm?

I am creating a game simular to candy crash and I  looking for  best way to search for matching blocks.
So far I have looked into right hand fill/scanline fill ,flood fill/seed fill. Flood fill seems like the best method for doing this type of search that I have found although I am thinking about adapting the A* algorithm to return matching nodes as if they were paths.

Any thoughts?

Flood fill seems most appropriate. I don't think A* is as appropriate, it would be a more interesting type of thing to do for fun.

Are you going to be making it open source? I would be interested to see what you come up with for it

---
class EOSERV {
Programmer | Oldbie
Open source EO Client: https://github.com/ethanmoffat/EndlessClient
};

Yeah I can I think it will be fun for people to mess with.

I am assuming you are giving each object in a class a type or (color) value as well as a pair of coordinates. I would check with a loop each time any coordinates changed due to falling. Scanning the whole grid seems like a lot of unnecessary math.

This can also be done easily with a recursive function. Have an empty array to store matching blocks. In the function, check the neighbours that aren't already in the array, if they match add them to the list then recursively call the function again for that neighbour. 

Well, there are a few other things to do but you get the idea =P

 

---
http://sordie.co.uk
http://twitter.com/@SordieEO

Apollo posted: (1st Feb 2016, 02:06 pm)

I am assuming you are giving each object in a class a type or (color) value as well as a pair of coordinates. I would check with a loop each time any coordinates changed due to falling. Scanning the whole grid seems like a lot of unnecessary math.

Yes each block is assigned an x,y and type when created this is how I am creating the blocks

enum BloxType
{
    BlueSQ = 0,
    GreenC = 1,
    RedD = 2,
    YellowS = 3,
    PurpleO = 4,
    BlackS = 5,
    GreyT = 6,
    BlueST = 7,
    NotUsed1 = 8,
    NotUsed2 = 9,
    NotUsed3 = 10,
    GreyWall = 11,
    PurpleD = 12,
    Bomb = 13,
    BlueD = 14,
    BlackWall = 15
};

struct Blox : public Shared
{
    unsigned char speed;
    BloxType type;// is based of position in the bitmap to keep it simple type * 64
    unsigned char x,y;
    bool moving;
    double timer;
    bool placed;
    Blox(unsigned char speed_,Type type_) : speed(speed_),type(type_),moving(false),timer(Timer::GetTime()),placed(false) {}
};

I store the blocks in a vector in my world class and create the grid like this.

bool new_blox(World *world)
{
  
   for(int x = 0; x < 12;++x)//12 wide
   {
       for(int y = 0; y < 12; ++y)//12 high
       {
           if(world->blox.size() >= 144) continue;

            Blox *nb = create_blox(world);
            nb->x = x;
            nb->y = y;
            world->blox.push_back(nb);
        }
    }
}

Blox *create_blox(World *world)
{
    return new Blox(1,static_cast<Type>(util::rand(0,Type::BlackWall)));
}

@Sordie I will test the  recursive method that you mentioned it seems very simplified and easy to controll.

insomniac posted: (2nd Feb 2016, 01:11 am)

@Sordie I will test the  recursive method that you mentioned it seems very simplified and easy to controll.

I don't think I explained it very well =P Umm.. have some pseudo code:

array list_of_blocks
array neighbours = ((1, 0), (0, 1), (-1, 0), (0, -1))

check_function(x, y)  {
  i for each neighbours {
    nx = x + neighbours(i, 0)
    ny = y + neighbours(i, 1)

    if block(nx, ny) = block(x, y) {
      if (nx, ny) not in list_of_blocks {
        list_of_blocks.add(nx, ny)
        check_function(nx, ny)
      }
    }
  }
}

// Now clear list_of_blocks call check_function(x, y) for any block that 
// has changed. After it returns list_of_blocks will contain a list of all 
// the blocks of the same type that are attached. You can also expand the
// neighbours array to include double 1's (1,1),(-1,1),(1,-1),(-1,-1) and
// it will also work diagonally

---
http://sordie.co.uk
http://twitter.com/@SordieEO

I slapped a couple functions together based of your example concept. Still using the util file from an old EOSERV :D! The basic concept is working anyway heres the functions adapted to my project so I didnt have to change much code.

PtrVector<Blox> check_neighbours(World *world,Blox *blox)
{
    PtrVector<Blox> tmpblox;
    //tmpblox.push_back(blox);

    UTIL_PTR_VECTOR_FOREACH(world->blox,Blox,wb)
    {
        if((wb->x == blox->x) && (wb->y == blox->y-1 || wb->y == blox->y +1 || blox->y == wb->y-1 || blox->y == wb->y +1))
        {
            if(wb->type == blox->type)
            tmpblox.push_back(*wb);
        }

        if((wb->y == blox->y) && (wb->x == blox->x-1 || wb->x == blox->x +1 || blox->x == wb->x-1 || blox->x == wb->x +1))
        {
            if(wb->type == blox->type)
            tmpblox.push_back(*wb);
        }

    }
    return tmpblox;
}

void sordie_check(World * world,Blox *blox)
{
    PtrVector<Blox> tmpblox;
    PtrVector<Blox> swapblox;
    PtrVector<Blox> holdblox;


    holdblox = check_neighbours(world,blox);
   // holdblox.push_back(blox);

    UTIL_PTR_VECTOR_FOREACH(holdblox,Blox,tb)
    {
        swapblox = check_neighbours(world,*tb);

        UTIL_PTR_VECTOR_FOREACH(swapblox,Blox,sb)
        {
            tmpblox.push_back(*sb);
        }
    }

    tmpblox.push_back(blox);
    Console::Out(util::to_string((signed)tmpblox.size()));

    if(tmpblox.size() >= 3)
    {
        UTIL_PTR_VECTOR_FOREACH(world->blox,Blox,wb)
        {
            UTIL_PTR_VECTOR_FOREACH(tmpblox,Blox,sb)
            {
                if(*wb == *sb)
                {
                    world->blox.erase(wb); // removing the element here is whats fucking up the function I think ??
                }
            }
        }
    }
}

The size returns correctly but when it comes to deleting the matching blox sometimes it doesnt remove all. I am trying to isolate the cause ??
Here is a couple screen shots So far I am just drawing the map/blox and trying to destroy 3 or more consecutive blox when they are clicked.

Fresh board:




Board after I clicked x 8, y 5 notice x 9, y 5??:


Last example I clicked x 10, y 0 notice x 10,y 1:

You are deleting an element of a container that you are using for comparison before all elements are compared. Try just flagging each object as inactive, then use a separate loop thru all objects that will delete inactive or "matched" tiles.

FOREACH(tiles, tile)

{ if (neighbor->type == tile->type) tile->inactive = true;}

FOREACH(tiles, tile)

{ if (tile->inactive) delete tile;}

*this is just a shorthand example not to be confused with real macros or code, also doesn't consider match of 3 but you get the idea.

I would recommend using range-based for loops and smart pointers instead of #define macros and raw pointers, they make life a lot easier and the syntax is a lot prettier for the loops than UTIL_PTR_VECTOR_FOREACH (plus #define macros don't play very nicely with the debugger)

With smart pointers you'll probably want std::shared_ptr so you don't have to worry about uniqueness and move semantics.

---
class EOSERV {
Programmer | Oldbie
Open source EO Client: https://github.com/ethanmoffat/EndlessClient
};

@ Apollo Thank you I did'nt realize I was destroying the container but I knew thats were the code was failing. I guess I expected a crash its weird how the container stayed intact I guess thats where undesired behavior comes into play :D. I tried assigning another variable and that worked but I ended up just using a goto anyway so I'm currently not using blox->(bool).

if(tmpblox.size() >= 3)
    {
        fuck_you: //restart scan if necessary
        holdblox = tmpblox;//tmpcontainer preventing undesired behavior

        UTIL_PTR_VECTOR_FOREACH(holdblox,Blox,tb)
        {
            UTIL_PTR_VECTOR_FOREACH(world->blox,Blox,wb)
            {
                if(*tb && *wb && wb->x == tb->x && wb->y == tb->y)
                {
                    swapblox = check_neighbours(world,*wb); //get all residual neighbors

                    UTIL_PTR_VECTOR_FOREACH(swapblox,Blox,sb)
                    {
                        tmpblox.push_back(*sb);
                    }

                    swapblox1.push_back(*wb);//storage to compare cords when dropping new blox
                    world->blox.erase(wb);
                    goto fuck_you;
                }
            }
        }

        UTIL_PTR_VECTOR_FOREACH(swapblox1,Blox,sb1)
        {
            int x = sb1->x;
            int y = sb1->y;
            for(int yy = y+1; yy > 0;--yy)
            fill_blox(world,x,yy);// currently not functiong 100%
        }
    }

;// currently not functiong 100%

void fill_blox(World *world,int x,int y)
{
    PtrVector<Blox> tmpblox;
    UTIL_PTR_VECTOR_FOREACH(world->blox,Blox,wb)
    {
        Blox *blox = 0;

        if(wb->x == x && wb->y == y -1)
        {
            blox =  create_blox(world);
            blox->x = wb->x;
            blox->y = wb->y;
            tmpblox.push_back(blox);

            wb->y = y;
        }

    }
    UTIL_PTR_VECTOR_FOREACH(tmpblox,Blox,tb)
    {
        world->blox.push_back(*tb);
    }
}

@ Ethanmoffat: I will probally maybe convert them at some point but for convenience I'm going to stick with predefined macros I'm just trying to blow through the code and dont feel like rewriting all the functions at this point.