Développement XNA pour la XBox et le PC
196
La classe Pathfinding : implémentation de l’algorithme
Il est temps de passer aux choses sérieuses ! Ajoutez une classe PathFinding au projet et
ajoutez-y une fonction statique qui retourne une liste de Tile. Elle devra recevoir en
argument la carte sur laquelle elle travaillera, ainsi que la case de départ et celle d’arrivée.
La première chose à faire est de déclarer tout ce qui sera utile dans la fonction. Tout d’abord
les collections : il en faut une qui contient la liste de cases pour la sortie de la fonction,
une pour la liste ouverte, une pour la liste fermée et une pour les nœuds voisins à analyser.
Notez enfin qu’une variable contenant le nombre d’éléments de cette dernière liste est
aussi déclarée. Il s’agit là d’une optimisation : l’utilisation d’une boucle for plutôt
qu’une boucle foreach ne requiert pas la création d’un objet pour l’énumération. Ensuite,
au lieu d’appeler à chaque fois la propriété Count, il est préférable de stocker sa valeur
dans une variable. L’optimisation peut être encore plus poussée en employant des tableaux
plutôt que des listes mais, pour ne pas compliquer plus les choses, ce n’est pas le cas ici.
Ensuite, il faut générer le nœud de départ (n’oubliez pas qu’il n’a pas de nœud parent) et
l’ajouter à la liste ouverte.
Le reste de la fonction se contente d’appliquer l’algorithme : retirez le nœud de la liste
ouverte et ajoutez-le à la liste fermée ; si la case du nœud est celle d’arrivée, remontez la
liste fermée et remplissez la liste de sortie de la fonction, sinon inspectez les nœuds
voisins. Si vous sortez de la boucle while, c’est qu’il n’y a plus d’éléments dans la liste
ouverte et qu’il n’existe donc aucune solution ; dans ce cas, retournez null.
La méthode de recherche du plus court chemin
class Pathfinding
{
public static List CalculatePathWithAStar(Map map, Tile startTile, Tile
➥endTile)
{
List result = new List();
NodeList openList = new NodeList();
NodeList closedList = new NodeList();
List possibleNodes;
int possibleNodesCount;
Node startNode = new Node(startTile, null, endTile);
openList.Add(startNode);
while (openList.Count > 0)
{
Node current = openList[0];
openList.RemoveAt(0);
closedList.Add(current);
if (current.Tile == endTile)
{
=Labat FM.book Page 196 Vendredi, 19. juin 2009 4:01 16