映射分支平铺路径

Question

我正在开发一款游戏（并且已经问过几个问题），现在我还有一个问题要问你们。

这个游戏中的关卡格式被设置为Uint16（我使用SDL）的tilemap，它们是tilemapData结构数组中的索引。 tilemapData结构的一个位是isConductive位/布尔值。

该位的使用基本上是创建将各种对象连接成一个“powerNet”的路径。我有以下关于当前方法的一些代码（这工作，但我将介绍为什么我真的很讨厌后话）

void findSetPoweredObjects(unsigned long x, unsigned long y, powerNetInfo * powerNet) { 
    //Look for poweredObjs on this tile and set their powerNet to the given powernet 
    for (int i = 0; i < level->numChunks[CHUNKTYPE_POWEREDDEF]; i++) 
    if (level->poweredObjects[i]->position[0] == x && level->poweredObjects[i]->position[1] == y) 
     level->poweredObjects[i]->powerNet = powerNet, powerNet->objectsInNet++; 
} 

void recursiveCheckTile(bool * isWalked, powerNetInfo * powerNet, unsigned long x, unsigned long y, tilemapData * levelMap) { 
    //If out of bounds, return 
    if (x < 0 || y < 0 || x >= level->mapDimensions[0] || y >= level->mapDimensions[1]) return; 
    //If tile already walked, return 
    if (isWalked[x + (y * level->mapDimensions[0])]) return; 
    //If tile is nonconductive, return 
    if (!(level->tiles[levelMap->map[x + (y * level->mapDimensions[0])]]->flags & TILETYPE_CONDUCTIVE)) return; 

    //Valid tile to check, see if there's a poweredobj on the tile (link it to the net if it is) and check the adjacent tiles. 
    isWalked[x + (y * level->mapDimensions[0])] = true; 

    findSetPoweredObjects(x,y,powerNet); 

    recursiveCheckTile(isWalked, powerNet, x - 1, y, levelMap); 
    recursiveCheckTile(isWalked, powerNet, x + 1, y, levelMap); 
    recursiveCheckTile(isWalked, powerNet, x, y - 1, levelMap); 
    recursiveCheckTile(isWalked, powerNet, x, y + 1, levelMap); 
} 

bool buildPowerNets(void) { 
    //Build the powernets used by the powered objects 
    //TODO: Rewrite buildPowerNets() & recursiveCheckTile() to avoid stack overflows and make it easier to backtrace powernets in-game 
    bool * isWalked; 
    isWalked = new bool[(level->mapDimensions[0] * level->mapDimensions[1])]; 
    unsigned long x, y; 
    tilemapData * levelMap = level->layers[level->activeMap]; 
    for (y = 0; y < level->mapDimensions[1]; y++) { 
    for (x = 0; x < level->mapDimensions[0]; x++) { 
     if (isWalked[x + (y * level->mapDimensions[0])]) continue; 
     isWalked[x + (y * level->mapDimensions[0])] = true; 
     if (level->tiles[levelMap->map[x + (y * level->mapDimensions[0])]]->flags & TILETYPE_CONDUCTIVE) { 
     //it's conductive, find out what it's connected to. 

     //But first, create a new powernet 
     powerNetInfo * powerNet = new powerNetInfo; 
     powerNet->objectsInNet = 0; 
     powerNet->producerId = -1; 
     powerNet->supplyType = POWER_OFF; 
     powerNet->prevSupplyType = POWER_OFF; 
     powerNet->powerFor = 0; 

     //Find adjacent tiles to this one, add them to it's powernet, and then mark them walked. Then repeat until the net is done. 
     recursiveCheckTile(isWalked, powerNet, x, y, levelMap); 
     } 
    } 
    } 
    delete isWalked; 
    for (int i = 0; i < level->numChunks[CHUNKTYPE_POWEREDDEF]; i++) 
     if (level->poweredObjects[i]->powerNet == NULL) return false; 
    return true; 
} 

注意，返回false意味着该函数失败（在这种情况下，没没有正确地链接所有的对象）。

我担心的是，由于堆栈溢出，走过导电图块的功能会在更复杂的贴图上失败。这些功能如何减轻这种风险有什么想法？如果需要，我可以提供更多关于结构的信息。

我想过修改代码，以便recursiveCheckTile只有在它到达交叉点时才进行递归调用，并且只是交互地跟随它的导电路径，否则这似乎只是一个部分解决方案，因为我可以'事先知道如何扭曲或分支路径可能。

如果它有所不同，速度在这里完全不重要，因为这个函数只在使用前处理地图时运行一次，所以使用一点额外时间不会造成伤害。

Answer 1

洪水填补

它看起来像你基本上是做你格的flood fill。您可以通过使用需要检查的队列或一堆方块来消除递归。有关伪代码，请参见Wikipedia文章的"alternate implementations" section。

自己维护队列/堆栈的好处是，当你访问它们时，你将从列表中删除正方形，而在递归解决方案中，即使在访问它们之后，正方形仍然保留在堆栈上。

下面是适合您的问题，维基百科的文章“简单”替代实现：

1. Set Q to the empty queue. 
2. Add node to the end of Q. 
3. While Q is not empty: 
4.  Set n equal to the first element of Q 
5.  Remove first element from Q 
6.  If n has already been visited: 
7.   Go back to step 3. 
8.  Mark n as visited. 
9.  Add the node to the west to the end of Q. 
10. Add the node to the east to the end of Q. 
11. Add the node to the north to the end of Q. 
12. Add the node to the south to the end of Q. 
13. Return. 

注意，您可以使用堆栈或为这个队列，要么将工作。下面是一些凉爽—和迷人—动画示出差异视觉：

基于队列的洪水填充

基于堆栈的洪水填充

连接分量标记

如果您最终在同一个网格上有多个电源网络，您也可能会发现connected component labeling页面很有趣。它基本上可以帮助您确定是否有多个断开的电源网，并且当您这样做时，它会告诉您每个正方形属于哪个网。

Answer 2

您可以反复重写此函数。

想想这样：你隐式地使用调用栈作为你的搜索算法的路径栈。每次您拨打recursiveCheckTile时，您都会将一个节点推入该堆栈。然而，调用堆栈相对较小，所以你很快就会把它吹掉。

您需要明确地管理您的路径堆栈。而不是调用四个相邻节点的递归函数，将节点推入此显式堆栈。你的算法是这样的（伪）：

add starting node to stack 

while(nodes on stack) 
{ 
    pop node 
    if(node is conductive) 
    { 
     add node to powerSet 
     push 4 adjoining nodes onto stack 
    } 
} 

这将产生相同的遍历（深度优先），但你的筹码将是明确的，所以你可以分配的内存gobsmacks它。