Comment générer une grille de navigation pour un monde 3D?

J'essaie de trouver une solution à ce problème. J'essaie de construire un maillage de navigation au format d'une grille de sommets verrouillés sur des coordonnées au sol x, y en forme de carrés pour un espace 3D. Mais j'ai du mal à essayer de trouver une façon de procéder.

J'ai essayé de regarder dans la bibliothèque de refonte. C'est une méthode assez robuste, mais elle ralentit apparemment avec des cartes plus grandes et un espace ouvert. Je ne sais pas non plus comment ils génèrent des sommets et des arêtes pour l'espace mondial avec la carte des hauteurs.

Ma prochaine pensée était de faire ce qu'Unreal Engine 3 faisait.

https://udn.epicgames.com/Three/NavigationMeshReference.html

Ce qui était d'utiliser des raycasts pour générer le maillage. Je n'arrivais pas à comprendre comment arrêter les diffusions.

Alors ... ma prochaine option était la boîte, peut-être une boîte moulée. Créez un volume subdivisé avec une taille qui est une puissance de 2. Alignez la boîte sur la grille et tirez des prismes rectangulaires vers le bas comme un rayon. S'il atterrit sur un morceau de géométrie qui fait partie du sol et que le rectangle n'est pas intersecté, laissez-y un carré. Et continuez jusqu'à ce que les limites du volume soient atteintes. Pour vérifier si les arêtes doivent être liées, je suppose que je pourrais vérifier pour voir si la pente entre deux paires de sommets est dans la pente praticable, les fusionner si c'est vrai.

Mes principaux problèmes sont ... cela ne semble pas être très optimal. Sans y penser, à l'estimation, le processus est O (N ^ 3) pour un niveau multicouche. Ce qui peut devenir assez méchant.

Et le dernier bit est pour créer automatiquement des groupes rectangulaires de ces carrés. Je ne sais pas trop comment faire ça. L'implémentation Unreal les sépare par pentes. Cependant, j'essaie de garder le format de la grille. Ce n'est donc pas tout à fait nécessaire. Le problème demeure sur la création de grandes tuiles rectangulaires pour diviser le processus de recherche de chemin en une base par tuile. Les tuiles ne peuvent être ni trop grandes, ni trop petites.

Les questions sont donc ...

Quelle serait une manière efficace de générer ce navmesh ceinturé? Et quelle serait une bonne façon de créer les tuiles?

Un monde 3D de base pourrait être représenté par un maillage de navigation qui peut être commodément intégré à la plupart des moteurs de jeu. L'acteur peut voyager le long des bords des polygones.

Ce serait une solution simple. Il existe de nombreux algorithmes pour rechercher un chemin et générer un navmesh.

Je voudrais partager quelque chose que j'ai lu il y a quelque temps.

Cela décrit une solution possible où nous pouvons briser notre monde de jeu en carreaux carrés. chaque fois qu'une tuile carrée est ajoutée dans le jeu (lorsque le joueur s'approche d'une zone / terrain procédural), une tuile carrée est ajoutée. Cependant, nous n'avons plus à calculer l'intégralité du navmesh. nous le calculons simplement pour cette tuile et l'ajoutons au graphique existant. Gain de performances significatif.

Le problème suivant abordé est le mouvement irrégulier de l'exemple précédent. Je peux comprendre qu'en considérant les virages futurs et en généralisant la direction, cela réduirait beaucoup le mouvement en zigzag et rendrait le mouvement fluide. Les jeux avec une animation détaillée ne le donnent pas, mais vous pouvez le remarquer dans certains jeux du monde ouvert où je suppose que la navigation est principalement cuite.

Quant à la question, je vous recommanderais d'aller vérifier la réponse de Kromster sur une liste d'algorithmes de génération de navmesh.

Consultez également The AI ​​Systems of Left 4 Dead dont les exemples font partie. De nombreux sujets plus intéressants couverts

Bonne chance.

il y a plusieurs façons, pourquoi ne pas simplement le rendre local pour le joueur, faire une petite grille qui suit le joueur et vérifie sous chaque intersection si oui ou non sa transverse, comme y a-t-il un étage là-bas et faites un lancer de rayon pour voir s'il y a un mur / bâtiment sur n'importe quel côté à venir ..

C'est un problème que j'ai vu partout. L'astuce est la "séparation des préoccupations". "Dis quoi?", Je vous ai entendu réfléchir. Ce qui est affiché à l'écran n'est PAS ce qu'est la "structure de données". Il est important de garder les visuels séparés des données pour construire le visuel. Cela permettra toujours de "pérenniser" votre jeu lorsque de nouvelles versions logicielles sous-jacentes seront publiées.

Construisez une structure de données (aka: modèle) qui représentera votre monde de jeu. Construisez ensuite une "vue" du modèle de structure de données. Si vous voulez changer le monde d'une grille en damier à une grille hexagonale, la structure des données (modèle) reste la même, mais l'affichage "peindra" (rendra) une vue différente.

Faites un double tableau. Et puis si un objet / des objets sont inpassables, ayez une méthode pour indiquer au tableau que la position n'est pas passable. Lorsqu'une IA essaie de se déplacer, elle regarde le double tableau et voit s'il est passable.