Techniques astucieuses de l’algorithme A* pour la recherche de chemin dans les jeux vidéo
(timmastny.com)- Dans un jeu 8 bits en vue de dessus inspiré de Zelda, implémenter le suivi par les monstres ne peut pas se limiter à un simple déplacement en ligne droite : la comparaison entre Dijkstra et A* permet de trouver les compromis de pathfinding adaptés au jeu
- Le déplacement en ligne droite s’arrête lorsqu’il rencontre un mur, mais en ajoutant du wall-sliding, le personnage peut se déplacer le long des murs, ce qui améliore les sensations de contrôle et peut aussi créer un élément stratégique consistant à piéger les monstres dans le décor
- L’algorithme de Dijkstra garantit le plus court chemin, mais explore largement autour du nœud de départ ; dans un jeu où la destination change à chaque frame, il effectue donc beaucoup plus de calculs que nécessaire pour déterminer la prochaine direction
- A* définit la priorité d’exploration selon la distance à la destination pour examiner d’abord la direction de la cible ; s’il rencontre un mur, il inspecte les nœuds voisins et, sans revisiter les nœuds déjà vus, peut trouver un détour
- Sur une carte de jeu, on peut ajuster vitesse et difficulté d’implémentation avec un graphe implicite qui ne préconstruit pas la liste d’adjacence, une exploration par tuiles et des heuristiques fondées sur la géométrie, comme une profondeur d’itération limitée
Contexte du jeu et besoins de base
- Dans un jeu 8 bits en vue de dessus inspiré de Zelda, basé sur PPU466, les monstres devaient poursuivre le joueur
- PPU466 présente des contraintes proches de celles d’une console fantasy comme PICO-8 : graphismes 8 bits, 4 couleurs par tuile, arrière-plan fixe et nombre réduit de sprites
- L’objectif est que les monstres suivent le joueur sans simplement s’arrêter contre les murs ni rester coincés de façon indésirable
Déplacement en ligne droite et wall-sliding
- L’approche la plus simple consiste à tracer une ligne droite entre le monstre et le joueur, puis à se déplacer dans cette direction
- Avec cette seule méthode, le monstre s’arrête dès qu’il touche un mur
- En appliquant le wall-sliding, lorsqu’il heurte un mur, il ne s’arrête pas et se déplace le long de celui-ci
- Pour les déplacements du joueur, c’est une technique qui rend les contrôles plus réactifs près des murs et des coins, et elle est utilisée dans presque tous les jeux
- Elle est employée depuis Pac-Man, et Pac-Man Championship Edition DX+ ajoute un effet d’étincelles lorsque le joueur effectue un wall-slide
- Ajouter le wall-sliding au déplacement en ligne droite permet de piéger les monstres dans certaines configurations de terrain
- Certains jeux en font un élément stratégique ; le safespotting de Runescape en est un exemple
- Dans ce jeu, ce comportement n’était pas souhaité, d’où l’examen de véritables algorithmes de pathfinding
Limites de l’algorithme de Dijkstra
- L’algorithme de Dijkstra est intuitif à implémenter et garantit le plus court chemin
- Le problème est qu’il en fait beaucoup trop par rapport au besoin
- Il trouve le plus court chemin entre le nœud de départ et tous les autres nœuds du graphe
- On peut certes l’arrêter lorsqu’il trouve le nœud de destination, mais il n’existe pas de moyen d’orienter la recherche vers une destination précise
- Dans un jeu vidéo, le joueur se déplace en permanence, donc la destination du monstre change à chaque frame
- Ce dont le monstre a besoin se rapproche davantage de la direction à prendre maintenant que d’un chemin complet
- On pourrait précalculer les plus courts chemins pour tous les pixels ou toutes les tuiles de la carte, mais cela consommerait beaucoup de mémoire
- Sur les plateformes anciennes ou limitées en ressources, Dijkstra n’est pas adapté
Pourquoi A* convient au pathfinding dans les jeux
- A* Search Algorithm utilise l’information de distance entre le nœud de départ et la destination pour définir les priorités d’exploration
- À la première étape, il essaie en priorité la direction qui mène en ligne droite vers la destination
- Contrairement à Dijkstra, il ne passe pas beaucoup de temps à explorer la direction opposée si ce n’est pas nécessaire
- Si un mur bloque le chemin, il examine les nœuds voisins pour tenter de le contourner
- Comme Dijkstra, il ne revisite pas les nœuds déjà vus ; même si de nombreux retours en arrière sont nécessaires, il finit donc par trouver un détour
- Dans l’exemple, le monstre qui utilise A* ne reste pas coincé derrière le mur
Structure de données en graphe implicite
- Les graphes de manuel sont représentés par une liste de nœuds et une matrice d’adjacence ou une liste d’adjacence, mais dans un jeu, on peut générer les nœuds voisins de manière plus flexible
- Par exemple, sur un écran de 256×240 pixels, chaque coordonnée de pixel peut être considérée comme un nœud
- Les pixels adjacents couvrent 8 directions : haut, bas, gauche, droite, ainsi que les 4 diagonales
- Le poids des déplacements haut, bas, gauche et droite est de 1, celui des diagonales est √2, soit environ 1,4
- Au lieu de créer à l’avance une énorme liste d’adjacence, on peut la générer à la volée uniquement pour les nœuds effectivement visités
- Les pixels situés sur un mur ou occupés par un autre sprite ne sont pas des positions valides pour un monstre ; ils sont donc exclus dynamiquement de la liste d’adjacence
- Avec cette méthode, il n’est pas nécessaire d’exclure manuellement dans l’éditeur de carte les nœuds inaccessibles
Heuristiques reflétant la géométrie de la carte
- Certains éléments de A* peuvent être ajustés directement à la structure géométrique de la carte
-
Taille des pas
- Au lieu d’utiliser les pixels comme nœuds, dans un jeu 2D à tuiles, on peut utiliser les tuiles comme nœuds
- L’exploration par tuiles réduit fortement le nombre d’itérations nécessaires pour trouver un chemin jusqu’au joueur, ce qui accélère la recherche
- Dans ce cas, le chemin ressemble davantage à une séquence de directions que doit suivre le monstre qu’à une liste exacte de déplacements frame par frame
- Comme les monstres ne se déplacent généralement pas à une vitesse de 1 tuile par frame, même avec un chemin basé sur les tuiles, l’information réellement nécessaire est la direction permettant d’atteindre le joueur
- Un chemin basé sur les pixels a la même nature, et le monstre ne se déplace pas forcément d’1 pixel par frame ni d’un nombre entier de pixels
-
Profondeur d’itération
- Dans A*, lorsqu’un nœud sort de la file de priorité, il constitue la dernière étape du meilleur chemin vu jusque-là
- Si l’on arrête l’algorithme après un nombre fixe d’itérations, on obtient la meilleure estimation de chemin disponible à ce stade vers le plus court chemin jusqu’à la destination
- Il est possible d’obtenir une direction de progression raisonnable sans exécuter l’algorithme jusqu’au bout
- La profondeur maximale d’itération doit être ajustée à la géométrie du niveau
- Si la profondeur est trop faible, le monstre peut encore rester coincé derrière un mur
- Dans l’exemple, avec une profondeur fixe de 30 tuiles, le monstre reste bloqué selon la position du joueur et ne parvient pas à avancer
- Comme A* est recalculé à chaque frame, des boucles peuvent apparaître
- À la première frame où il atteint le mur, l’algorithme calcule qu’il faut descendre
- À la frame suivante, il calcule qu’il faut monter
- Cette répétition piège le monstre dans une boucle
- Si le joueur entre dans le rayon de recherche du monstre, celui-ci peut trouver le bon chemin
- Avec une profondeur fixe de
1, ce phénomène devient encore plus extrême : le monstre revient sans cesse au pixel dont la distance euclidienne au joueur est la plus courte
Compromis avec le précalcul
- Pour raffiner l’approche, on peut précalculer, pour n’importe quelle position sur la carte, la profondeur maximale dont A* a besoin pour trouver un chemin
- Contrairement au précalcul complet de tous les chemins à la manière de Dijkstra, il suffit de stocker cette seule valeur maximale
- Avec cette profondeur maximale, A* peut trouver un chemin valide en temps réel
1 commentaires
Commentaires Hacker News
Astuces utilisées avec A* dans un MMO en production : 1) utiliser un graphe hiérarchique — par ville, entre les pièces d’un bâtiment, puis à l’intérieur d’une pièce — permet de trouver un chemin en une fraction de milliseconde entre n’importe quels points, dans n’importe quelle pièce de n’importe quel bâtiment de n’importe quelle ville
2) stocker les métadonnées de la recherche A* en cours directement dans les nœuds du graphe évite de maintenir un tableau associatif séparé
3) mieux vaut ne pas suivre le chemin résultant à la lettre, mais l’utiliser comme entrée pour un comportement de steering qui coupe les coins pour viser le nœud suivant quand c’est possible. Si le chemin mène à un autre personnage, on peut faire en sorte que la cible laisse des « miettes de pain » et les ajouter au chemin lorsque sa nouvelle position n’est plus accessible en ligne droite depuis le dernier nœud du chemin
2b) je compresse cela en un bitmask 16 bits. Huit segments de 2 bits, donc 8 directions, stockés dans une table de hachage
2c) chaque segment de bits a quatre états : FULL_BLOCK (mur), HARD_BLOCK (gros objet empêchant de traverser la tuile dans n’importe quelle direction), SOFT_BLOCK (petit objet bloquant le passage par un coin), NO_BLOCK (tuile vide ou avec un objet très petit)
Ainsi, lorsqu’une unité cherche un chemin dans un bâtiment, il n’est pas nécessaire de tester les obstacles sur chaque tuile. Si un objet n’est pas massif et que son orientation ne bloque pas les coins d’entrée et de sortie, une tuile occupée par cet objet reste traversable. Enfin, pour éviter que la simulation ne se casse quand le joueur oublie de placer des portes, les agents peuvent aussi traverser les murs
https://store.steampowered.com/app/2287430/Metropolis_1998/
Tant qu’un personnage reste à l’intérieur de cette « bulle », on peut sauter complètement les vérifications de collision avec le monde
À l’université, je ne comprenais pas pourquoi A* était si difficile dans les RTS, mais quand on m’a expliqué que, pour empêcher les unités de se traverser, tout ce qui bouge doit recalculer son chemin en évitant en permanence toutes les autres unités, j’ai encore plus admiré Command & Conquer
À moins d’avoir une raison très solide, personnellement j’éviterais
Pour accélérer une IA de Quoridor écrite en Scala, j’ai beaucoup réfléchi à la recherche de chemin rapide, et voilà ce que j’ai appris
MPAA (Multi-Path Adaptive A*) est utile quand on doit réexplorer plusieurs fois la même zone dans un contexte où des obstacles sont ajoutés. On peut réinjecter les résultats précédents pour accélérer la recherche de chemin
JPS (Jump Point Search) est théoriquement séduisant car il réduit fortement le nombre de « nœuds » à considérer, mais le surcoût de recherche des jump points annulait tout gain réel de performance. Il y a peut-être moyen de combiner les idées de MPAA et de JPS, mais dès qu’on commence à bricoler créativement les algorithmes, on se fait vite piéger par de petits détails conceptuels. Par exemple, utiliser
>au lieu de>=quand>=est nécessaire peut faire perdre la garantie du véritable plus court chemin dans certaines situationsPour stocker les nœuds ouverts, au lieu d’un tas classique, si la priorité maximale est un entier relativement petit, on peut aussi envisager une file de priorité à buckets. Comme le tableau interne est indexé par priorité, les insertions et extractions peuvent être assez rapides
Quoridor se joue sur une grille 9x9, et la recherche de chemin répétée est indispensable pour évaluer à quel point un joueur est proche de son objectif et s’il peut l’atteindre. Pour déterminer les coups possibles depuis une position donnée, il faut vérifier qu’aucun coup ne rend l’objectif inatteignable. Je prévois de publier cela dans quelques mois, avec au moins 3 « moteurs » de décision : mtdf (variante de minimax), MCTS (version parallèle avec quelques astuces) et un hybride mêlant catboost
Ce qui est bien, c’est qu’on peut utiliser cela comme table de consultation pour la fonction heuristique, au lieu d’une simple distance en ligne droite. Par exemple, au début de chaque tour, on peut initialiser cette table avec l’algorithme de Floyd-Warshall pour refléter les murs déjà posés. Sur un problème similaire, cette technique a nettement accéléré A* tout en restant très simple. En revanche, c’était du pur A*, sans MPAA ni JPS
Il y a plusieurs années, j’ai ajouté à l’implémentation JPS de PathFinding.js une fonctionnalité qui visualise la recherche récursive des jump nodes. La démo en ligne est ici : https://qiao.github.io/PathFinding.js/visual/
S’il y a plus d’un ennemi, il peut être plus avantageux, du point de vue du joueur, de lancer simplement Dijkstra une fois, puis de laisser chaque monstre consulter son chemin optimal jusqu’au joueur
Le coût de calcul devient alors plus prévisible quand le nombre de monstres varie
Le problème de profondeur trop faible dans la dernière animation semble produire un comportement intéressant. On dirait que le monstre « attend pour voir de quel côté tu vas aller »
Est-ce qu’on ne pourrait pas aussi le tromper en faisant semblant d’aller d’un côté avant de changer de direction ? Heureusement, les humains sont assez indulgents avec ce genre de choses, et semblent modéliser à peu près tout comme si c’était intelligent
En gros, il suffirait que l’ennemi ne mette à jour son chemin qu’après un court délai au lieu de le faire à chaque frame. Il suivrait alors son ancien chemin par « inertie », ce qui permettrait au joueur de le berner
Comme utilisation intéressante de A* dans un contexte de jeu, il y avait un programmeur qui devait créer des adversaires contrôlés par ordinateur pour un jeu du début des années 2000
Il avait abstrait les choix disponibles pour l’IA dans le jeu, puis lui faisait chercher avec A* la distance la plus courte dans ce graphe. Ce qui était élégant, c’est que ce n’était pas l’usage traditionnel de recherche de chemin dans le monde, mais une recherche de chemin sur une représentation des choix que l’ordinateur pouvait faire, où le plus court chemin représentait la meilleure stratégie possible
0 - https://www.gamedeveloper.com/design/building-the-ai-of-f-e-...
1 - https://web.archive.org/web/20230804100329/https://alumni.me...
Il y a aussi des ressources de référence (pas les miennes) : https://github.com/agoose77/goap-resources
Les humains semblent considérer qu’eux-mêmes et les autres humains emploient des schémas de pensée similaires, avec une profondeur de réflexion comparable, pour des activités pourtant très différentes comme planifier un itinéraire, évaluer un risque face à une récompense, ou organiser un événement dans 6 mois. Si l’on peut encoder divers « espaces de recherche » sous forme de graphes adaptés à un algorithme commun, alors, en plein état d’immersion pendant une partie, il devient plausible que l’IA paraisse réfléchie, presque comme une personne
À l’époque où j’apprenais A* à l’université, j’ai rencontré en même temps ce problème étrange sur un serveur Minecraft public
Le serveur laggait énormément et, en lançant un profilage, on a découvert que des zombies étaient coincés dans une boucle de recherche de chemin pour essayer d’entrer dans un village complètement bloqué par une grande clôture. Cela signifiait que l’implémentation de l’époque était naïve au point de ne jamais abandonner
Il me semble qu’il y avait un rapport de bug assez détaillé expliquant comment corriger ça
Cela pouvait avoir un effet très visible sur les fps, en particulier lorsque plusieurs animaux essayaient tous de franchir un passage impossible. Cela dit, si on voit ça comme un comportement de chat extrêmement obstiné à vouloir passer une porte fermée, on pourrait dire que c’est très réaliste. Ce serait encore plus réaliste si, dès qu’on ouvrait la porte, le chat changeait immédiatement d’avis et perdait tout intérêt à passer !
Un article sur les systèmes multi-agents utilisant A* en terrain inconnu pourrait aussi vous intéresser : https://www.researchgate.net/publication/333917261_Implement...
Il y a de bonnes astuces dans cet article et dans le fil HN. Je n’ai pas encore souvent eu l’occasion d’utiliser A*, mais je sais qu’il existe une bonne bibliothèque Haskell : https://hackage.haskell.org/package/astar-monad-0.3.0.0#read...