Puzzle Bubble SDL游戏（级联算法）

Question

我正在用 SDL 制作一款类似泡泡谜题的游戏，我被困在当泡泡卡在空中且没有可见连接时泡泡会掉落的机制上。这是我的意思的一个例子。当我破坏橙色泡泡时，其他泡泡都会掉落。

网格（2D 向量）中的所有气泡都有一个结构来确定它们的连接：

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

你会如何解决这个问题？我的头脑告诉我使用递归，但我并没有真正的经验。我将不胜感激任何伪代码或任何可能有帮助的东西

Answer 1

如果你不需要邻居是单独的变量，那么使用某种容器会更容易：

std::list<Bobble*> neighbours;

或

std::vector<Bobble*> neighbours;

使用后一个选项，您可以通过元素索引轻松访问每个邻居：

// 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];

现在您可以轻松地遍历元素（无论您选择使用哪个容器）：

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

在循环内部，正如您已经猜到的那样，您需要递归地进入每个元素：

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
       // ...
    }
}

第一次循环后，如果最终遇到橙色泡泡，可能会残留一些未标记为已连接的泡泡，因为您在找到橙色泡泡之前就进入了它们，结果发现它们是死胡同，并且您不会在第一个循环中对他们 return。

这就是为什么应该有第二个递归循环来标记那些剩余的循环。但是这个应该很容易弄清楚，所以我把它留作练习（提示：在第二个循环中，你不需要进入已经标记为已连接的气泡 - 这会加快速度）。

Puzzle Bubble SDL游戏（级联算法）

Puzzle Bubble SDL game (cascade algorithm)

c++

algorithm

sdl

game-engine