J'ai d'abord posé cette question sur le débordement de pile, mais je suppose que personne n'est très intéressé par les jeux vidéo là-bas ...

Quels sont les algorithmes de recherche de chemin utilisés dans les jeux de tous types? (De tous les types où les personnages se déplacent, de toute façon) Dijkstra est-il beaucoup utilisé? Je ne pense pas, car cela ne trace pas réellement les étapes à suivre pour arriver quelque part, non? Si je comprends bien, cela ne détermine que l'objet le plus proche. Je ne cherche pas vraiment à coder quoi que ce soit; juste faire des recherches, mais si vous collez du pseudocode ou quelque chose, ce serait bien (je peux comprendre Java et C ++). Je cherche essentiellement un aperçu rapide de la recherche de chemin en général.

Je sais que A * est comme l'algorithme à utiliser dans les jeux 2D. C'est génial et tout, mais qu'en est-il des jeux 2D qui ne sont pas basés sur une grille? Des choses comme Age of Empires ou Link's Awakening. Il n'y a pas d'espaces carrés distincts pour naviguer, alors que font-ils?

Que font les jeux 3D? J'ai lu ce truc http://www.ai-blog.net/archives/000152.html , ce que j'entends est une grande autorité sur le sujet, mais cela n'explique pas vraiment COMMENT, une fois les maillages définis, la recherche de chemin est terminée. SI A * est ce qu'ils utilisent, alors comment faire quelque chose comme ça dans un environnement 3D? Et comment fonctionnent exactement les cannelures pour arrondir les coins?

Trop de questions à la fois, il est donc difficile de donner une réponse concrète mais de discuter de quelques-uns de ces sujets. Je vais diviser la réponse en deux et essayer d'y répondre du mieux que je peux. Je ne prétends pas que ces listes soient complètes , mais ce sont quelques-unes des différentes méthodes dont je me souviens.

Partie 1 - Algorithmes de recherche de chemin

Pour commencer, il existe de nombreuses façons d'implémenter la recherche de chemins, mais tous ne renvoient pas le chemin le plus court, ni ne sont efficaces ou même fiables. Par exemple:

• Méthodes primitives qui ne "regardent pas vers l'avenir" et ne font qu'une étape à la fois:

  • Backstepping aléatoire - Faites un pas à la fois dans la direction de l'objectif. Si un obstacle est rencontré, essayez de le contourner en faisant un pas en arrière dans une direction aléatoire, puis en réessayant. Pas fiable du tout et restera coincé dans une multitude de situations.

  • Traçage d'obstacles - Autre approche, semblable à un pas en arrière aléatoire mais au lieu de reculer de manière aléatoire, commencez à tracer autour de l'objet une fois qu'une collision est détectée, comme si vous aviez la main droite collée au mur et que vous deviez bouger en le touchant. Une fois qu'il n'y a pas de collision, continuez de vous déplacer dans la direction du but. Une fois de plus, vous pouvez rester coincé dans de nombreuses situations.

• Méthodes qui permettent de trouver le chemin complet en une seule fois:

  • Breadth First Search - Traversée simple du graphique en visitant chaque couche d'enfants à la fois, arrêtez-vous lorsque le chemin est trouvé. Si le graphique n'est pas pondéré (c'est-à-dire que la distance entre chaque nœud adjacent est toujours la même), il trouve le chemin le plus court mais pas trop efficacement. Pour les graphiques pondérés, il peut ne pas renvoyer le chemin le plus court, mais il en trouvera toujours un s'il existe.

  • Depth First Search - Une autre façon de parcourir un graphique, mais au lieu de le prendre couche par couche, l'algorithme essaie d'abord de rechercher en profondeur dans le graphique. Cette méthode peut avoir des problèmes si la profondeur de la recherche n'est pas limitée, en particulier lors de l'utilisation d'une implémentation récursive, ce qui peut entraîner un débordement de pile, il est donc généralement plus sûr de l'implémenter de manière itérative à l'aide d'une pile.

  • Meilleure première recherche - Similaire à la recherche en largeur, mais utilise une heuristique qui choisit d'abord le voisin le plus prometteur. Le chemin renvoyé n'est peut-être pas le plus court, mais il est plus rapide à exécuter que la première recherche étendue. Un * est un type de meilleure première recherche.

  • Méthode de Dijkstra : assure le suivi du coût total depuis le début de chaque nœud visité et l'utilise pour déterminer le meilleur ordre pour parcourir le graphique. Fonctionne avec des graphiques pondérés et renvoie le chemin le plus court, mais peut impliquer beaucoup de recherches.

  • A * - Similaire à Dijkstra, mais utilise également une heuristique pour estimer la probabilité que chaque nœud soit proche de l'objectif, afin de prendre la meilleure décision. En raison de cette heuristique, A * trouve le chemin le plus court dans un graphique pondéré d'une manière beaucoup plus rapide.

• Ensuite, il y a des variations de A * (ou des optimisations d'orientation en général) qui le rendent plus rapide ou plus adapté à certaines circonstances, telles que (voir la réponse associée et une liste complète sur cstheory.SE ):

  • LPA * - Similaire à A * mais peut recalculer plus rapidement le meilleur chemin quand un petit changement au graphique est fait
  • D * Lite - Basé sur LPA *, il fait la même chose, mais suppose que le "point de départ" est une unité se déplaçant vers la fin pendant que les modifications du graphique sont effectuées
  • HPA * (hiérarchique) - Utilise plusieurs couches à différents niveaux d'abstraction pour accélérer la recherche. Par exemple, une couche de niveau supérieur peut simplement connecter des pièces, tandis qu'une couche de niveau inférieur se charge d'éviter les obstacles.
  • IDA * (Iterative Deepening) - Réduit l'utilisation de la mémoire par rapport à la norme A * en utilisant l'approfondissement itératif.
  • SMA * (Simplified Memory-Bounded) - Utilise uniquement la mémoire disponible pour effectuer la recherche.
  • Jump Point Search - Crédits à Eric dans les commentaires pour l'avoir mentionné! Accélère la recherche de chemin sur les cartes de grille à coût uniforme ( lien ).

Partie 2 - Représentation de l'espace de recherche

Et enfin pour répondre à cette question:

Je sais que A * est comme l'algorithme à utiliser dans les jeux 2D. C'est génial et tout, mais qu'en est-il des jeux 2D qui ne sont pas basés sur une grille?

Deux grandes idées fausses ici! En réalité:

1. Un * ne se soucie pas si le jeu est en 2D ou en 3D, et est également approprié pour les deux cas.
2. A * fonctionne sous n'importe quelle représentation graphique, donc peu importe si le monde est une grille ou non.

Donc, si le monde n'a pas besoin d'être une grille, de quelles autres manières pouvez-vous le représenter? Voici un bref aperçu des moyens de partitionner l'espace mondial pour la recherche de chemins, et la plupart d'entre eux fonctionnent à la fois pour la 2D et la 3D:

• Grille rectangulaire - Partitionnez le monde en grille régulière de carrés, chaque cellule de la grille étant un nœud dans le graphique, et la connexion entre deux nœuds non obstrués est une arête.

  

• Quadtree - Une autre façon de partitionner l'espace, mais au lieu de partitionner en une grille de cellules de taille régulière, partitionnez en quatre, puis divisez récursivement chacune de ces quatre en quatre. L'ajout d'une troisième dimension en fait un octree .

  

• Polygones convexes - Partitionner la zone praticable en un maillage de polygones convexes interconnectés. Chaque polygone devient un nœud et les bords partagés sont les bords du graphique. Ceux-ci peuvent être des triangles par exemple, et parfois même un maillage créé par un artiste lors de la création des ressources de niveau. Souvent appelé maillage de navigation . Voir ce lien . Voici un ensemble d'outils de construction de maillage de navigation très populaire: Refonte .

  

• Points de visibilité - La façon la plus courante consiste à placer un nœud juste à l'extérieur de chacun des sommets convexes de l'obstacle, puis à connecter chaque paire de nœuds qui peuvent se voir . Vérifiez ce lien . Les nœuds ne doivent pas nécessairement être les sommets et peuvent être placés manuellement par le concepteur dans la carte. Dans ce cas, le système est souvent appelé graphe de points de cheminement .