映射一个分支瓦路 [英] Mapping a branching tile path

问题描述

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

I'm working on a game (and have asked a couple questions on it already), and now I have another question to ask of you guys.

在这场比赛中的级别的格式设置为标记Uint16的（我使用SDL），这些指标为tilemapData结构的数组的tilemap的。其中一个tilemapData结构的位是isConductive位/布尔值。

The level format in this game is set up as a tilemap of Uint16's (I'm using SDL) which are indices into an array of tilemapData structs. One of the bits of the tilemapData struct is the isConductive bit/boolean.

该位的用途基本上是创建一个连接各种物件组合成一个单一的路径的PowerNet。我有下面的一些code对当前的方法（这工作，但我将介绍为什么我真的很讨厌它之后）

The use of this bit is basically to create paths that connect various objects together into a single "powerNet." I've got some code below on the current method (which works, but I'll cover why I really hate it after)

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意味着函数失败（在此情况下，它没有正确链接的所有对象）。

Note that returning false means that the function failed (in this case, it didn't properly link all of the objects).

我担心的是，该功能走路导电地砖将平了失败，更复杂的地图，因为的堆栈溢出。有哪些想法，如何缓解这些功能的这种风险？我可以提供，如果它需要使用的结构的详细信息。

My worry is that the function to walk the conductive tiles will flat-out fail on more complex maps because of a stack overflow. What are some ideas for how to mitigate this risk with these functions? I can provide more info on the structs used if it's needed.

我想过修改code，使 recursiveCheckTile 不仅使当它达到一个结，只是interatively遵循的传导路径是对否则递归调用，但似乎仍然只能解决部分问题，因为我不能提前知道的时候怎么扭曲或分支的路径可能是。

I've thought of modifying the code so that recursiveCheckTile only makes a recursive call when it reaches a junction and just interatively follows the conductive path it's on otherwise, but that still seems to be only a partial solution since I can't know ahead of time how twisted or branching the path might be.

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

If it makes a difference, speed is entirely unimportant here, since this function only runs once when the map is being processed before being used, and so using a little extra time won't hurt.

推荐答案

它看起来像你基本上是做你的网格的颜色填充。可以通过采用一队列或堆栈需要检查的平方消除递归。见伪$维基百科的文章的替代实现一节 C $℃。

Flood fill

It looks like you're basically doing a flood fill of your grid. You can eliminate the recursion by employing a queue or a stack of squares that need to be checked. See the "alternate implementations" section of the Wikipedia article for pseudo-code.

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

The advantage of maintaining the queue/stack yourself is that you will remove squares from the list as you visit them, whereas in the recursive solution the squares remain on the stack even after you have visited them.

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

Here's the "simple" alternative implementation from the Wikipedia article adapted to your problem:

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.

请注意，您可以使用一个堆栈或在此队列中，无论是将工作。这里有一些很酷＆mdash;和迷人的＆mdash;动画显示在视觉上的区别：

Note that you can use a stack or a queue for this, either will work. Here are some cool—and mesmerizing—animations showing the difference visually:

您也可以找到连通区域标记页有趣的，如果你永远结束不得不在同一个电网多电源网络。基本上，它可以帮助你计算出，如果你有多个断开电源网络，当你做它会告诉你哪一个每平方米所属。

You may also find the connected component labeling page interesting if you ever end up having multiple power nets on the same grid. It basically helps you figure out if you have multiple disconnected power nets, and when you do it tells you which one each square belongs to.

这篇关于映射一个分支瓦路的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！