A * recherche de chemin de maillage de navigation

J'ai donc créé ce jeu java 2D descendant dans ce cadre appelé Greenfoot et j'ai travaillé sur l'IA pour les gars que vous allez combattre. Je veux qu'ils puissent se déplacer dans le monde de manière réaliste, alors j'ai vite réalisé, entre autres choses, que j'aurais besoin d'une sorte de guide.

J'ai réalisé deux prototypes A *. L'un est basé sur une grille , puis j'en ai créé un qui fonctionne avec des points de cheminement, alors maintenant je dois trouver un moyen de passer d'une "carte" 2d des obstacles / bâtiments à un graphique de nœuds à partir duquel je peux faire un chemin. Le cheminement réel semble bien, juste mes listes ouvertes et fermées pourraient utiliser une structure de données plus efficace, mais j'y reviendrai si et quand j'en ai besoin.

J'ai l'intention d'utiliser un maillage de navigation pour toutes les raisons exposées dans cet article sur ai-blog.net . Cependant, le problème que j'ai rencontré est que ce que pense A * est le chemin le plus court à partir des centres / bords du polygone n'est pas nécessairement le chemin le plus court si vous voyagez à travers une partie du nœud. Pour avoir une meilleure idée, vous pouvez voir la question que j'ai posée sur stackoverflow .

J'ai obtenu une bonne réponse concernant un graphique de visibilité. Depuis, j'ai acheté le livre ( Computational Geometry: Algorithms and Applications ) et j'ai approfondi le sujet, mais je suis toujours en faveur d'un maillage de navigation (voir " Managing Complexity " dans les notes d' Amit sur Path-Finding ). (En remarque, je pourrais peut-être utiliser Theta * pour convertir plusieurs points de cheminement en une seule ligne droite si le premier et le dernier ne sont pas masqués. Ou chaque fois que je reviens en arrière, vérifiez avant le dernier point de cheminement pour voir si je peux aller directement de que pour cela)

Donc, fondamentalement, ce que je veux, c'est un maillage de navigation où une fois que je l' aurai mis à travers un algorithme d'entonnoir (par exemple, celui de Digesting Duck ), j'obtiendrai le vrai chemin le plus court, plutôt que d'en obtenir un qui est le chemin le plus court suivant nœud à nœud uniquement, mais pas le plus court étant donné que vous pouvez parcourir certains polygones et ignorer les nœuds / bords.

Oh et je veux aussi savoir comment vous proposez de stocker les informations concernant les polygones. Pour l'exemple de prototype de waypoint que j'ai fait, je viens d'avoir chaque nœud en tant qu'objet et de stocker une liste de tous les autres nœuds vers lesquels vous pouvez voyager à partir de ce nœud, je suppose que cela ne fonctionnera pas avec les polygones? et comment savoir si un polygone est ouvert / traversable ou s'il s'agit d'un objet solide? Comment puis-je stocker les nœuds qui composent le polygone?

Enfin, pour mémoire: je veux le programmer moi-même à partir de zéro même s'il existe déjà d'autres solutions disponibles et je n'ai pas l'intention de (ré) utiliser ce code dans autre chose que ce jeu, donc peu importe que ce sera inévitablement de mauvaise qualité.

Je conseillerais que même si vous allez écrire tout votre propre code, vous téléchargez Recast et construisez l'exemple d'application car il a des visualisations qui montrent le navmesh généré et cela vous permet de tester la recherche de chemin avec un simple point et cliquez interface. Vous pouvez apprendre beaucoup simplement en jouant avec ça.

Comme vous l'avez déjà réalisé, il y a deux étapes pour produire un bon chemin - le localisateur de chemin A * puis le post-traitement ultérieur qui comprend le redressement du chemin (l'élimination de tous les virages non nécessaires pour éviter les obstacles) et éventuellement aussi le ajout de courbes aux points de retournement.

Trouver son chemin

Vous avez maîtrisé la partie A *, ce qui est génial. Vous avez également fait remarquer qu'A * ne trouverait pas toujours le chemin le plus droit. Il est crucial de comprendre que c'est parce que A * est un algorithme pour trouver le chemin le plus court à travers un graphique (étant un concept mathématique où les nœuds sont sans dimension) lorsque vous l'appliquez à un maillage, vous devez mapper les nœuds aux éléments de maillage d'une manière ou d'une autre.

La chose la plus évidente à faire est de naviguer d'un point central à l'autre et de baser le coût sur cette distance, mais cela pose quelques problèmes. L'un est qu'il ne trouvera pas toujours le chemin géométriquement le plus court et le second est que si vous essayez de suivre le chemin que vous avez calculé là-bas, vous remarquerez qu'une ligne droite d'un centre au suivant peut traverser un polygone qui n'est pas ne fait pas partie du chemin (et peut ne pas être navigable du tout). Ce n'est pas un moyen horrible de coûter la traversée du graphe tout en effectuant A * mais ce n'est clairement pas suffisant pour n'importe quel but de traversée.

La prochaine solution la plus simple consiste à effectuer A * d'un bord à l'autre à travers le maillage. Vous trouverez cela plus simple à penser si vous imaginez qu'au lieu d'un nœud par polygone, vous avez un par bord par polygone. Ainsi, votre chemin va de votre point de départ à l'intérieur du bord le plus proche, traverse juste à l'intérieur du bord du polygone adjacent, puis juste à l'intérieur du bord suivant dans ce même polygone et ainsi de suite. Cela produit le chemin le plus court plus souvent et présente également l'avantage d'être traversable si vous ne souhaitez pas effectuer une étape de redressement de chemin.

Redressement de trajectoire

L'algorithme utilisé dans Detour (la bibliothèque de navigation qui accompagne Recast) est assez simple. Vous devez remarquer qu'il ne fera que redresser le chemin dans les limites des polygones trouvés lors de la recherche A *. En tant que tel, si cela ne trouve pas le chemin le plus serré autour d'un obstacle, vous n'obtiendrez pas non plus un chemin serré après avoir exécuté cet algorithme. En pratique, les mailles navales produites par la refonte ont tendance à avoir un seul polygone que vous pouvez traverser lorsque vous naviguez sur un point d'étranglement (le point le plus proche entre deux obstacles) et donc A * produira toujours une liste de nœuds aussi proches de l'obstacle que possible. Si vous utilisez des tuiles comme navmesh, ce ne sera pas le cas et cet algorithme très simple insérera des virages parasites.

L'algorithme de redressement de trajectoire du détour n'est pas tout à fait O (n) en complexité car lorsqu'il détermine qu'il doit insérer un tour, il l'insère au point où il a resserré l'entonnoir pour la dernière fois (en tournant à gauche et vice versa) et puis recommence le traçage à travers les nœuds à partir de ce point.

Si vous voulez redresser le chemin en dehors des polygones qui font partie de l'itinéraire A *, les choses deviennent beaucoup plus complexes. Vous devrez implémenter une routine de lancer de rayons qui peut tester si deux points de votre navmesh peuvent se voir (vous devriez de toute façon l'avoir pour que vous puissiez voir si vous devez utiliser A *). Pour ce faire, vous intersectez le segment de ligne formé par origine-> cible avec les bords de connexion du polygone contenant l'origine, puis testez les bords de connexion du polygone qui vous emmène, etc. Si vous croisez une arête non connectée (je les appelle arêtes de bordure), alors vous avez heurté un obstacle.

Vous pouvez ensuite effectuer ce test ray-cast chaque fois que l'algorithme d'entonnoir détermine qu'il doit insérer un tour pour voir s'il le fait vraiment, mais je pense que vous devrez continuer à effectuer ce test à chaque nœud jusqu'à ce que vous insériez un tour (à point auquel vous pouvez revenir à l'algorithme d'entonnoir simple). Cela va coûter cher, ce qui rend le chemin redressé approximativement O (n ^ 2).

Représentant le navmesh

Vous pouvez représenter votre maillage sous la forme d'un tableau de classes de polygones. La classe de polygones peut être aussi simple qu'un tableau de sommets et un tableau de références au polygone adjacent pour chaque arête s'il y en a un. Bien sûr, vous pouvez probablement penser à des moyens de stocker cela de manière plus compacte. Puisqu'un sommet est généralement partagé par plusieurs polygones, il est normal d'avoir un grand tableau de sommets et que chaque polygone stocke des indices dans ce tableau. Selon les caractéristiques de votre navmesh, vous pourriez avoir un nombre moyen d'arêtes de connexion qui ne représente que 50% ou moins du nombre d'arêtes. Dans ce cas, vous souhaiterez peut-être stocker un lien vers un autre polygone et l'index du bord plutôt que de stocker un lien pour chaque bord. Je vous recommande également de stocker l'index du polygone dans le tableau de polygones du navmesh plutôt que d'utiliser une référence de classe.