INTELLIGENCE ARTIFICIELLE
1
420-J32-BB
Aujourd'hui
• Génération de comportements : recherche de chemin (pathfinding)
• A*
• Recherche de chemin++
Graphes
• En résumé :
• Dijkstra et A* sont des algorithmes gloutons de plus court chemin;
• A* généralise Dijkstra en ajoutant une heuristique qui accélère la
recherche, tout en restant optimal si cette heuristique est admissible.
Demo
?
1
1
Pathfinding
• Pour déterminer un chemin du point A au point B
à l'aide d'un algorithme de recherche,
l'environnement de jeu doit être partitionné en
une structure de données que les algorithmes
peuvent explorer : un graphe de navigation.
• Il existe de nombreuses façons de représenter la
géométrie qui compose un environnement de jeu:
• Jeux de tuiles ou de cellules (tile- or cell-based
games)
• Graphe de navigation par points de visibilité
(POV)
• Géométrie étendue (expanded geometry)
• Navmesh
Pathfinding
• Tile- or cell-based games
• Différents types de terrains
• RTS et autres jeux de stratégie
• 100x100 => 10K vertices => 78K
edges
Pathfinding
Pathfinding
• Graphe de navigation par points de visibilité (POV)
• Créé en plaçant des nœuds, généralement manuellement, à des points
importants de l'environnement, de sorte que chaque nœud ait une ligne
de vue vers au moins un autre.
• Soigneusement positionnés, les nœuds formeront un graphe reliant toutes
les zones importantes de la géométrie de l'environnement.
Pathfinding
• Géométrie étendue
• Si un environnement est construit à partir
de polygones, il est possible d'utiliser les
informations contenues dans ces formes
pour créer automatiquement un POV, ce
qui, pour les grandes cartes, peut
représenter un gain de temps
considérable.
Pathfinding
• Géométrie étendue
• Ceci est réalisé en commençant par agrandir
les polygones d'une valeur proportionnelle
au bounding box/radius des agents du jeu.
• Les sommets définissant cette géométrie
étendue sont ensuite ajoutés comme nœuds
à un graphe de navigation.
• Enfin, un algorithme est exécuté pour tester
la visibilité entre les sommets, et les arêtes
sont ajoutées au graphe en conséquence.
Pathfinding
• Navmesh
• Représentation de l'environnement en zones “navigables”, plutôt qu’en
cases.
• Il est composé de polygones connectés (souvent convexes) dans lesquels
un agent peut se déplacer librement. La convexité garantit qu’un agent
peut aller d’un point à un autre sans sortir de la zone, ce qui rend le
pilotage beaucoup plus simple et fiable.
• La navigation se fait de polygone en polygone, puis le mouvement est
lissé à l’intérieur des polygones pour obtenir des déplacements naturels.
Pathfinding
• Les navmeshes sont efficaces. La structure
de données nécessaire à leur stockage est
compacte et permet une recherche très
rapide.
• Comme pour POV, lorsque les
environnements sont entièrement construits
à partir de polygones (comme la majorité
des FPS) il est possible d'utiliser des
algorithmes pour générer automatiquement
les navmeshes à partir de la géométrie de
l'environnement.
Pathfinding
• Graphes à maillage grossier (Coarsely Granulated / Grained Graphs)
• Noeuds positionnés manuellement
• Très compact, consomme peu de mémoire
• Si le mouvement est restreint (Pac-Man), cela peut fonctionner.
• Mais quand le mouvement est plus "libre", il y a des limitations
sérieuses.
Pathfinding
• Graphes à maillage fin (Finely
Grained Graphs)
• On peut régler ces 2 problèmes
en augmentant le nombre de
noeuds de notre graphe de
navigation.
Pathfinding
• Utilisation de l'algorithme de remplissage par
propagation (Flood Fill) pour créer un graphe
de navigation
• part d’une cellule de départ
• visite récursivement (ou via pile/queue) tous
les voisins accessibles
• marque chaque cellule visitée
• s’arrête quand il n’y a plus de voisins valides
Pathfinding
• Encore le Spatial Partitioning à la rescousse!
• On cherche souvent le noeud visible le plus proche d'une position.
• Tester chacun des noeuds n'est pas optimal.
Pathfinding
A* Dijkstra
Pathfinding
• Il n'y a pas de différence entre le pathfinding 2D et 3D!
• La verticalité (les sauts) est gérée en ajustant les poids des arêtes.
Pathfinding
• Path Smoothing
• Rough but Quick
• Precise but Slow
Pathfinding
Rough but Quick - Path Smoothing
1. Récupérer la position de départ de l’arête E1.
2. Récupérer la position d’arrivée de l’arête E2.
3. Si l’agent peut se déplacer entre ces deux positions sans être obstrué par la géométrie du monde :
• attribuer à E1 la destination de E2;
• supprimer E2 du chemin;
• réassigner E2 à la nouvelle arête qui suit E1.
• Remarque : il ne s’agit pas d’un simple test de ligne de vue. La taille de l’agent doit être prise en compte, il doit pouvoir se déplacer entre ces
deux positions sans entrer en collision avec les murs.)
4. Si l’agent ne peut pas se déplacer librement entre les deux positions :
• assigner E2 comme successeur immédiat de E1;
• avancer E2 vers l’arête suivante du chemin.
5. Répéter ces étapes jusqu’à ce que la destination de E2 soit égale à la destination finale du chemin.
Pathfinding
Pathfinding
Pathfinding
• Réduire le temps CPU
• Pré-calculer les chemins
• Pré-calculer les coûts
• Répartir le pathfinding sur plusieurs
frames
• Pathfinding hiérarchique
Pathfinding
• Pré-calculer les chemins
Pathfinding
• Pré-calculer les coûts
Pathfinding
• Répartir le pathfinding sur plusieurs frames
• On peut alléger la charge du CPU en allouant une quantité fixe de ressources par frame,
répartie parmi toutes les requêtes de recherche.
• Ceci est réalisé en divisant les recherches sur plusieurs frames, une technique connue sous
le nom de time slicing.
• Cela complexifie le code mais l'effort en vaut la peine pour certains jeux car la charge sur le
CPU devient constante, quel que soit le nombre d'agents effectuant des requêtes.
Pathfinding
• Que fais l'agent pendant ce temps?
Pathfinding
• Pathfinding hiérarchique
Pathfinding
• Retomber sur ses pattes!
Ressources
• [Link]
• PGAI chapitre 8 - Practical Path Planning - page 333
• AIFG chapitre 4 (sections 3 à 4)- Pathfinding - page 195
• [Link]
• [Link] (navmesh)
• [Link]
id=EQYcDAAAQBAJ&printsec=frontcover&redir_esc=y#v=onepage&q&f=false (PCG for
C++ Game Dev)
• [Link]
Au prochain cours
• Backtracking
• Mini-maxing
• Markov