Comment générer un maillage de navigation 2D dans un environnement dynamique lors de l'exécution?

9

J'ai donc compris comment utiliser A * pour trouver un chemin et je peux l'utiliser sur une grille. Cependant, mon monde de jeu est immense et j'ai de nombreux ennemis qui se dirigent vers le joueur, qui est une cible en mouvement, donc un système de grille est trop lent pour trouver un chemin. J'ai besoin de simplifier mon graphique de nœud en utilisant un maillage de navigation.

Je saisis le concept de "comment" fonctionne un maillage (trouver un chemin à travers des nœuds sur les sommets et / ou les centres des bords des polygones).

Mon jeu utilise des obstacles dynamiques générés de manière procédurale au moment de l'exécution.

Je ne peux pas tout à fait comprendre comment prendre un avion qui comporte plusieurs obstacles et diviser par programme la zone praticable en polygones pour le maillage de navigation, comme l'image suivante.

maillage de navigation

Où est-ce que je commence? Comment savoir quand un segment de zone piétonnière est déjà défini, ou pire, quand je me rends compte que je dois subdiviser une zone piétonnière précédemment définie lorsque l'algorithme "parcourt" la carte?

J'utilise javascript dans nodejs, si cela est important.

Stephen
la source
1
Le partitionnement dynamique que vous essayez d'implémenter dépendra des spécificités de vos éléments de carte. Vos éléments d'obstacles sont-ils entièrement composés de rectangles alignés sur la grille comme indiqué dans votre exemple? Rectangles tournés? Polygones irréguliers? Ou des formes non polygonales avec beaucoup de courbes? Avez-vous des données ponctuelles / poly pour la forme des obstacles? Dans l'affirmative, ces données de forme sont-elles des triangles, des rectangles, exclusivement des polygones convexes ou un mélange de polygones convexes et concaves?
Matthew R
@Matthew My world est composé d'obstacles polygonaux convexes, sans courbes ni polygones concaves. Chaque obstacle est stocké sous la forme d'un objet polygone avec des sommets représentés par des objets vectoriels.
Stephen
1
Pour ce que ça vaut, je travaille sur une solution basée sur cet article: gradworks.umi.com/3493710.pdf Si je réussis je posterai ma solution.
Stephen
1
le maillage de navigation n'est pas là pour vous dire à 100% si vous pouvez aller quelque part ou non, c'est juste un aperçu de base des zones accessibles à pied, vous devez toujours faire des vérifications de collision contre des objets dynamiques, modifier: à peu près ce que Ray a dit
dreta
@Stephen - Voir la réponse du commentaire long .
Matthew R

Réponses:

3

@Stephen - Commentaire long - Ce document semble valoir la peine d'être lu lorsque j'aurai du temps. Fondamentalement, ce que j'aurais suggéré est quelque chose dans le sens de l'algorithme Hertel-Mehlhorn qui est mentionné dans l'article (une référence pour cet algorithme spécifique peut être trouvée ici http://www.bringyou.to/compgeom/ ) avec l'ajout de subdiviser les côtés de la carte (en dehors de la limite de la zone de jeu) un certain nombre de fois pour réduire l'occurrence de multiples petits triangles formés dans les coins. Ces petits triangles peuvent être problématiques car ils peuvent finir par être plus petits que la chose pour laquelle vous préformez la recherche de chemin. Le Hertel-Mehlhorn est pour la réduction des polygones produits par une partition triangulaire si vous êtes intéressé ici, c'est plus sur la triangulation:http://www.personal.kent.edu/~rmuhamma/Compgeometry/MyCG/PolyPart/polyPartition.htm .

De plus, si vous préférez ne pas réinventer la roue, je pense que cette bibliothèque fera tout ce dont vous avez besoin: http://code.google.com/p/polypartition/ . Il préforme les triangulations et les réductions avec l'une des nombreuses options différentes, y compris Hertel-Mehlhorn. Il s'agit d'une licence MIT, ce qui signifie qu'elle peut être utilisée pour des projets fermés et commerciaux si cela pose problème.

Si vous décidez de continuer à travailler sur votre propre implémentation, j'aimerais voir ce que vous proposez.

Matthew R
la source
1
Excellente réponse, @Mathew. Et vous devriez certainement lire ce document! Il est facile à suivre et explique une excellente technique (en particulier l'annexe A qui parle de la découverte / génération basée sur agent du maillage). Je suis en train de coder une version de cet algorithme pour javascript, et cela se passe bien. Je le posterai comme réponse quand ce sera fait.
Stephen
@Stephen aimerait voir ce travail
kevzettler
@Stephen Je recherche aussi une version javascript
Apolo
6

Plutôt qu'un maillage, vous pourriez simplement envisager une approche hiérarchique A *. Le plus grand avantage d'un maillage est de gérer des mondes de jeu qui ne sont pas alignés sur la grille, plutôt que de réduire la complexité d'une grille.

Avec une approche hiérarchique, vous subdivisez votre monde à plusieurs reprises (un peu comme un arbre quadruple) et générez des informations de connectivité entre les nœuds. Vous pouvez ensuite générer rapidement un chemin entre de gros morceaux du monde et utiliser uniquement la grille haute résolution pour rechercher un chemin dans un plus grand morceau.

L'approche hiérarchique donnera des ordres de grandeur de meilleures performances, tandis qu'au mieux un maillage ne vous donnera qu'une petite amélioration linéaire.

L'approche naïve consiste simplement à diviser votre monde en X par X plus gros morceaux alignés sur la grille, à générer les informations de connectivité entre eux (par exemple, y a-t-il un chemin entre le morceau 2x1 de 3x1 à 2x2 et quelle est la distance du chemin moyen) .

Notez que vous ne pouvez pas toujours obtenir des chemins idéaux avec cette approche dans certaines circonstances particulières. La génération de couches de morceaux de taille variable atténue le problème, mais honnêtement, il est généralement beaucoup plus facile d'éviter les problèmes avec les chemins problématiques et de se fier au fait que le joueur est très peu susceptible de remarquer des ennemis prenant des chemins sous-optimaux, sauf dans le le plus dégénéré des cas.

Sean Middleditch
la source
1
Je devrais expliquer davantage: mon jeu n'est pas aligné sur la grille. Je construisais une grille dans une zone de 800 x 600 pixels, chaque pixel étant un espace sur la grille (je pensais toujours à A *, donc je ne pensais pas encore aux performances de cela). J'ai des obstacles qui ne sont pas aussi simples que ceux de l'exemple ci-dessus, j'essayais juste d'illustrer le problème. De toute évidence, un tel terrain de jeu devait être révisé, et après quelques recherches, je pense qu'un maillage de navigation serait la bonne voie à suivre.
Stephen
3

Je pense que vous pourriez être trop compliqué. Vous n'avez probablement pas besoin de générer des maillages de navigation à la volée. Ayez à la place un maillage de navigation statique pour votre monde de base.

Le contournement des obstacles peut être résolu en utilisant des comportements de direction (utilisez l'évitement d'obstacles). Si par hasard votre obstacle est si grand qu'il remplit ou bloque complètement le voyage d'un nav-poly au suivant, alors ayez un moyen de vérifier ce cas de bord et de recalculer le chemin entre le poly dans lequel vous vous trouvez actuellement et le celui dont vous êtes bloqué.

Ray Dey
la source