0

我对此有一个可行的解决方案，尽管我相信必须有一个更好的实现。简而言之，问题是这样的：

我正在开发一个 connect>=3，宝石风格的益智游戏。当“板”的状态发生变化时，我将所有部分分组，以便如果它们水平或垂直“连接”，它们共享一个 ID。这就是我目前的做法：

[伪]

for all( array object* )
{
    if !in_a_group() check_neighbours( this )
}

void check_neighbours( ID )
{
    if ( check_is_same_type( left ) )
    { 
        if !in_a_group() this.ID = ID ; check_neighbours( ID )
        else if( in_a_group ) change_IDs(this.ID, ID ) 
    }
    same for right ...
    up ...
    down ...     
}

那是我所做的一个非常肮脏的伪版本。我递归调用 check_neighbours，将第一个分支的 ID 向前传递（我使用这个指针作为 ID，而不是生成一个）。

如果我发现一个连接的具有不同 ID 的片段，我会用新 ID 覆盖具有该 ID 的所有片段（我在这里有一个 ASSERT 因为它实际上不应该发生。到目前为止还没有进行大量测试）

除非该作品没有 ID，否则我不会在原始分支检查_neighbours。

这工作得很好，虽然我的伪可能缺少一些小逻辑。我的问题是它有可能使用许多分支（这可能是我正在处理的硬件的问题）。我已经在这个问题上工作了很长时间，以至于我看不到另一个解决方案。有没有感觉到你错过了一些非常明显的东西？

我也是stackoverflow的新手，对编程相当陌生，任何关于礼仪等的建议都值得赞赏。

4

1 回答 1

0

你会如何建议避免递归？

据我了解，您的算法基本上是一个带有小扭曲的“洪水填充”。

无论如何，为了避免递归，您需要分配数组来存储未处理项目的坐标并使用队列或先进先出。因为您知道网格的尺寸（并且因为它是宝石风格的（？）游戏，所以您应该能够在几乎任何地方预先分配它。

任何洪水填充类型递归算法的伪代码。

struct Coord{
    int x, y;
}

typedef std::queue<Coord> CoordQueue;

bool validCoord(Coord coord){
    return (coord.x >= 0) && (coord.y >= 0) 
        && (coord.x < boardSizeX) && (coord.y < boardSizeY);
}

bool mustProcessCoord(Coord coord);

void processAll(){
     CoordQueue coordQueue;
     Coord startPoint = Coord(0, 0);
     coordQueue.pushBack(startPoint);

     while (!coordQueue.empty()){
         const Coord &curCoord = coordQueue.front();
         //do something with current coordinates.
         processCoord(curCoord);

         const int numOffsets = 4;
         const int offsets[numOffsets][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
         for (int offsetIndex = 0; offsetIndex < numOffsets; offsetIndex++){
              Coord neighborCoord = Coord(curCoord.x + offsets[offsetIndex][0],
                    curCoord.y + offsets[offsetIndex][1]); 
              if (!isValidCoord(neighborCoord) || !mustProcessCoord(neighborCoord))
                  continue;
              coordQueue.push_back(neighborCoord);
         }

         coordQueue.pop_front();
     }
}

看 ？没有递归，只是一个循环。几乎任何递归函数都可以展开成类似的东西。

如果您的底层平台受到限制并且您没有 std::queue，请改用数组（实现为数组的环形缓冲区可以像 fifo 队列一样工作）。因为你知道板子的大小，你可以预先计算数组的大小。其余的应该很容易。

于 2013-04-02T13:27:11.787 回答