Search code examples
c++algorithmsdlgame-engine

Puzzle Bubble SDL game (cascade algorithm)

I am making a puzzle bubble-like game in SDL and I am stuck on the mechanic that makes the bubbles fall when they get stuck in the air with no visible connections. Here is an example of what I mean. When I destroy the orange bubbles, all the others would fall.

Example

All the bubbles in the grid (2D vector) have a struct that determines their connections:

struct Neighbours
{
    Bobble* TopRight{ nullptr };
    Bobble* Right{ nullptr };
    Bobble* BottomRight{ nullptr };
    Bobble* TopLeft{ nullptr };
    Bobble* Left{ nullptr };
    Bobble* BottomLeft{ nullptr };
};

How would you tackle this problem? My head is telling me to use recursion, but I am not really experienced with that. I would appreciate any pseudocode or anything that might help

Solution

  • If you don't need the neighbours to be separate variables, it would be really easier to use some sort of a container instead:

    std::list<Bobble*> neighbours;

    or

    std::vector<Bobble*> neighbours;

    With the latter option you can acecss each neighbour easily by element index:

    // the last enum element may be useful, or may not be
enum { TopRight, Right, BottomRight, TopLeft, Left, BottomLeft, NumElements };

// ...

// init the vector with neighbours

// ...

// access top-left
neighbours[TopLeft];

    Now you can easily iterate over the elements (whichever container you chose to use):

    for(Bobble* b : neighbours) {
   // do stuff...
}

    Inside the loop, as you already guessed, you need to recursively go into each element:

    void searchForOrange(Bobble* b, bool callerConnected)
{
    // this ensures we won't have an infinite loop
    b->setVisited(true);
    // mark b as connected if we know that the previous bubble is connected;
    // this ensures that after we find an orange, all the following
    // bubbles we go into, will also get marked as connected
    b->markAsConnected(callerConnected);

    for(Bobble* n : b->neighbours) {
        if(n != nullptr and not n->wasVisited()) {
           // check if n is an orange
           if(n->isOrange()) {
               // mark as connected to orange
               b->markAsConnected(true);
           } else {
               searchForOrange(n, b->isConnected());
               // if the path through n lead to an orange
               // then mark b as also connected; 
               // this ensures that all the bubbles in the direct backward
               // path get marked as connected
               if(n->isConnected()) {
                   b->markAsConnected(true);
               }
           }
        }
    }
   if(b->isConnected()) {
       // TODO: second loop that will, on the way back,
       //       iterate over all bubbles that were visited,
       //       but not yet marked as connected
       // ...
    }
}

    After the first loop, if an orange bubble was eventually encountered, there may remain some bubbles that are not marked as connected, because you went into them before finding the orange one, and they turned out to be a dead end, and you don't return to them in the first loop.

    That's why there should be a second recursive loop that will mark those remaining ones as well. But this one should be easy to figure out, so I'm leaving it as an excersise (hint: in the second loop, you don't need to go into bubbles that are already marked as connected - this will speed thigns up).