Comment fonctionne la recherche de chemin du maillage de navigation?

27

Je veux comprendre comment les navmeshes fonctionnent, comment les implémenter et pourquoi c'est mieux que d'autres types de systèmes de cheminement.

algorithm path-finding Feu
la source
Cela est apparu au cours de mes pérégrinations matinales sur Internet: aigamedev.com/open/reviews/alienswarm-node-graph Ça vaut peut-être la peine d'être lu :-)
coderanger
Ce didacticiel peut être utile pour les utilisateurs d'Unity qui rencontrent cet article: binpress.com/tutorial/unity3d-ai-navmesh-navigation/119
MichaelHouse

Réponses:

6

C'est la même chose que la recherche de points de cheminement, mais au lieu de points de cheminement, vous avez des polygones de chemin et vous pouvez en déduire quelques choses sur navimesh:

  • les polygones de chemin sont des zones où les entités peuvent marcher en toute sécurité
    • d'autres domaines ne devraient probablement pas être pris en considération
    • les points de cheminement doivent faire un saut de foi dans l'espace entre eux; rappelez-vous les PNJ coincés dans les murs? C'était à des endroits où deux points de cheminement n'étaient pas directement connectés.
  • Il y a potentiellement moins de nœuds (car les polygones sont plus grands)
    • C'est donc probablement plus rapide
    • Par conséquent, il a des besoins en mémoire potentiellement plus petits
  • C'est plus réaliste (parce que l'aire du polygone contient en théorie une quantité infinie de points)
user712092
la source
2

Généralement, ils sont utilisés avec une sorte d'algorithme A * amélioré (prend en compte les liens de saut ou de vol pour la recherche de chemin 3D). De cette façon, ce n'est pas vraiment un système différent de tout le reste, c'est plutôt un moyen de générer un réseau de recherche de chemin normal directement à partir d'un environnement ou d'un terrain hautement poly (enfin, relativement parlant). Pour une raison quelconque, nous les appelons ici des balises, mais l'idée est la même, une sorte de processus automatisé s'exécute sur chaque carte et produit un ensemble simple de connexions qui peuvent faire fonctionner A * sur elles dans des délais raisonnables. Si vous essayiez de trouver un chemin par rapport aux données sous-jacentes brutes, ce serait trop lent pour un jeu à cause de la densité du maillage.

coderanger
la source
N'est-ce pas un graphique de points de cheminement, sauf sur un maillage simplifié? Je pensais que les navmeshes vous permettaient de faire du chemin sur le polygone.
Incendie du
Le graphique simplifié vous permet d'effectuer un parcours longue distance, la courte portée est généralement gérée d'une autre manière. Il semble que le système de Valve utilise les données de maillage pour les deux, juste de différentes manières (routage de supernode vs contraintes locales).
coderanger
Un simple ensemble de connexions n'est pas un navmesh, n'est-ce pas? Je pensais que cela s'appelait navmesh parce que vous traitez sur des polygones.
Feu
Je ne pense pas que la navigation locale ou globale soit pertinente ici.
Feu
1
Un ensemble de polygones voisins est toujours un graphique comme un ensemble de points de cheminement et vous pouvez faire A * dessus de la même manière. La seule différence est qu'une fois que vous savez quels polygones vous allez parcourir, vous tracez les lignes différemment.
coderanger
0

Il y a plusieurs façons de le faire. Un * et tel est une bonne option, mais manque de documentation. Vous pouvez faire quelque chose comme placer des nœuds de manière quasi aléatoire autour de la carte et vérifier quels nœuds peuvent se voir et créer un petit réseau de nœuds. Pas le plus optimal mais facile à comprendre.


la source