Je voudrais lire sur les algorithmes de recherche de chemin. Existe-t-il un document de base ou des documents ou des tutoriels sur Internet qui seraient un bon début pour moi?
algorithm
path-finding
Spoike
la source
la source
Réponses:
Si vous cherchez à faire de la recherche et à en apprendre davantage sur la découverte de trajectoire en général, je suggérerais certainement d'apprendre plus d'un algorithme. Vous voudrez comprendre les concepts généraux, mais pourrez les appliquer à tout ce sur quoi vous travaillez. La plupart des développeurs de jeux qui doivent faire des recherches sérieuses finissent par écrire leurs propres algorithmes personnalisés. Bien que fortement basés sur des solutions connues, chaque jeu est différent et aura des exigences différentes.
Je commencerais par lire certaines des méthodes les plus connues, telles que A *, les recherches sur l'algorithme de Dijkstra, la profondeur et l'étendue en premier. Il y a beaucoup de bonnes informations sur Internet sur chacun d'eux. ( http://en.wikipedia.org/wiki/Pathfinding )
En les lisant, notez les avantages et les inconvénients de chaque approche, ainsi que le type de données sur lequel l’algorithme peut fonctionner. Peut-il être appliqué à des chemins en 3 dimensions? Peut-il être modifié pour tenir compte de notre IA humaine qui veut éviter les mines antipersonnel sur la carte?
En ce qui concerne l'orientation, A * est à peu près le ticket d'or que tout le monde utilise. Vous devriez certainement savoir comment cela fonctionne. ( http://en.wikipedia.org/wiki/A*_search_algorithm )
Voici un bon exemple de A * tel qu’il s’applique à un jeu RTS, qui doit prendre en compte des entités de taille différente: http://aigamedev.com/open/tutorials/clearance-based-pathfinding/
Bonne chance!
la source
Les algorithmes de recherche de chemin sont essentiellement des algorithmes de résolution de problèmes de recherche de graphes.
http://en.wikipedia.org/wiki/Pathfinding#Algorithms
Le plus connu est l'algorithme de Djikstra: http://en.wikipedia.org/wiki/algorithme_Dijkstra
et son variant, l'algorithme de recherche A *: http://en.wikipedia.org/wiki/A*
la source
Il s'agit d'une excellente ressource de départ qui examine tous les aspects de la recherche de chemin dans une approche très facile à digérer.
Notes d'Amit à propos de Path-Finding
la source
La recherche de chemin est un problème assez résolu ... comme mentionné dans presque toutes les réponses, certaines variations sur A * seront ce que vous utiliserez.
Le plus gros défi pour moi est de savoir comment vous voulez représenter votre chemin . Utilisation d'une grille, de noms de chemins, de navmeshes, de grilles hiérarchiques ou d'autres structures complexes, etc.
Je n'ai pas de références spécifiques en tête, mais explorer AIGameDev vous donnera toutes sortes d'idées sur ce qui se passe.
Rappelez-vous simplement que chaque représentation a ses avantages et ses inconvénients; il ne s'agit pas de trouver le "meilleur", mais de trouver celui qui convient le mieux à votre jeu .
la source
Il y a une bonne liste sur Wikipedia: Pathfinding
Autant que je sache, A * et D * sont très populaires.
la source
Il existe plusieurs algorithmes de recherche de chemin sur le marché.
L'un des plus populaires est probablement A * ( A-Star ). C'est un algorithme très utile si vous avez une fonction heuristique qui peut vous donner des coûts estimés pour atteindre un objectif (par exemple, la distance de la ligne de visée par rapport à la cible). A * est très utile pour trouver le chemin le plus court du début à la fin.
En dehors de cela, il y a aussi l'algorithme de Dijkstra qui est très utile pour trouver l'élément le plus proche parmi plusieurs éléments. Par exemple. si vous voulez savoir quel power-up (ou similaire) est le plus proche de votre personnage de jeu.
Il existe plusieurs autres algorithmes, mais je suppose que A * est de loin le plus populaire. Mat Buckland a un excellent chapitre sur la découverte de chemins dans son livre de programmation AI par exemple . Je vous encourage fortement à en obtenir une copie. Sinon, vous trouverez une foule d’informations en ligne en recherchant "Recherche par étoile".
la source
Voici un tutoriel sur l'utilisation de l'algorithme de Dijkstra pour la recherche de chemin.
la source
Voici un bon exemple d'utilisation de A * dans un jeu contenant du code psuedo: http://www.anotherearlymorning.com/2009/02/pathfinding-with-a-star/
la source
Ce n’est pas vraiment une amorce, mais nous avons beaucoup discuté des algorithmes de graphes dans notre classe d’algorithmes à l’automne dernier, à l’automne 2009. Nous avons utilisé ce livre,
Introduction aux algorithmes, troisième édition de Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein
http://mitpress.mit.edu/algorithms/
et il est également accompagné de conférences youtube d'une classe du MIT.
http://ocw.mit.edu/courses/electric-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/
Les chapitres 17, 18 et 19 traitent des chemins les plus courts.
la source
Voir [Algorithmes de recherche de graphes et d’arbres] sur Wikipedia 1 . Celles-ci ne sont quasiment qu’une variante de la recherche dans l’espace d’état;
Il y a aussi Collaborative Diffusion , qui est l'un des algorithmes mentionnés précédemment, fait de manière intéressante.
la source
Celui-ci a l'air intéressant:
http://www.codeproject.com/Articles/455 Je me demande s'il vaut mieux que A *?
la source