récursive + 900 éléments + voisin check = causes stackoverflow

Question

J'ai un jeu de simulation de ville et essaie de trouver un moyen de vérifier le flux de notre système d'alimentation. Les bases: La carte de la ville est basée sur des tuiles (30 par 30 tuiles = 900 tuiles). Maintenant, je commence à une centrale électrique et je fais une vérification de voisin récursive (en haut, à gauche, à droite, en bas) pour vérifier s'il y a quelque chose qui va transporter l'énergie. S'il y a quelque chose, je commence aussi à vérifier ces tuiles pour les voisins. Pour éviter doubles contrôles et/ou des appels récursifs infinis, je remplis un ArrayList avec des tuiles traitées et vérifier si une nouvelle tuile a déjà été traité et ajouté à la liste de tableaux ...

récursive commencé:

public void updatePowerEnvironment(int id, ArrayList<Integer> elements) { 
    Log.w("GT", "update env for id: " + id); 
    int newId = id - GameMap.mMapSize; 
    if (newId >= 0 && GameMap.mMapCells.get(newId).mPowerEnabled 
      && !elements.contains(newId)) { 
     elements.add(newId); 
     updatePowerEnvironment(newId, elements); 
    } 
    newId = id + GameMap.mMapSize; 
    if (newId < GameMap.mMapCells.size() && GameMap.mMapCells.get(newId).mPowerEnabled 
      && !elements.contains(newId)) { 
     elements.add(newId); 
     updatePowerEnvironment(newId, elements); 
    } 
    newId = id - 1; 
    if (newId >= 0 && GameMap.mMapCells.get(newId).mPowerEnabled 
      && !elements.contains(newId)) { 
     elements.add(newId); 
     updatePowerEnvironment(newId, elements); 
    } 
    newId = id + 1; 
    if (newId < GameMap.mMapCells.size() 
      && GameMap.mMapCells.get(newId).mPowerEnabled 
      && !elements.contains(newId)) { 
     elements.add(newId); 
     updatePowerEnvironment(newId, elements); 
    } 
} 

Si je peux faire confiance à la sortie du journal, aucune case n'a été essayée pour être traitée deux fois. Cela signifie que je n'ai pas d'erreurs dans les appels récursifs. Ce qui signifie aussi que la pile est simplement trop petite.

Est-ce que quelqu'un a une idée sur la façon d'éviter la limite de la pile?

[Mise à jour et mon code à la suite de Erics réponse]

public void updatePowerEnvironment(int id, ArrayList<Integer> elements) { 
    Stack<Integer> toProcess = new Stack<Integer>(); 
    toProcess.push(id); 
    int mapSize = GameMap.mMapCells.size(); 
    while (!toProcess.empty()) { 
     id = toProcess.pop(); 
     Log.e("GT", "id to process: " + id); 
     if (elements.contains(id)) { 
      continue; 
     } 
     int[] neighborIds = computeNeighbors(id); 
     for (int neighbor : neighborIds) { 
      if (neighbor < 0 || neighbor >= mapSize) { 
       continue; 
      } 
      if (!GameMap.mMapCells.get(neighbor).mPowerEnabled) { 
       continue; 
      } 
      toProcess.push(neighbor); 
     } 
     elements.add(id); 
    } 
} 

private int[] computeNeighbors(int id) { 
    return new int[] {id + GameMap.mMapSize, id - GameMap.mMapSize, id + 1, id - 1}; 
} 

Answer 1

Si je comprends votre problème correctement vous essayez de calculer la fermeture transitif du « est alimenté par » relation entre deux tuiles. Il est certainement possible de calculer une fermeture transitive de manière non récursive.

Voici un algorithme non récursif qui calcule la fermeture transitive d'une relation en C#. Vous devriez être capable de l'adapter à la langue de votre choix.

http://blogs.msdn.com/b/ericlippert/archive/2010/02/08/making-the-code-read-like-the-spec.aspx

Notez que fondamentalement ce que je fais ici est d'éviter la limite de la pile par allocation ma propre pile sur le tas. Cette chose peut grandir autant que vous voulez. (Si vous n'avez plus de mémoire, alors vous avez de plus gros problèmes!)

Notez également qu'il serait judicieux de choisir une structure de données qui fait le "est un membre de?" prédicat extrêmement bon marché. Une liste de tableau de taille n est généralement O (n) pour répondre à la question "cet élément est-il membre de cette collection?" ce qui signifie que votre algorithme est O (n^2) global. Pouvez-vous utiliser une collection comme un ensemble ou une table de hachage qui a des tests de confinement O (1)?

De plus, sur un niveau purement "qualité de code", cette méthode pourrait nécessiter un travail. Le fait qu'il y ait tant de code dupliqué il y a un drapeau rouge. Je serais enclin à écrire cette méthode comme cette esquisse:

Set<int> PoweredTiles(int powersource) 
{ 
    Set<int> result = an empy set; 
    Stack<int> stack = an empty stack; 
    stack.Push(powersource); 
    while (stack is not empty) 
    { 
     int current = stack.Pop(); 
     if (result.Contains(current)) continue; 
     result.Add(current); 
     int[] neighbours = { compute the neighbours } 
     foreach(int neighbour in neighbours) 
     { 
      if (neighbour is not in range of grid) continue; 
      if (neighbour is not a power carrier) continue; 
      stack.Push(neighbour); 
     } 
    } 
    return result; 
} 

court, au point, non récursive, pas de code dupliqués et O (n).

Answer 2

Vous avez juste besoin de convertir votre implémentation récursive en une implémentation itérative (comme la théorie nous dit est toujours possible).

Par exemple, vous pouvez:

• maintenir une file d'attente de cellules à être vérifiée
• alors que cette file d'attente n'est pas vide, traiter l'élément avant
  • pour traiter une cellule , faites tout ce que vous avez à faire pour la cellule elle-même, puis pour chacun de ses quatre voisins
  • s'ils ne sont pas déjà dans la file d'attente, ajoutez-les à la file d'attente
• répétition jusqu'à ce que la file d'attente est vide

Answer 3

Un algorithme récursif efficace, devrait fonctionner à condition que vous ne videz pas les drapeaux (je suppose que vous configurez simplement des drapeaux si une tuile a le pouvoir ou non) avant de faire la récursion . Quelque chose comme ceci:

void updateCell(position) 
{ 
    for each direction (north, south, east, west) do the following: 
    -- is there a cell there? (test for edges), if not, exit now; 
    -- can it be powered? 
    false: exit now; 
    true: set powered=true, call updateCell(this position); 
} 

void updatePowerGrid(start) 
{ 
    clearPowerFlags(); 
    set powered=true for start; 
    updateCell(start); 
} 

Cela devrait fonctionner assez bien jusqu'à ce que vous utilisiez des tailles de grille vraiment énormes.

Answer 4

Vous pouvez le rendre itératif. Avoir deux listes, une qui garde la trace de l'endroit où vous avez été, et celle qui garde la trace de l'endroit où vous êtes en train de vérifier.

code Psuedo avec votre code:

While(ToBeChecked is not empty) { 
    //Note In python i'd be using a copy of the list so I could edit it without 
    //concequence during the iteration. ie for a in b[:] 
    for each element in ToBeChecked 
     updatePowerEnvironment(...); 
     //Remove element you are checking   
     removeElementFromToBeChecked(...); 
} 

public void updatePowerEnvironment(int id, ArrayList<Integer> elements) { 
    Log.w("GT", "update env for id: " + id); 
    int newId = id - GameMap.mMapSize; 
    if (newId >= 0 && GameMap.mMapCells.get(newId).mPowerEnabled 
      && !elements.contains(newId)) { 
     elements.add(newId); 
     //call addElementToBeChecked instead and I beleive the above already 
     //makes sure it has not already been checked 
     addElementToBeChecked(newId, elements); 
    } 
    newId = id + GameMap.mMapSize; 
    if (newId < GameMap.mMapCells.size() && GameMap.mMapCells.get(newId).mPowerEnabled 
      && !elements.contains(newId)) { 
     elements.add(newId); 
     addElementToBeChecked(newId, elements); 
    } 
    newId = id - 1; 
    if (newId >= 0 && GameMap.mMapCells.get(newId).mPowerEnabled 
      && !elements.contains(newId)) { 
     elements.add(newId); 
     addElementToBeChecked(newId, elements); 
    } 
    newId = id + 1; 
    if (newId < GameMap.mMapCells.size() 
      && GameMap.mMapCells.get(newId).mPowerEnabled 
      && !elements.contains(newId)) { 
     elements.add(newId); 
     addElementToBeChecked(newId, elements); 
    } 
} 

addElementToBeChecked(...) { 
    ToBeChecked.add(); 
    //Some other stuff if needed 
} 
removeElemenToBeChecked(...) { 
    ToBeChecked.remove(); 
    //Some other stuff if needed 
} 

Answer 5

La première chose que je voudrais essayer est juste de changer l'ordre de recherche du Nord-Sud-Ouest-Est à Nord-Est-Sud-Ouest. Comme ceci:

public void updatePowerEnvironment(int id, ArrayList<Integer> elements) { 
    if (!GameMap.ValidCellId(id)) 
     return; 
    if (!GameMap.mMapCells.get(id).mPowerEnabled) 
     return; 
    if (elements.Contains(id)) 
     return; 
    elements.Add(id); 
    updatePowerEnvironment(id - GameMap.mMapSize, elements); 
    updatePowerEnvironment(id + 1, elements); 
    updatePowerEnvironment(id + GameMap.mMapSize, elements); 
    updatePowerEnvironment(id - 1, elements); 
} 

Cela pourrait réduire la profondeur de récursivité, dépendant sur les cartes impliquées.