Mappare un percorso di piastrelle ramificazione

Question

Sto lavorando su un gioco (e ho chiesto un paio di domande su di esso già), e ora ho un'altra domanda da chiedere a voi ragazzi.

Il formato di livello in questo gioco si configura come un tilemap di di Uint16 (sto usando SDL), che sono gli indici in un array di struct tilemapData. Uno dei bit della struct tilemapData è il isConductive bit / booleano.

L'uso di questo bit è sostanzialmente quella di creare percorsi che collegano i vari oggetti in un unico "PowerNet." Ho un po 'di codice di seguito il metodo corrente (che funziona, ma mi occuperò perché io odio davvero dopo)

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

Si noti che il ritorno falso significa che la funzione non è riuscita (in questo caso, non ha correttamente collegare tutti gli oggetti).

La mia preoccupazione è che la funzione di camminare per le piastrelle conduttive saranno flat-out non riuscire sulle mappe più complesse a causa di un overflow dello stack. Quali sono alcune idee su come mitigare questo rischio con queste funzioni? Posso fornire più informazioni sulle struct utilizzati se è necessario.

ho pensato di modificare il codice in modo che recursiveCheckTile fa solo una chiamata ricorsiva quando raggiunge un incrocio e proprio interatively segue il percorso conduttivo è su altrimenti, ma che sembra ancora essere solo una soluzione parziale in quanto non posso sapere in anticipo come contorto o diramazione del percorso potrebbe essere.

Se si fa la differenza, la velocità è del tutto irrilevante qui, dal momento che questa funzione viene eseguito solo una volta quando la mappa è in fase di elaborazione prima di essere utilizzato, e quindi con un po 'di tempo in più non farà male.

Answer 1

riempimento Flood

Sembra che tu sei fondamentalmente facendo un riempimento alluvione della griglia. È possibile eliminare la ricorsione impiegando una coda o una pila di quadrati che devono essere controllati. Vedere la "implementazioni alternative" sezione di questo articolo di Wikipedia per pseudo-codice.

Il vantaggio di mantenere la coda / pila te è che potrete eliminare le piazze dalla lista come li si visita, mentre nella soluzione ricorsiva le piazze rimangono sullo stack, anche dopo averli hanno visitato.

Ecco il "semplice" implementazione alternativa alle voci di Wikipedia adatta al vostro problema:

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.

Si noti che è possibile utilizzare una pila o di una coda per questo, sia funzionerà. Ecco alcuni-animazioni affascinanti fresche e che mostrano la differenza visivamente:

fill inondazioni basata su code

fill inondazioni stack-based

etichettamento di componenti connesse

Si possono anche trovare le componente collegato pagina etichettatura interessante se mai finisce per avere più reti elettriche sulla stessa griglia. Aiuta fondamentalmente a capire se si dispone di più reti di alimentazione scollegato, e quando lo fai ti dice quale ogni quadrato appartiene.

Answer 2

È possibile riscrivere questa funzione in modo iterativo.

Pensare in questo modo: Stai implicitamente utilizzando lo stack di chiamate, come il vostro stack percorso per il vostro algoritmo di ricerca. Ogni volta che si chiama recursiveCheckTile si sta spingendo un nodo su quella pila. Lo stack di chiamate è relativamente piccolo, tuttavia, in modo che stai soffiando fuori rapidamente.

È necessario gestire il tuo stack percorso in modo esplicito. Invece di fare una chiamata a una funzione ricorsiva per i quattro nodi adiacenti, spingere un nodo su questo stack esplicito. Il vostro algoritmo simile a questa (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
    }
}

Questo produrrà lo stesso attraversamento (in profondità), ma il vostro stack sarà esplicita in modo da poter allocare gobsmacks di memoria per esso.