Algorithme PathFinding: comment gérer efficacement les changements de poids

Question

J'ai donc un algorithme de pathfinding simple qui précalcule la route la plus courte vers plusieurs endpoints cibles, chacun ayant un poids différent. Cela équivaut à peu près à avoir un point de terminaison avec un noeud entre lui et chaque point de terminaison, bien que les bords aient des poids différents. L'algorithme qu'il utilise est un simple algorithme d'étalement, qui 1d regarde ce ce (| signifie mur, - signifie l'espace):

• 5 - - - 3 | - - - 2 - - - - 2
• 5 4 - - 3 | - - - 2 - - - - 2 : Handled distance 5 nodes
• 5 4 3 - 3 | - - - 2 - - - - 2 : Handled distance 4 nodes
• 5 4 3 2 3 | - - - 2 - - - - 2 : Handled distance 3 nodes
• 5 4 3 2 3 | - - 1 2 1 - - 1 2 : Handled distance 2 nodes
• Done. Any remaining rooms are unreachable.

Ainsi, supposons que j'ai une solution de pathfinding précalculée comme celui-ci, où seul le 5 est une cible:

- - - - | 5 4 3 2 1 -

Si je change le mur dans une pièce. Recomputing est simple. Réagissez simplement tous les nœuds de distance (mais ignorez ceux qui existent déjà). Cependant, je ne suis pas en mesure de trouver un moyen efficace de gérer ce qu'il faut faire si le 4 est devenu un mur. Il est clair que le résultat est le suivant:

- - - - | 5 | - - - -

Cependant, dans une solution 2d Je ne sais pas comment traiter efficacement avec 4. Il est facilement possible de stocker que 4 dépend de 5 et doit donc recaculation, mais comment puis-je déterminer sa nouvelle dépendance et ses valeurs en toute sécurité? Je préfère éviter de recalculer l'ensemble du tableau. Une solution, qui vaut mieux que rien, consiste à (grossièrement) recalculer uniquement les éléments du tableau avec une distance Manhattan de 5 par rapport à la valeur 5, et de conserver les informations source. Cela signifierait fondamentalement réappliquer l'algorithme à une zone sélectionnée Mais puis-je faire mieux?

Answer 1

Hmmm. Une solution que j'ai trouvé est la suivante: Gardez une liste des nœuds qui sont accessibles le plus rapidement à partir de chaque nœud. Si un nœud devient un mur, vérifiez le nœud auquel il était accessible et récupérez la liste correspondante. Revérifiez ensuite tous ces nœuds en utilisant l'algorithme standard. Lorsque vous atteignez un nœud dont la nouvelle distance est plus petite, notez-la comme nécessitant un nouveau test.

Prenez tous les voisins des nœuds marqués qui ne sont pas marqués et réappliquez l'algorithme sur eux, en ignorant tous les nœuds marqués que cette technique touche. Si l'algorithme réappliqué augmente la valeur d'un nœud marqué, utilisez la nouvelle valeur.