Je cherche la meilleure solution pour trouver la voie dans mon jeu. La carte est finalement basée sur une grille, mais les entités sont positionnées à l'aide de flotteurs et peuvent se déplacer dans n'importe quelle direction vers n'importe quel point de la carte. Le «terrain» dans mon jeu a un coût de déplacement uniforme, mais bien sûr, il peut y avoir des obstacles qui bloquent le chemin. La majorité des obstacles seront statiques, et bien qu'il y ait d'autres entités animées dans le jeu, je peux m'en tirer sans les considérer - c'est un jeu de stratégie de style hôpital à thème isométrique , donc pas de combat.
La plupart des articles de recherche de chemin que j'ai vus couvrent le mouvement 3D ou 2D basé sur une grille. Des suggestions pour quelque chose qui pourrait couvrir mon cas d'utilisation? Merci beaucoup.
la source
Réponses:
C'est ce qu'on appelle le «problème de détection de chemin sous tous les angles». Vous avez essentiellement deux choix:
Générez un maillage de navigation pour votre carte et recherchez-le en utilisant A *
Recherchez sur une grille à l'aide d'un algorithme destiné spécifiquement à la recherche de chemins sous tous les angles. Traditionnellement, la façon de procéder était le lissage de chemin A * + (interpolation linéaire, etc.) , mais ces jours-ci, une alternative plus populaire est Theta * , qui est plus facile à implémenter, s'exécute plus rapidement et produit de meilleurs résultats que le lissage de chemin.
Toutes les méthodes ci-dessus génèrent des résultats presque optimaux. Si, pour une raison quelconque, vous avez besoin de résultats optimaux, ce document a été publié il y a quelques semaines. Je n'ai pas encore eu la chance de le lire, donc je ne sais pas à quel point il est efficace ou difficile à mettre en œuvre.
la source