Pathfinding : programmer les déplacements des personnages
CHAPITRE 9
187
pratiques en matière d’optimisation d’algorithmes, l’Internet fourmille d’articles à ce
sujet, consultez-les.
L’algorithme A* : compromis entre performance et pertinence
Dans cette section, nous allons nous pencher sur le fonctionnement de l’algorithme et
verrons un exemple d’utilisation. Vous serez ainsi capable de l’utiliser dans vos jeux.
Principe de l’algorithme
Nous allons à présent travailler sur une carte représentant le niveau d’un jeu. Chaque case
qui constitue la carte est appelée nœud. Le point de départ sera symbolisé par une case
verte et le point d’arrivée, par une case rouge. Les cases blanches symbolisent des cases
classiques, franchissables sans effort particulier. Les cases bleues symbolisent l’eau et sont
plus difficiles à franchir que les cases classiques. Enfin, les cases grises symbolisent des
murs parfaitement infranchissables. La figure 9-1 donne un exemple de ce type de carte.
Le travail de recherche de chemin s’effectue grâce à deux listes de nœuds :
• une liste ouverte, qui contient les nœuds susceptibles de conduire le joueur au nœud de
destination, c’est-à-dire les nœuds à vérifier ;
• et une liste fermée, contenant les nœuds déjà traités qui composeront le chemin final.
Intéressons-nous d’abord à la première phase de l’algorithme.
Commencez par ajouter le point de départ à la liste fermée, puisque la solution passera
forcément par lui. Intéressez-vous ensuite à tous les points voisins de ce point de départ
et ajoutez-les également à la liste ouverte, tout en ignorant ceux qui sont infranchissables
(les murs dans notre exemple).
Figure 9-1
Le type de carte qui sera
utilisé
=Labat FM.book Page 187 Vendredi, 19. juin 2009 4:01 16
CHAPITRE 9
187
pratiques en matière d’optimisation d’algorithmes, l’Internet fourmille d’articles à ce
sujet, consultez-les.
L’algorithme A* : compromis entre performance et pertinence
Dans cette section, nous allons nous pencher sur le fonctionnement de l’algorithme et
verrons un exemple d’utilisation. Vous serez ainsi capable de l’utiliser dans vos jeux.
Principe de l’algorithme
Nous allons à présent travailler sur une carte représentant le niveau d’un jeu. Chaque case
qui constitue la carte est appelée nœud. Le point de départ sera symbolisé par une case
verte et le point d’arrivée, par une case rouge. Les cases blanches symbolisent des cases
classiques, franchissables sans effort particulier. Les cases bleues symbolisent l’eau et sont
plus difficiles à franchir que les cases classiques. Enfin, les cases grises symbolisent des
murs parfaitement infranchissables. La figure 9-1 donne un exemple de ce type de carte.
Le travail de recherche de chemin s’effectue grâce à deux listes de nœuds :
• une liste ouverte, qui contient les nœuds susceptibles de conduire le joueur au nœud de
destination, c’est-à-dire les nœuds à vérifier ;
• et une liste fermée, contenant les nœuds déjà traités qui composeront le chemin final.
Intéressons-nous d’abord à la première phase de l’algorithme.
Commencez par ajouter le point de départ à la liste fermée, puisque la solution passera
forcément par lui. Intéressez-vous ensuite à tous les points voisins de ce point de départ
et ajoutez-les également à la liste ouverte, tout en ignorant ceux qui sont infranchissables
(les murs dans notre exemple).
Figure 9-1
Le type de carte qui sera
utilisé
=Labat FM.book Page 187 Vendredi, 19. juin 2009 4:01 16