Forums Développement Multimédia

Les formations Mediabox
Les formations Mediabox

Annexe : Le Pathfinding - L'A* en JavaScript

Par gnicos (Nicolas Gauville), le 26 août 2012
Navigation rapide : Sommaire

Rappel : Ceci est une annexe du cours sur les jeux isométriques en HTML5/JS.

Ce cours se base sur les chapitres “pas à pas”, et utilise les fichiers fournis à la fin du huitième chapitre :

Jeu entier (incluant les dossiers “www” et “dev”) : jeu.zip

Moteur isométrique (dossier “dev/src” uniquement) : moteur_iso.zip

A l'inverse, ce cours ne se base pas sur les autres annexes.

Introduction

Le Pathfinding permet de trouver un chemin entre deux points dans un tableau. C'est l'une des grosses difficultés des jeux isométriques lorsqu'ils se jouent à la souris. Nous allons donc devoir passer par le Pathfinding pour pouvoir permettre l'utilisation de la souris ou l'adaptation de notre jeu pour tablette tactile. Ce tutoriel permettra ainsi aux débutants comme aux confirmés de voir simplement comment mettre en place un algorithme de Pathfinding.

I. Fonctionnement de l'A*

L'algorithme de Pathfinding que nous allons utiliser est l'A*. La raison est simple : il existe déjà un tutoriel très intéressant sur cet algorithme. Ce tutoriel concerne l'ActionScript 3, mais la première partie, théorique, nous concerne également.

Pour l'apprentissage du fonctionnement de cet algorithme, je vais donc vous renvoyer vers ce tutoriel. Dans la suite de ce tutoriel, nous allons donc utiliser cet algorithme, mais, cette fois, en JavaScript !

  1. - L'algorithme A* - théorie (tutoriel de Thoutmosis, lecture vivement recommandée)

Une fois que vous avez compris le fonctionnement, nous pouvons passer au code !

II. La classe Node

Pour commencer, nous allons créer une classe “Node” définissant un point du tableau, soit l'équivalent d'une tuile, mais destiné, cette fois, à la recherche pour l'algorithme de Pathfinding. Cette classe sera très simple.

Structure de la classe Node

Constructeur Node ( int $x, int $y, bool $walkable )

Crée une nouvelle node. La position est définie par $x et $y, et $walkable défini la possibilité d'accéder à la node (tout comme c'est le cas pour les tuiles).

int g, int h, int f

Valeurs G, H, F nécessaires à l'algorithme.

int line, int col

Ligne et colonne, équivalentes à x et y.

bool walkable

Possibilité d'accéder à la node pour le joueur.

Node parent

Propriété nécessaire à l'algorithme.

Création de la classe

Vous pouvez donc créer un nouveau fichier “src/node.js” dans laquelle nous allons créer la classe node. Pensez également à ajouter ce fichier au fichier “index.html”.

Nous commençons par définir la classe, comme nous le faisions pour les classes Tile, Map, …

/**
 * Class Node
 * int $x : Position en x.
 * int $y : Position en y.
 * bool $walkable : Possibilité d'accéder à la node.
 */
var Node = function ( $x, $y, $walkable )
{
        this.construct ( $x, $y, $walkable );
};

De la même façon, nous définissons également un variable “p”, pour accéder facilement au prototype :

var p = Node.prototype;

Nous pouvons alors définir les propriétés de la classe :

/**
 * int g
 */
p.g = 0;
 
/**
 * int h
 */
p.h = 0;
 
/**
 * int f
 */
p.f = 0;
 
/**
 * int col
 */
p.col = 0;
 
/**
 * int line
 */
p.line = 0;
 
/**
 * bool walkable
 */
p.walkable = true;
 
/**
 * Node parent
 */
p.parent = null;

Nous définissons enfin le constructeur. Notez que la propriété “parent” est associée à la node elle même par défaut.

/**
 * Constructeur.
 */
p.construct = function ( $x, $y, $walkable )
{
        this.line = $x;
        this.col = $y;
        this.walkable = $walkable;
        this.parent = this;
};

Notre classe Node est alors prête ! Voici le code total :

/**
 * Class Node
 * int $x : Position en x.
 * int $y : Position en y.
 * bool $walkable : Possibilité d'accéder à la node.
 */
var Node = function ( $x, $y, $walkable )
{
        this.construct ( $x, $y, $walkable );
};
 
var p = Node.prototype;
 
/**
 * int g
 */
p.g = 0;
 
/**
 * int h
 */
p.h = 0;
 
/**
 * int f
 */
p.f = 0;
 
/**
 * int col
 */
p.col = 0;
 
/**
 * int line
 */
p.line = 0;
 
/**
 * bool walkable
 */
p.walkable = true;
 
/**
 * Node parent
 */
p.parent = null;
 
/**
 * Constructeur.
 */
p.construct = function ( $x, $y, $walkable )
{
        this.line = $x;
        this.col = $y;
        this.walkable = $walkable;
        this.parent = this;
};

III. La classe Pathfinder

Cette fois, sa se complique, avec la classe Pathfinder ! Nous allons commencer par voir sa structure, et coder les méthode “utilitaires”. Enfin, quand tout ceci sera prêt, nous coderons l'algorithme !

Structure de la classe Pathfinder

int NODE_DISTANCE_VALUE

Valeur d'un déplacement entre deux nodes adjacentes. Nous choisirons 100.

array openList

Liste ouverte.

array closeList

Liste fermée.

Array findPath ( Array $graph, Node $start, Node $end )

Fonction permettant de trouver un chemin, nous créerons cette fonction dans la prochaine partie. $graph désigne le tableau de node, $start et $end les deux nodes à relier.

void removeFromCloseList ( Node $node )

Méthode permettant de supprimer une node de la liste fermée.

void removeFromOpenList ( Node $node )

Méthode permettant de supprimer une node de la liste ouverte.

void addToCloseList ( Node $node )

Méthode pour ajouter une node dans la liste fermée.

void addToOpenList ( Node $node )

Méthode pour ajouter une node dans la liste ouverte.

Node getCurrentNode ()

Méthode pour récupérer la node courante (c'est à dire la node de la liste ouverte ayant la valeur “f” la plus petite.

Array getNeighbours ( Node $node, Array $graph )

Méthode permettant de récupérer les tuiles voisines à une tuile (soit 0 à 4 tuiles, ou 0 à 8 tuiles, selon le nombre de directions).

bool isOnOpenList ( Node $node )

Méthode permettant de savoir si la node “$node” est dans la liste ouverte.

bool isOnCloseList ( Node $node )

Méthode permettant de savoir si la node “$node” est dans la liste fermée.

Création de la structure de la classe

Nous allons donc, maintenant, coder cette classe. Cette classe n'ayant aucun besoin d'être instanciée, nous la structurerons comme un simple objet, comme nous l'avions fait pour la classe “TileType” (ou encore “PNGMapLoader”, “JSONMapLoader” ou “XMLMapLoader” pour ceux qui ont lu ces annexes).

Nous avons donc la structure suivante :

/**
 * IA Pathfinder
 */
var Pathfinder =
{
        /**
         * int NODE_DISTANCE_VALUE : valeur d'un déplacement entre deux nodes adjacentes.
         */
        NODE_DISTANCE_VALUE: 100,
 
        /**
         * Array m_openList : liste ouverte.
         */
        openList: null,
 
        /**
         * Array m_closeList : liste fermée.
         */
        closeList: null,
 
        /**
         * Fonction findPath.
         * Array $graph : Graphe.
         * Node $start : Node de départ.
         * Node $end : Node d'arrivée.
         */
        findPath: function ( $graph, $start, $end )
        {
        },
 
        /**
         * Function removeFromCloseList
         * Node $node : node à supprimer de la liste fermée.
         */
        removeFromCloseList: function ( $node )
        {
        },
 
        /**
         * Function removeFromOpenList
         * Node $node : node à supprimer de la liste ouverte.
         */
        removeFromOpenList: function ( $node )
        {
        },
 
        /**
         * Function addToCloseList
         * Node $node : node à ajouter à la liste fermée.
         */
        addToCloseList: function ( $node )
        {
        },
 
        /**
         * Function addToOpenList
         * Node $node : node à ajouter à la liste ouverte.
         */
        addToOpenList: function ( $node )
        {
        },
 
        /**
         * Function getCurrentNode
         */
        getCurrentNode: function ()
        {
        },
 
        /**
         * Function getNeighbours
         * Node $node : Node pour laquelle il faut chercher les voisins.
         * Array $graph : Graphe dans lequel il faut chercher.
         */
        getNeighbours: function ( $node, $graph )
        {
        },
 
        /**
         * Function isOnOpenList
         * Node $node : Node à chercher dans la liste ouverte.
         */
        isOnOpenList: function ( $node )
        {
        },
 
        /**
         * Function isOnCloseList
         * Node $node : Node à chercher dans la liste fermée.
         */
        isOnCloseList: function ( $node )
        {
        }
};

Maintenant, nous allons coder toutes ces méthodes !

removeFromCloseList

Une première méthode toute simple. Cette méthode sert simplement à supprimer une node de la liste fermée, elle fonctionnera donc de la même façon que la méthode “removeTile” de la classe Map.

On commence par chercher l'index de la node à supprimer :

var index = this.closeList.indexOf ( $node );

Puis, si l'index est différent de ”-1” (valeur renvoyée si la node ne fait pas partie du tableau), on la supprime du tableau.

if ( index !== -1 )
{
        this.closeList.splice ( index, 1 );
}

La fonction est alors définie ainsi :

/**
 * Function removeFromCloseList
 * Node $node : node à supprimer de la liste fermée.
 */
removeFromCloseList: function ( $node )
{
        var index = this.closeList.indexOf ( $node );
 
        if ( index !== -1 )
        {
                this.closeList.splice ( index, 1 );
        }
},

removeFromOpenList

Ici, fonction identique à la précédente, sauf qu'elle concerne cette fois la liste ouverte. On a donc le code suivant :

/**
 * Function removeFromOpenList
 * Node $node : node à supprimer de la liste ouverte.
 */
removeFromOpenList: function ( $node )
{
        var index = this.openList.indexOf ( $node );
 
        if ( index !== -1 )
        {
                this.openList.splice ( index, 1 );
        }
},

addToCloseList

Une méthode pour ajouter une node à la liste fermée. On utilise donc simplement la méthode “push” de la classe Array. Nous supprimerons tout de même la node de la liste ouverte avant (inutile de vérifier si elle en fait partie, la méthode “removeFromOpenList le fera) :

/**
 * Function addToCloseList
 * Node $node : node à ajouter à la liste fermée.
 */
addToCloseList: function ( $node )
{
        this.removeFromOpenList ( $node );
        this.closeList.push ( $node );
},

addToOpenList

Une autre méthode pour ajouter à la liste ouverte, encore une fois, elle est presque identique à la méthode précédente :

/**
 * Function addToOpenList
 * Node $node : node à ajouter à la liste ouverte.
 */
addToOpenList: function ( $node )
{
        this.removeFromCloseList ( $node );
        this.openList.push ( $node );
},

getCurrentNode

La méthode “getCurrentNode” doit renvoyer la node, qui, dans la liste ouverte, a la plus petite valeur “f”. Nous allons donc définir une valeur “f” par défaut (assez grande) :

var min_f = 1000000;
var current_node = null;

Ensuite, nous parcourons toutes les tuiles de la liste ouverte, vérifiant à chaque fois si la tuile en cours à une valeur inférieure à celle trouvée, si c'est le cas, on la définit comme courante. Une fois la boucle terminée, la variable “current_node” sera alors la node voulue.

/**
 * Function getCurrentNode
 */
getCurrentNode: function ()
{
        var min_f = 1000000;
        var current_node = null;
 
        for ( var i = 0, max = this.openList.length; i < max; ++i )
        {
                var node = this.openList[i];
 
                if ( node.f < min_f )
                {
                        min_f = node.f;
                        current_node = node;
                }
        }
        return current_node;
},

getNeighbours

Cette méthode doit définir les nodes voisines d'une node. Ils sont au nombre de 4 ou 8 selon le nombre de directions, sauf si la node est à l'une des extrémités du graphe. Nous allons donc créer un Array pour contenir les voisins :

var neighbours = [];

Ensuite, nous ajoutons les quatre voisins, à conditions qu'ils existent !

if ( $node.line > 0 )
{
        neighbours.push ( $graph[$node.line - 1][$node.col] );
}
 
if ( $node.line + 1 < $graph.length )
{
        neighbours.push ( $graph[$node.line + 1][$node.col] );
}
 
if ( $node.col > 0 )
{
        neighbours.push ( $graph[$node.line][$node.col - 1] );
}
 
if ( $node.col + 1 < $graph[0].length )
{
        neighbours.push ( $graph[$node.line][$node.col + 1] );
}

Et nous renvoyons les voisins trouvés :

return neighbours;

Nous avons donc la méthode suivante :

/**
 * Function getNeighbours
 * Node $node : Node pour laquelle il faut chercher les voisins.
 * Array $graph : Graphe dans lequel il faut chercher.
 */
getNeighbours: function ( $node, $graph )
{
        var neighbours = [];
 
        if ( $node.line > 0 )
        {
                neighbours.push ( $graph[$node.line - 1][$node.col] );
        }
 
        if ( $node.line + 1 < $graph.length )
        {
                neighbours.push ( $graph[$node.line + 1][$node.col] );
        }
 
        if ( $node.col > 0 )
        {
                neighbours.push ( $graph[$node.line][$node.col - 1] );
        }
 
        if ( $node.col + 1 < $graph[0].length )
        {
                neighbours.push ( $graph[$node.line][$node.col + 1] );
        }
 
        return neighbours;
},

isOnOpenList

Cette méthode doit indiquer si la node demandée appartient à la liste ouverte. Il suffit donc de savoir si son index (renvoyé par la méthode Array.indexOf) est différent de ”-1” ou non :

/**
 * Function isOnOpenList
 * Node $node : Node à chercher dans la liste ouverte.
 */
isOnOpenList: function ( $node )
{
        return ( this.openList.indexOf ( $node ) !== -1 );
},

isOnCloseList

Encore une fois, méthode identique à la précédente, sur la liste fermée cette fois ci :

/**
 * Function isOnCloseList
 * Node $node : Node à chercher dans la liste fermée.
 */
isOnCloseList: function ( $node )
{
        return ( this.closeList.indexOf ( $node ) !== -1 );
}

Nous pouvons alors passer à l'algorithme !

IV. Algorithme

Notre algorithme (A*) sera donc contenu dans la méthode “findPath” de la classe Pathfinding. C'est donc cette méthode que nous allons maintenant coder.

On commence simplement par créer les listes :

/**
 * Initialisation des listes.
 */
this.openList = [];
this.closeList = [];

Nous allons également définir deux autres variables : “currentNode” pour la node courante, et “finalPath” pour le chemin trouvé :

/**
 * Variable destinée à accueillir le chemin final.
 */
var finalPath = [];
 
 /**
  * Node courante.
  */
var currentNode = null;

Et … nous pouvons alors passer à l'algorithme ! Première étape : on ajoute la node de départ à la liste ouverte.

/**
 * Algo :
 * On ajoute la node de départ à la liste ouverte.
 */
this.addToOpenList( $start );

Ensuite, on boucle jusqu'à ce que la liste ouverte soit vide. On s'intéresse alors à la node ayant le plus petit “f” dans la liste ouverte :

while ( this.openList.length > 0 )
{
        /**
         * On boucle jusqu'à ce que la liste ouverte soit vide.
         * On récupère la node avec le plus petit F, avec la méthode "getCurrentNode".
         */
        currentNode = this.getCurrentNode ();
 
        // ...
        // ...
}

Nous commençons par vérifier que “currentNode” n'est pas la node d'arrivée. Si c'est le cas, c'est que le chemin à été trouvé, que nous nous pouvons arrêter la boucle.

/**
 * Si "currentNode" est la node d'arrivée, on arrête.
 */
if ( currentNode === $end )
{
        break;
}

Sinon, on bascule “currentNode” sur la liste fermée, et on cherche ses voisins :

/**
 * On bascule "currentNode" dans la liste fermée.
 */
this.addToCloseList ( currentNode );
 
/**
 * Récupération des voisins de "currentNode".
 */
var neighbours = this.getNeighbours ( currentNode, $graph );

Nous allons alors analyser les voisins de currentNode, avec une boucle for :

/**
 * On examine les voisins de "currentNode".
 */
for ( var i = 0, max = neighbours.length; i < max; ++i )
{
        var node = neighbours[i];
 
        //...
        //...
}

Première chose : vérifier que le voisin (node) n'est pas dans la liste fermée, et n'est pas un obstacle. Si c'est le cas, on l'ignore. Sinon, on calcule les nouvelles valeurs “F”, “G”, et “H” :

  1. - Pour G : c'est la distance depuis le point de départ. On récupère donc la valeur “G” de la node parente, à laquelle on ajoute la valeur de “NODE_DISTANCE_VALUE”.
  2. - Pour H : c'est la distance entre la node courante et la node d'arrivée, à vol d'oiseau. On soustrait donc, coordonnée à coordonnée, les coordonnées de la node courante à celle de la node d'arrivée. On multiplie le tout par “NODE_DISTANCE_VALUE” pour obtenir un résultat homogène à la variable G.
  3. - Pour F : on additionne G et H.
/**
 * Si la node est dans la liste fermée, où est un obstacle, on l'ignore.
 */
 if ( !(this.isOnCloseList( node ) || node.walkable === false) )
 {
       /**
        * Sinon, on continue.
        * On calcule les nouvelles valeurs de g, h et f.
        */
        var newG=node.parent.g + this.NODE_DISTANCE_VALUE;
        var newH=(Math.abs($end.line-node.line)+Math.abs($end.col-node.col))*this.NODE_DISTANCE_VALUE;
        var newF=newH+newG;
 
        //...
        //...
}

Si la node est déjà dans la liste ouverte :

  1. - On compare la nouvelle valeur de g à l'anciène,
  2. - Si elle est inférieure, on met à jour f, g et h, et on fait de currentNode son parent.
if ( this.isOnOpenList( node ) )
{
        /**
         * Si la node est déjà dans la liste ouverte :
         * On compare la nouvelle valeur de g à l'anciène,
         * Si elle est inférieure, on met à jour f, g et h,
         * et on fait de currentNode son parent.
         */
        if ( newG < node.g )
        {
                node.g = newG;
                node.h = newH;
                node.f = newF;
                node.parent = currentNode;
        }
}

Si la node n'est pas dans la liste ouverte :

  1. - On fait de currentNode son parent.
  2. - On met à jour f, g et h.
  3. - On ajoute la node à la liste ouverte.
else
{
        /**
         * Si la node n'est pas dans la liste ouverte :
         * On fait de currentNode son parent.
         * On met à jour f, g et h.
         * On ajoute la node à la liste ouverte.
         */
        node.g = newG;
        node.h = newH;
        node.f = newF;
        node.parent = currentNode;
        this.addToOpenList ( node );
}

Norte grande boucle est alors terminée, nous allons donc maintenant nous intéresser à l'issue de cette boucle. Deux cas sont possibles. Soit la boucle s'est arrêtée parce que la liste ouverte est vide : dans ce cas, il n'y a pas de solution. Soit la boucle s'est arrêtée parce que la node d'arrivée à été trouvée (renvoyée par “getCurrentNode”), et, dans ce cas, la solution à été trouvée.

Si la liste ouverte est vide, on renvoie directement finalPath (qui est un array vide) :

/**
 * La boucle s'est arrêtée.
 * Deux solution :
 * - Soit la liste ouverte est vide, donc il n'y a pas de solution :
 * - Soit la liste ouverte n'est pas vide, donc le résultat a été trouvé.
 */
if ( this.openList.length === 0 )
{
        return finalPath;
}

Sinon, on refait le chemin à l'envers pour remplir “finalPath”, grâce aux propriétés “parent” :

/**
 * Il y a une solution :
 * On doit refaire le chemin à l'envers.
 */
var lastNode = $end;
while ( lastNode !== $start )
{
        finalPath.push ( lastNode );
        lastNode = lastNode.parent;
}
 
return finalPath.reverse();

Notre classe “Pathfinder” est donc terminée et prête à l'emploi ! Nous n'avons plus qu'à adapter notre moteur isométrique pour qu'il sache s'en servir !

Voici le code final du fichier “Pathfinder.js” :

/**
 * IA Pathfinder
 */
var Pathfinder =
{
        /**
         * int NODE_DISTANCE_VALUE : valeur d'un déplacement entre deux nodes adjacentes.
         */
        NODE_DISTANCE_VALUE: 100,
 
        /**
         * Array m_openList : liste ouverte.
         */
        openList: null,
 
        /**
         * Array m_closeList : liste fermée.
         */
        closeList: null,
 
        /**
         * Fonction findPath.
         * Array $graph : Graphe.
         * Node $start : Node de départ.
         * Node $end : Node d'arrivée.
         */
        findPath: function ( $graph, $start, $end )
        {
                /**
                 * Initialisation des listes.
                 */
                this.openList = [];
                this.closeList = [];
 
                /**
                 * Variable destinée à accueillir le chemin final.
                 */
                var finalPath = [];
 
                 /**
                  * Node courante.
                  */
                var currentNode = null;
 
                /**
                 * Algo :
                 * On ajoute la node de départ à la liste ouverte.
                 */
                this.addToOpenList( $start );
 
                while ( this.openList.length > 0 )
                {
                        /**
                         * On boucle jusqu'à ce que la liste ouverte soit vide.
                         * On récupère la node avec le plus petit F, avec la méthode "getCurrentNode".
                         */
                        currentNode = this.getCurrentNode ();
 
                        /**
                         * Si "currentNode" est la node d'arrivée, on arrête.
                         */
                        if ( currentNode === $end )
                        {
                                break;
                        }
 
                        /**
                         * On bascule "currentNode" dans la liste fermée.
                         */
                        this.addToCloseList ( currentNode );
 
                        /**
                         * Récupération des voisins de "currentNode".
                         */
                        var neighbours = this.getNeighbours ( currentNode, $graph );
 
                        /**
                         * On examine les voisins de "currentNode".
                         */
                        for ( var i = 0, max = neighbours.length; i < max; ++i )
                        {
                                var node = neighbours[i];
 
                                /**
                                 * Si la node est dans la liste fermée, où est un obstacle, on l'ignore.
                                 */
                                 if ( !(this.isOnCloseList( node ) || node.walkable === false) )
                                 {
                                       /**
                                        * Sinon, on continue.
                                        * On calcule les nouvelles valeurs de g, h et f.
                                        */
                                        var newG=node.parent.g + this.NODE_DISTANCE_VALUE;
                                        var newH=(Math.abs($end.line-node.line)+Math.abs($end.col-node.col))*this.NODE_DISTANCE_VALUE;
                                        var newF=newH+newG;
 
                                        if ( this.isOnOpenList( node ) )
                                        {
                                                /**
                                                 * Si la node est déjà dans la liste ouverte :
                                                 * On compare la nouvelle valeur de g à l'anciène,
                                                 * Si elle est inférieure, on met à jour f, g et h,
                                                 * et on fait de currentNode son parent.
                                                 */
                                                if ( newG < node.g )
                                                {
                                                        node.g = newG;
                                                        node.h = newH;
                                                        node.f = newF;
                                                        node.parent = currentNode;
                                                }
                                        }
                                        else
                                        {
                                                /**
                                                 * Si la node n'est pas dans la liste ouverte :
                                                 * On fait de currentNode son parent.
                                                 * On met à jour f, g et h.
                                                 * On ajoute la node à la liste ouverte.
                                                 */
                                                node.g = newG;
                                                node.h = newH;
                                                node.f = newF;
                                                node.parent = currentNode;
                                                this.addToOpenList ( node );
                                        }
                                 }
 
                        }
                 }
 
                /**
                 * La boucle s'est arrêtée.
                 * Deux solution :
                 * - Soit la liste ouverte est vide, donc il n'y a pas de solution :
                 * - Soit la liste ouverte n'est pas vide, donc le résultat a été trouvé.
                 */
                if ( this.openList.length === 0 )
                {
                        return finalPath;
                }
 
                /**
                 * Il y a une solution :
                 * On doit refaire le chemin à l'envers.
                 */
                var lastNode = $end;
                while ( lastNode !== $start )
                {
                        finalPath.push ( lastNode );
                        lastNode = lastNode.parent;
                }
 
                return finalPath.reverse();
        },
 
        /**
         * Function removeFromCloseList
         * Node $node : node à supprimer de la liste fermée.
         */
        removeFromCloseList: function ( $node )
        {
                var index = this.closeList.indexOf ( $node );
 
                if ( index !== -1 )
                {
                        this.closeList.splice ( index, 1 );
                }
        },
 
        /**
         * Function removeFromOpenList
         * Node $node : node à supprimer de la liste ouverte.
         */
        removeFromOpenList: function ( $node )
        {
                var index = this.openList.indexOf ( $node );
 
                if ( index !== -1 )
                {
                        this.openList.splice ( index, 1 );
                }
        },
 
        /**
         * Function addToCloseList
         * Node $node : node à ajouter à la liste fermée.
         */
        addToCloseList: function ( $node )
        {
                this.removeFromOpenList ( $node );
                this.closeList.push ( $node );
        },
 
        /**
         * Function addToOpenList
         * Node $node : node à ajouter à la liste ouverte.
         */
        addToOpenList: function ( $node )
        {
                this.removeFromCloseList ( $node );
                this.openList.push ( $node );
        },
 
        /**
         * Function getCurrentNode
         */
        getCurrentNode: function ()
        {
                var min_f = 1000000;
                var current_node = null;
 
                for ( var i = 0, max = this.openList.length; i < max; ++i )
                {
                        var node = this.openList[i];
 
                        if ( node.f < min_f )
                        {
                                min_f = node.f;
                                current_node = node;
                        }
                }
                return current_node;
        },
 
        /**
         * Function getNeighbours
         * Node $node : Node pour laquelle il faut chercher les voisins.
         * Array $graph : Graphe dans lequel il faut chercher.
         */
        getNeighbours: function ( $node, $graph )
        {
                var neighbours = [];
 
                if ( $node.line > 0 )
                {
                        neighbours.push ( $graph[$node.line - 1][$node.col] );
                }
 
                if ( $node.line + 1 < $graph.length )
                {
                        neighbours.push ( $graph[$node.line + 1][$node.col] );
                }
 
                if ( $node.col > 0 )
                {
                        neighbours.push ( $graph[$node.line][$node.col - 1] );
                }
 
                if ( $node.col + 1 < $graph[0].length )
                {
                        neighbours.push ( $graph[$node.line][$node.col + 1] );
                }
 
                return neighbours;
        },
 
        /**
         * Function isOnOpenList
         * Node $node : Node à chercher dans la liste ouverte.
         */
        isOnOpenList: function ( $node )
        {
                return ( this.openList.indexOf ( $node ) !== -1 );
        },
 
        /**
         * Function isOnCloseList
         * Node $node : Node à chercher dans la liste fermée.
         */
        isOnCloseList: function ( $node )
        {
                return ( this.closeList.indexOf ( $node ) !== -1 );
        }
};

Conclusion

Nous avons ainsi pu réécrire l'algorithme A* en JavaScript. Vous pouvez remarquer que si l'algorithme est un peu complexe, sa mise en place en JavaScript est relativement simple. Nous verrons, par la suite, comment l'implémenter dans le moteur isométrique.

Navigation rapide : Sommaire