Quels sont les algorithmes de recherche de chemin? [fermé]

Réponses:

34

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!

rapport
la source
2
+1 pour le peu que les programmeurs doivent apprendre à adapter des solutions connues. C'est quelque chose que de nombreux développeurs de jeux potentiels ne comprennent pas.
Ingénieur
22

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*

images clés
la source
2
Le dernier lien est cassé parce que le * n'est pas vu comme faisant partie de celui-ci: en.wikipedia.org/wiki/A%2A
Hendrik Brummermann
fixx0r3d les deux liens
tenpn
Les algorithmes simples de recherche de graphes ne sont que les bases de la recherche de chemin.
Mars
13

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

... Pathfinding aborde le problème de trouver le bon chemin du point de départ au but: éviter les obstacles, éviter les ennemis et minimiser les coûts (carburant, temps, distance, équipement, argent, etc.). Le mouvement aborde le problème de prendre un chemin et de le suivre. Il est possible de consacrer vos efforts à un seul de ceux-ci. À un extrême, un pathfinder sophistiqué associé à un algorithme de mouvement trivial ...

David Young
la source
1
+1 pour Amit. J'ai appris A * sur son site web il y a plus de 10 ans.
tenpn
Belles illustrations aussi. Haute qualité.
singe
5

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 .

Ipsquiggle
la source
5

Il y a une bonne liste sur Wikipedia: Pathfinding

Autant que je sache, A * et D * sont très populaires.

Craig Martek
la source
+1 pour avoir mentionné le dynamique A * mieux connu sous le nom de D *
David Young
4

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".

bummzack
la source
Oh mon. Tandis que je tapais ceci, la même réponse a été donnée environ un milliard de fois. Désolé :)
bummzack
Je viens de remarquer que le livre mentionné est aussi sur Google-Books (bien qu’il ne soit pas complet). Lisez-le ici: books.google.com/books?id=gDLpyWtFacYC
bummzack
2

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.

bluedes
la source
2

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.

utilisateur712092
la source
+1 Ce document sur Collaborative Diffusion est très intéressant.
Ingénieur
1
Je pense que le lien est brisé. Peut-être que ceci est le bon: scalablegamedesign.cs.colorado.edu/gamewiki/index.php/…
pek
-2

Celui-ci a l'air intéressant:

http://www.codeproject.com/Articles/455 Je me demande s'il vaut mieux que A *?

Tom
la source
Bienvenue sur le site. Ce que vous avez donné est connu sous le nom de réponse sous forme de lien uniquement, ce qui est déconseillé. Il serait préférable de résumer les qualités de la méthode dans votre réponse. Vous pourriez alors vous demander s'il vaut mieux que le simple A *, plutôt que de le méditer inutilement dans le texte.
Seth Battin
Je vois que votre réponse est plus ou moins à la hauteur de cette question (ce qui est regrettable). Je ne veux pas vous singulariser, j'ai simplement passé votre entrée dans la première file d'attente de critiques de posts . Quoi qu'il en soit, l'amélioration de votre réponse est toujours la bienvenue.
Seth Battin
Je vais juste répéter ce que Seth a dit. Résumer.
Gris