Displaying the path of branching tiles

Question

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

The level format in this game is configured as Uint16 tilemap (I use SDL), which are indexes into an array of tilemapData structures. One of the bits of the tilemapData structure is isConductive bit / boolean.

Using this bit is mainly for creating paths that connect different objects together into one "PowerNet" network. I have the code below on the current method (which works, but I will explain why I really hate it)

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 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 conductive, find out what it 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 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 incorrectly bound all objects).

My concern is that the passage function of the conductive plates will fail on more complex cards due. What are some ideas on how to reduce this risk with these features? I can provide additional information about the structures used, if necessary.

I thought about changing the code so that recursiveCheckTile makes a recursive call only when it reaches the connection, and just leads a sequential path otherwise, but this still seems to be only a partial solution, as I may not know in advance how can be twisted or branching path.

If it matters, the speed here is completely unimportant, since this function works only once, when the card is processed before its use, and therefore using a little extra time will not hurt.

Answer 1

Flood filling

It looks like you're basically doing a fill fill on your grid. You can eliminate recursion by using a queue or a stack of squares to check. See the “Alternative Implementations” section of the Wikipedia article for pseudocode.

The advantage of saving the queue / stack is that you remove the squares from the list as you visit them, while in the recursive solution, the squares remain on the stack even after you visit them.

Here's a “simple” alternative implementation from a 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. 

Please note that you can use the stack or queue for this, or it will work. Here are some interesting animations showing the difference visually:

Queue Based Filling

Stack based threading

Marking connected components

You can also find a related component with labeling if you ever render multiple network networks on the same grid. This basically helps you understand if you have several disconnected network networks, and when you do this, it tells you which square each belongs to.

Answer 2

You can rewrite this function iteratively.

Think of it this way: you implicitly use the call stack as the stack stack for your search algorithm. Each time you call recursiveCheckTile , you push node to this stack. However, the call stack is relatively small, so you quickly pop it.

You need to manage the path stack explicitly. Instead of making a recursive function call for four neighboring nodes, push node to 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 lead to the same bypass (first in depth), but your stack will be explicit so that you can allocate gobsmacks of memory for it.