映射分支瓦片路径(Mapping a branching tile path)

我工作的一个游戏（和问几个问题就可以了的话），现在我还有一个问题要问你们的。

在这场比赛中的水平格式设置为标记Uint16的（我使用SDL），这些指数为tilemapData结构数组的tilemap的。 一项所述的结构体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只能使一个递归调用，当它到达一个结，只是interatively遵循它。否则的传导路径，但似乎仍然只能解决部分问题，因为我不能提前知道的时间如何扭曲或分支的路径可能是。

如果它的确与众不同，速度完全是不重要的位置，因为该功能只运行一次，如果地图正在被使用之前处理，因此使用一些额外的时间将不会受到伤害。

Answer 1:

洪水填充

它看起来像你基本上是做一个颜色填充你的网格。 您可以通过使用队列或需要被检查方格一叠消除递归。 参见“可替换实施方式”部分的维基百科文章为伪代码。

保持队列的优点/堆栈自己的是，你会从列表中为您访问它们，而在递归解决方案的平方保持您曾经访问过他们甚至在堆栈中删除正方形。

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

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.

请注意，您可以使用堆栈或为这个队列，要么将工作。 这里是显示在视觉上的差别一些很酷的和迷人的动画：

基于队列的颜色填充

基于堆栈的洪水填充

连接分量标记

您也可以找到连接组件标签页有趣的，如果你曾经最终不得不在同一网格多个电源网。 基本上，它可以帮助你计算出，如果你有多个断开电源网络，当你这样做它会告诉你每平方米属于哪一种。

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它。

文章来源: Mapping a branching tile path