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.

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.

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;
}

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.

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.

回答1:

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.

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:

Queue-based flood fill

Stack-based flood fill

Connected-component labeling

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.

回答2:

You can rewrite this function iteratively.

Think of it this way: You're implicitly using the call stack as your path stack for your search algorithm. Each time you call recursiveCheckTile you're pushing a node onto that stack. The call stack is relatively small, however, so you're blowing it out quickly.

You need to manage your path stack explicitly. Instead of making a call to a recursive function for the four adjoining nodes, push a node onto this explicit stack. Your algorithm will look like this (pseudo):

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

This will yield the same traversal (depth-first), but your stack will be explicit so you can allocate gobsmacks of memory for it.