Lowlight.fr

Oh, Tu ne manqueras pas d'arriver quelque part, si tu marches assez longtemps, lui répondit le chat du Cheshire.

Alice au pays des merveilles
Lewis Caroll (illustrations de Jun Mochizuki)

Le pathfinding

La recherche de chemins, ou **pathfinding** est un problème récurrent dans le domaine de l'intelligence artificielle, en particulier dans les domaines de la robotique mobile et des jeux vidéo. Il existe une multitude d'algorithmes pour résoudre ce problème °(Backtracking, DFS, Bellman-Ford, etc.)° mais le plus répandu est sans doute l'A*, qui lui-même a engendré moultes variantes de celui-ci (D*, IDA*, SMA*, etc.).

L'**A*** est basé sur l'algorithme de Dijkstra, la seule différence étant la présence d'une fonction **heuristique**. Celle-ci, à condition d'être **admissible** °(i.e. elle ne surévalue jamais le coût entre un certain nœud et le nœud d'arrivé)°, permettra à l'A* de toujours trouver le chemin le plus court en explorant un nombre de nœud réduit.

Cet article consiste en une **présentation** de la bibliothèque lowlighter/astar (documentation) que j'ai réalisé, ainsi que d'une **explication** de l'algorithme **A*** et de l'une de ses variantes, le **Jump Point Search**. En dernier lieu sera abordé le **post-processing**.

Démonstration et exemples de code

Les cases fléchées représentent les noeuds traités par l'algorithme.

Chaque biome possède un certain coût °(les montagnes et forêts étant plus coûteux que les plaines)°, qui n'est pas pris en compte lorsque l'A* JPS est utilisé. Le profil terrestre ne peut pas accéder aux cases maritimes tandis que pour les profils aquatiques, c'est le contraire. Le profil amphibien peut accéder à toutes les cases de la carte.

Diagonales
Couper à travers
Carte torique
Heuristique
Profil
Scores
Jump Point Search
Carte

    //Initialisation
        let map = [], X = 0, Y = 0

    //Création de la carte
        for (let x = 0; x < X; x++) { map[x] = []
            for (let y = 0; y < Y; y++) {
                //Retourne une valeur positive pour les biomes terrestres, négative pour les biomes aquatiques
                    map[x][y] = biome(x, y)
            }
        }

    //Paramétrage des options
        let options = {
            order:"xy",
            diagonals:true,
            cutting:false,
            torus:false,
            heuristic:"euclidian",
            thread:false
        }

    //Nouvelle configuration
    //Il est possible de définir plusieurs couches avec différents paramètres/fonction de coût avec une même carte
    //n désigne la cellule de départ et m celle d'arrivée
        let astar = new Lowlight.Astar.Configuration(map,
            $.extend({cost(n, m) { return m >= 0 ? m : null }}, options), //Terrestre
            $.extend({cost(n, m) { return m < 0 ? -m : null }}, options), //Aquatic
            $.extend({cost(n, m) { return Math.abs(m) }}, options) //Tout type de terrain
        )

    //Calcul d'un chemin
        astar.path({x:0, y:0}, {x:0, y:0}, {
            callback(path, scores) { path.map(n => console.log(n)) },
            layer:0, //Terrestre
            jps:false
        })
                

A propos de cette bibliothèque

Il s'agit donc d'une énième implémentation de l'A* en JavaScript, mais qui se veut flexible et simple. Elle peut solutionner des problèmes à **n** dimensions grâce à son utilisation des graphes, bien que la majeure partie des fonctions utilitaires sont prévues pour les problèmes bidimensionnels.

Vous pouvez télécharger le code source sur GitHub et consulter la documentation.

Caractéristiques

  • Basé sur la **théorie des graphes** pour permettre une grande flexibilité
    • Support des **graphes multiples**, utilisation des mêmes nœuds pour différents graphes
  • Utilitaires de construction de graphe pour les **tableaux bi-dimensionnels**
    • **Choix de l'ordre d'accès** ([x][y] ou [y][x])
    • Support des déplacements **diagonaux** avec coupe ou non
    • Support des cartes **toriques**
    • Support de l'A* **Jump Search Point** (JPS) pour les grilles à coût uniformes
  • **3 heuristiques ** : Manhattan, Diagonale, Euclidienne
    • Support des heuristiques **personnalisées**
  • Support des **coûts variables**
  • Support du **multi-tâche** (avec les Web Workers)
  • Utilisation des tas binaires et du principe de connectivité pour plus de **rapidité**

A* : Explication du code

Vous trouverez ci-dessous une explication ayant une approche très pragmatique, expliquant pas à pas l'exécution de l'algorithme.

L'algorithme en détails

L'initialisation consiste en la déclaration de la liste **ouverte** et de la liste **scores**.


    let open = new BinaryHeap()
    let scores = new Map()
            

La liste ouverte permettra de garder en mémoire les noeuds ayant été découverts, et qui seront potentiellement utilisés par la suite. On utilise généralement une **file de priorité** afin d'alléger les opérations de tri, d'où l'utilisation d'un **tas binaire**.

La liste des scores quant à elle, permet de garder une trace des scores des différents noeuds passés en revue. Celui-ci est calculé de la façon suivante : [Coût total du noeud de départ au noeud actuel] + [Coût heuristique du noeud actuel au noeud d'arrivée]

La prochaine étape consiste à les initialiser toutes deux avec le noeud de départ. Ce dernier n'a pas de prédécesseur (puisqu'il s'agit du départ) et coût est nul.


    open.add({node:start, estimated:0})
    scores.set(start, {score:0, from:null})
            

La boucle principale est active tant que la liste ouverte contient au moins un élément. Elle récupère les noeuds les plus prometteurs les uns après les autres, et si le noeud d'arrivée est trouvé, celle-ci s'achève.


    while (open.size) {
        let current = open.pop().node
        if (current === goal) { break }
        //...
            

À chaque itération, les voisins du noeud traité sont récupérés et leurs scores sont °(re)°calculés. Si l'un des scores est meilleur que celui précédemment enregistré, celui-ci est mis à jour en précisant le noeud permettant d'atteindre ce score. Par défaut, les scores des noeuds non découverts sont supposé **infini**.

Ces noeuds sont ensuite enregistrés dans la liste ouverte s'ils viennent d'être découvert.


        //...
        graph.neighbors(current).map(node => {
            let score = (scores.has(current) ? scores.get(current).score : 0) + cost(current, node)
            if (score < (scores.has(node) ? scores.get(node).score : Infinity)) {
                scores.set(node, {score, from:current})
                open.set({node, estimated:(score + heuristic(node, goal))})
            }
        })
        //...
            

Puis le noeud traité est retiré de la liste ouverte puisqu'il n'est plus nécessaire de l'étudier.


        //...
        open.delete(current)
    }
            

Une fois sorti de la boucle principale, la liste des scores contiendra le noeud d'arrivée si un chemin a été trouvé. Si c'est le cas, le chemin inverse est reconstruit puis retourné en fin d'exécution.


    let path = []
    if (scores.has(goal)) {
        let current = goal, path.push(goal)
        while ((current = scores.get(current).from) !== null) { path.push(current) }
        return path.reverse()
    } else { return path }
            

Jump Point Search : Explication du code

L'A* est un algorithme très puissant mais il peut rapidement devenir assez gourmand. Il est possible d'améliorer ses performances en effectuant certaines concessions.

Le JPS est une variante de l'A* spécifiquement conçu pour les graphes dont les coûts de déplacements sont uniformes. Néanmoins, cela se repose sur des règles spécifiques à chaque structure, ce qui fait qu'en pratique, la plupart des implémentations ne supportent que les grilles bidimensionnelles.

L'algorithme en détails

Puisqu'il s'agit d'une variante de l'A*, la boucle principale reste sensiblement la même. Néanmoins, l'enregistrement des noeuds découverts dans la liste ouverte diffère légèrement.


    neighborhood(current).map(node => {
        if ((jumped = jump(node, current)) !== null) {
            //Mise à jour des scores
            //Idem que dans l'A* classique
        }
    })
            

Deux différences sont à noter.

La première est que la liste récupérée des voisins du noeud traité est en réalité un sous-ensemble de la liste réelle. En effet, tout l'algorithme repose sur des **règles d'élagages** °(pruning rules, qui seront expliquées un peu plus tard)°.

La seconde est que l'on utilise une méthode de "**saut**" qui cristallise toute la force du JPS. Elle sera expliquée plus en détails un peu plus tard, mais constatez qu'un noeud n'est considéré comme découvert que sous certaines conditions, ce qui réduit de façon conséquente la maintenance de la liste ouverte, d'où les gains de rapidité.

Détaillons le contenu de la méthode **jump** :


    function jump(goal, n, p) {
        while (1) {
            //...
            

On supposera dans la suite de cette explication que **n** est le noeud actuel, **p** son prédécesseur et **access(p, n)** une méthode qui retourne un booleén indiquant s'il est possible d'atteindre **n** depuis le noeud **p** °(i.e. le noeud **n** n'est pas bloquant)°.

La boucle infinie permet de se "**projeter**" au loin, c'est ce qu'on appelle sauter. Celle-ci s'achève dans les cas suivants :

  • Le noeud est **bloquant**
  • Le noeud est celui d'**arrivée**
  • Un **voisin forcé** a été découvert

Commençons par traiter les deux premiers cas :


            //Noeud est bloquant ou noeud d'arrivée
                if (!access(p, n)) { return null }
                if ((n.x === goal.x)&&(n.y === goal.y)) { return n }
            

Ensuite nous allons calculer les composantes de vitesse :


            //Direction
                let d = {x:Math.sign(n.x-p.x), y:Math.sign(n.y-p.y)}
            

Puis nous allons traiter les différents cas dans lesquelles nous pourrions être confrontés à un **voisin forcé**.

Avant de continuer, revenons aux "**pruning rules**".
Notez que celles-ci sont différentes pour chaque type de structure, et je ne parlerais que celle des grilles bidimensionnelles.
Comme évoqué en début de section, les coûts de déplacements d'une case à l'autre sont censés être uniformes. Cela permet d'émettre certaines suppositions permettant de réduire le nombre de noeuds à considérer dans la liste **ouverte**.

Voici le code couleur à suivre sur les images suivantes :

  • **Noir** : Noeud actuellement traité
  • **Gris clair** : Prédécesseur
  • **Vert foncé** : Noeuds à stocker dans la liste ouverte à la prochaine itération lors de l'exécution de l'A* classique
  • **Gris foncé** : Noeuds écartés de la liste ouverte par déduction du JPS

Sur la *figure 1*, on **découvre** 8 nouveaux noeuds, ce qui devrait en théorie ajouter 8 éléments dans la liste ouverte. Toutefois, comme la *figure 2* le suggère, on peut éliminer le traitement des noeuds de gauche, car ils sont tous deux accessibles par le prédécesseur pour un coût de déplacement inférieur °(ou égal)°. Par le même principe, les noeuds centraux peuvent être écartés puisqu'ils sont accessibles depuis les noeuds de gauche. En exploitant cette supposition au maximum, on obtient finalement la *figure 5*.

Il y a cependant un cas °(deux avec sa symétrie axiale)° où il n'est pas possible de pousser la supposition jusqu'à la *figure 5* de l'image précédente : s'il y a présence d'un °(ou deux)° noeud°(s)° bloquant°(s)°. Les noeuds suivants **doivent** être ajoutés à la liste ouverte, puisqu'ils ne sont pas directement accessibles : il s'agit de voisin°(s)° forcé°(s)°.

Pour tous les déplacements latéraux, il vous suffit de reprendre les explications ci-dessous en imaginant la rotation des images dans votre tête. Nous pouvons donc maintenant écrire le code pour les sauts horizontaux :


            //Horizontal
                if ((d.x != 0)&&(d.y == 0)) {
                    if (((!access(n, {x:n.x, y:n.y-1}))&&(access(n, {x:n.x+d.x, y:n.y-1})))||
                        ((!access(n, {x:n.x, y:n.y+1}))&&(access(n, {x:n.x+d.x, y:n.y+1}))))
                        { return n }
                }
            

Et le voici le code correspondant pour les sauts verticaux :


            //Vertical
                if ((d.x == 0)&&(d.y != 0)) {
                    if (((!access(n, {x:n.x-1, y:n.y}))&&(access(n, {x:n.x-1, y:n.y+d.y})))||
                        ((!access(n, {x:n.x+1, y:n.y}))&&(access(n, {x:n.x+1, y:n.y+d.y}))))
                        { return n }
                }
            

En ce qui concerne les sauts diagonaux, le principe reste le même, avec une légère subtilité. Un déplacement diagonal résulte en la présence d'au moins **trois** voisins forcés. Pour les atteindre, il suffit de sauter une fois horizontalement, une fois verticalement et une nouvelle fois diagonalement.

Tout comme les déplacements latéraux, la présence de voisins forcés supplémentaires peut survenir lors de la rencontre avec une case bloquante...


            //Diagonale
                if ((d.x != 0)&&(d.y != 0)) {
                    if (((!access(n, {x:n.x-d.x, y:n.y}))&&(access(n, {x:n.x-d.x, y:n.y+d.y})))||
                        ((!access(n, {x:n.x, y:n.y-d.y}))&&(access(n, {x:n.x+d.x, y:n.y-d.y}))))
                        { return n }
                    //Sauts latéraux
                        if ((jump(goal, graph.node({x:n.x+d.x, y:n.y}), n) !== null)||(jump(goal, graph.node({x:n.x, y:n.y+d.y}), n) !== null)) { return n }
                }
            

Si nous n'avons pas quitté la boucle, l'algorithme continue avec dans sa direction avec le noeud suivant :


            //Noeud suivant
                p = n
                n = graph.node({x:n.x+d.x, y:n.y+d.y})
        }
        return null
    }
            

Et voilà !

Comme nous avons réalisé des sauts en évitant de stocker les noeuds intermédiaires, notre chemin est **troué**. Il ne faut donc pas oublier de le compléter...


    while ((current.x != start.x)||(current.y != start.y)) {
        let parent = scores.get(current).from
        while ((current.x != parent.x)||(current.y != parent.y)) {
            path.push(current)
            current = graph.node({
                x:current.x + Math.sign(parent.x - current.x),
                y:current.y + Math.sign(parent.y - current.y)
            }, true)
        }
    }
            

Post-processing : Explication du code

Le but de l'A* est de trouver le chemin le plus court entre deux noeuds. Cependant, celui-ci peut être assez biscornu. L'usage du **post-processing** nous permettra d'obtenir une route à l'apparence légèrement plus naturelle.

Prochainement