Algorithme de recherche de trajectoire avec obstacles "dépendant de la direction"?

Question

J'ai rencontré le problème suivant. Je programmais un jeu et j'utiliserai un algorithme de pathfinding pour déterminer comment créer des tunnels pour un labyrinthe de salle et de tunnel. Mais j'ai besoin d'un algorithme qui va trouver des chemins à travers des parcours d'obstacles dans lesquels la direction d'approche est pertinente. C'est à dire. un chemin passant horizontalement à travers un obstacle peut être OK, tandis que celui qui passe verticalement peut ne pas l'être.

Un exemple schématisée:

. = free space 
X = path 
| = vertical-blocking obstacle 
a = start point 
b = end point 

Si nous avons

..... 
a.|.b 
..... 

alors nous devrions obtenir un chemin comme

..... 
XXXXX 
..... 

Mais si nous avons

..a.. 
..|.. 
..b.. 

alors nous devrions obtenir un chemin comme

..XX. 
..|X. 
..XX. 

Quel genre d'algorithme ferait cela? Est-ce que "A *" peut être modifié pour faire cela? Un * résoudra le problème sans modification

Answer 1

Vous envisagez de trouver un chemin sur une grille, mais (au moins dans discrete work spaces) ce problème est équivalent à la planification sur un graphique. Par conséquent, si vous pouvez convertir votre grille en un graphique approprié, toute recherche de graphique complète permettra de résoudre ce problème, et toute recherche de graphique optimale donnera les plans que vous avez demandés (ou des chemins de coût équivalent).

Le défi devient alors de formuler le graphique à partir de la grille. Un graphique non orienté de la grille que vous avez fournie ci-dessus ressemblera à quelque chose comme: