Introduction

Bonjour et bienvenue dans ce tuto qui va vous aider à comprendre et à implémenter l’un des algorithmes de pathfinding les plus connus, j’ai nommé A* ( prononcez “A STAR” ).Dans une seconde partie nous verrons comment implémenter (coder) cet algorithme en Typescript. Mais avant d’aller plus loin, osons un peu le décor. 

Le Pathfinding, à quoi ça sert ?

Vous êtes-vous déjà demandé comment votre GPS faisait pour trouver le chemin le plus rapide ou le plus court parmi une multitude d’autres chemins ? Ou alors comment les robots œuvrant dans les entrepôts d’Amazon se débrouillaient pour aller d’un point A à un point B sans jamais se percuter tout en optimisant leur trajet ?

Ou encore comment des personnages de jeux vidéos arrivaient jusqu’au joueur sans se perdre, de façon rapide et efficace ?

Enfin pas toujours hein …

Et bien tout ça, on le doit au Pathfinding, et du coup on est en droit de se demander …

C’est quoi le Pathfinding ?

La recherche de chemin, couramment appelée pathfinding par anglicisme, est un problème de l’intelligence artificielle qui se rattache plus généralement au domaine de la planification et de la recherche de solution. Il consiste à trouver comment se déplacer dans un environnement entre un point de départ et un point d’arrivée en prenant en compte différentes contraintes.

https://fr.wikipedia.org/wiki/Recherche_de_chemin

Voilà, maintenant on sait que le Pathfinding est avant tout un problème, que l’on catégorise volontiers comme relevant de l’intelligence artificielle. C’est aussi et surtout un domaine d’études qui a vu pas mal de scientifiques user leurs cheveux sur les problèmes qu’il couvre. Après toutes ces années, deux algorithmes sont vraiment ressortis du lot il s’agit:

  • De l’algorithme Dijkstra, du nom de son auteur Edsger Dijkstra, qui est connu pour retourner toujours le chemin le plus court entre deux points en prenant en compte l’intégralité des obstacles référencés.
  • De l’algorithme A* (prononcez A star) , inventé par Peter E. HartNils John Nilsson et Bertram Raphael. Cet algorithme est connu pour retourner rapidement l’un des meilleurs chemins possibles. Son principal avantage, par rapport à Dijkstra, est qu’il est plus rapide et que la solution qu’il retourne est souvent l’une des meilleurs si ce n’est la meilleure. Il est donc très prisé dans les domaines où l’on privilégie la vitesse à l’exactitude des résultats, comme le jeu vidéo par exemple. Il est aussi très simple à implémenter, c’est pourquoi j’ai choisi de vous le montrer.

Mais laissez-moi détailler un peu plus pourquoi j’ai choisi A *.

Pourquoi avoir choisi A* ?

La encore l’explication est très simple, l’efficacité d’un algorithme ( et ce quel que soit le domaine ) se mesure à l’aide de son rapport qualité/complexité. Mais que signifient ces mots ?

La qualité

La qualité de l’algorithme, c’est sa capacité à résoudre plus ou moins correctement le problème qu’on lui pose.

Exemple:

Posons la problématique suivante: Je veux que mon algorithme me permette de calculer une dizaine de nombre premiers, cependant tout ces nombres devront être compris dans un intervalle.

  1. Considérons l’algorithme A: Il sait calculer dix nombres premiers mais ne prend pas en compte la notion d’intervalle.
  2. Considérons l’algorithme B: Il est identique à l’algorithme A à ceci près que lui prend en compte la notion d’intervalle.

Conclusion: l’algorithme B a un meilleur rapport qualité que l’algorithme A.

La complexité

La complexité d’un algorithme est la notion la plus compliqué à comprendre ici, c’est pour cela qu’on va la simplifier. En effet, ce tuto est dédié à un algorithme spécifique et non à l’algorithmie en générale, que les puristes me pardonnent donc si je “charcute” certaines notions. La complexité d’un algorithme, c’est en gros le nombre de calculs moyens qu’il va devoir réaliser pour arriver au résultat escompté.

Exemple:

  1. Considérons l’algorithme A: on considère que sa complexité se situe aux alentours de 100 opérations.
  2. Considérons l’algorithme B: Il est identique à l’algorithme A à ceci près que sa complexité est deux fois plus importante.

Conclusion: l’algorithme B a une plus grande complexité que l’algorithme A.

Le choix A*

A* est l’un des algorithmes les plus efficaces pour trouver un chemin rapidement, cependant, il se peut que dans des schémas assez complexes, comme un labyrinthe ou il faut faire beaucoup d’allers retours ou s’éloigner souvent de son objectif pour mieux l’atteindre, il peut ne pas retourner le chemin le plus court ou être un peu moins rapide que d’autres. Maintenant que l’on sait pourquoi on l’a choisi, on va pouvoir commencer à l’expliquer.

Explication de l’algorithme

Avant de commencer il est essentiel d’introduire quelques mots de vocabulaires algorithmique notamment:

  1. Le graphe: c’est ainsi que l’on va nommer “le monde” que notre algorithme va devoir parcourir pour trouver un chemin d’un point A vers un point B.
  2. Un node: c’est une unité du graphe, une “unité du monde”, l’algorithme va parcourir le “graphe” en passant des “nodes”.
  3. La liste ouverte: C’est une liste qui contient les nodes à analyser.
  4. La liste fermée: C’est une liste qui contient les nodes déjà analysés.

Vous pouvez vous représenter le graphe comme une grille où les nodes sont les cases d’un tableau.

Fonctionnement de l’algorithme

Ce schéma représentera notre monde, notre “graphe”. Avant de commencer à décrire en détail l’algorithme A* nous allons introduire quelques petites choses. Chaque node possède plusieurs propriétés qui vont être utiles à l’algorithme, présentons-les !!

  1. La propriété parent (P): il s’agit du node qui a permis “d’arriver” au node courant.
  2. La propriété G: il s’agit de la distance parcourue depuis le point de départ pour arriver au node courant.
  3. La propriété H: il s’agit de la distance à vol d’oiseau entre le node courant et le node d’arrivée.
  4. La propriété poids(F): il s’agit de la somme de G et de H.

Comme unité de mesure pour le calcul des propriétés F, G et H nous allons dire qu’un “déplacement” d’un node, donc d’une case, horizontal ou vertical vaut 100, nous ne considérerons pas les déplacements en diagonal pour cet exemple, afin de le garder le plus simple possible. Maintenant, passons aux différentes étapes de l’algorithme:

Les différentes étapes de l’algorithme

  1. Ajout du node de départ à la liste ouverte.
  2. Entrée dans la boucle suivante:
    1. Récupération du node avec le plus petit F contenu dans la liste ouverte. On le nommera CURRENT.
    2. Basculer CURRENT dans la liste fermée.
    3. Pour chacun des 4 nodes adjacents à CURRENT appliquer la méthode suivante:
      • Si le node est un obstacle ou est dans la liste fermée ignorez-le et passer à l’analyse d’un autre node.
      • Si le node n’est pas dans la liste ouverte, ajoutez-le à ladite liste et faites de CURRENT son parent(P). Calculez et enregistrez ses propriétés F, G et H.
      • Si le node est déjà dans la liste ouverte, recalculez son G, s’il est inférieur à l’ancien, faites de CURRENT son parent(P) et recalculez et enregistrez ses propriétés F et H.
      • Stopper la boucle de recherche si vous ajoutez le node d’arrivée à la liste fermée ou si la liste ouverte est vide, dans ce dernier cas, il n’y a pas de chemin possible entre A et B.
  3. Prenez le node d’arrivée et reconstruisez le chemin à rebours, càd en bouclant sur les propriétés parentes jusqu’à ce que le parent soit le noeud de départ.

Voici les étapes en bon français, laissez-moi vous proposer une implémentation en Typescript:

Le code Typescript

Fichier Node.ts

export const NEUTRAL = 0;
export const OPENED = 100;
export const CLOSED = 200;
export const NODE_DISTANCE_VALUE = 10;
export class Node {

    public g: number            = 0;
    public h: number            = 0;
    public f: number            = 0;
    public col: number          = 0;
    public row: number          = 0;
    public walkable: boolean    = true;
    public parent: Node         = null;
    public state: number        = NEUTRAL;

    public toString() {
        return `${this.row}, ${this.col}`;
    }
}

Fichier FastFinder.ts

import { NODE_DISTANCE_VALUE, Node, CLOSED, OPENED } from "./Node";

export class FastFinder {
    private opened: Node[] = [];
    private closed: Node[] = [];

    public findPath(graphe:Node[][], startNode:Node, endNode:Node): Node[] {
        // on crée les listes fermées et les listes ouvertes
        this.opened = new Array();
        this.closed = new Array();

        // - Ajout du node de départ à la liste ouverte.

        this.addToOpenList(startNode);


        //  stopper la boucle si la liste ouverte est vide
        let hasNextStep: boolean = true;
        while (hasNextStep) {
            // a. Récupération du node avec le plus petit F contenu dans la liste ouverte. 
            // On le nommera CURRENT.
            this.opened.sort((a, b) => a.f < b.f ? -1 : 1);
            const currentNode = this.opened[0];

            //  stopper la méthode si on ajoute le noeud d'arrivée à la liste fermée
            if (this.opened.length > 0 && currentNode === endNode) {
                hasNextStep = false;
                break;
            }

            // b. Basculer CURRENT dans la liste fermée.
            this.addToCloseList(currentNode);

            //  récupération des voisins de CURRENT
            let neighbours = this.getNeighbours(currentNode, graphe);
            let maxi = neighbours.length;

            // Pour chacun des nodes adjacents à CURRENT appliquer la méthode suivante:
            for (let i = 0; i < maxi; ++i) {
                const node = neighbours[i];

                //Si le node est un obstacle ou est dans la liste fermée ignorez-le et passer à l'analyse d'un autre node.
                if (this.isOnCloseList(node) || node.walkable === false)
                    continue;

                const opened: boolean = this.isOnOpenList(node);

                /* on calcule le nouveau g */
                const newG = currentNode.g + NODE_DISTANCE_VALUE;

                /*on calcule le nouveau h */
                const newH = (Math.abs(endNode.row - node.row) + Math.abs(endNode.col - node.col)) * NODE_DISTANCE_VALUE;

                /*on calcule le nouveau F*/
                const newF = newH + newG;
                if (
                    (opened && newG < node.g) ||
                    !opened
                ) {
                    //Si le node est déjà dans la liste ouverte, recalculez son G, s'il est inférieur à l'ancien, 
                    //faites de CURRENT  son parent(P) et recalculez et enregistrez ses propriétés F et H.

                    //Si le node n'est pas dans la liste ouverte, ajoutez-le à la dite liste et faites de CURRENT son parent(P). 
                    //Calculez et enregistrez ses propriétés F, G et H.

                    node.parent = currentNode;
                    node.g = newG;
                    node.h = newH;
                    node.f = newF;
                    if (!opened) {
                        this.addToOpenList(node);
                    }
                }

            }

        }

        // on finalise notre algo
        const finalPath = [];

        // on est sorti de la liste, on a deux solutions, soit la liste ouverte est vide dans ces cas là il 
        // n'y a pas de solutions et on retourne un finalPath vide
        // soit il y a au moins un élément dans la liste ouverte et on peut reconstruire le chemin à rebours.
        if (this.opened.length > 0) {
            // Soit on construit le chemin à rebours;
            let lastNode: Node = endNode;

            while (lastNode != startNode) {
                finalPath.unshift(lastNode);
                lastNode = lastNode.parent;
            }
        }
        //on retourne nos résultats
        return finalPath;
    }

    public addToCloseList(param_node) {

        const index = this.opened.indexOf(param_node);
        if (index > -1)
            this.opened.splice(index, 1);

        this.closed.push(param_node);
        param_node.state = CLOSED;
    }

    public addToOpenList(param_node) {

        const index = this.closed.indexOf(param_node);
        if (index > -1)
            this.closed.splice(index, 1);

        this.opened.push(param_node);
        param_node.state = OPENED;
    }

    public getNeighbours(node, graphe): Node[] {
        const row = node.row;
        const col = node.col;
        const indices = [[row, col + 1], [row, col - 1], [row - 1, col], [row + 1, col]];
        const results = [];

        indices.forEach(
            (coords) => {
                const r = coords[0];
                const c = coords[1];
                if (graphe[r] && graphe[r][c]) {
                    results.push(graphe[r][c]);
                }
            }
        );

        return results;
    }

    public isOnOpenList(param_node) {
        return this.opened.indexOf(param_node) > -1;
    }

    public isOnCloseList(param_node) {
        return this.closed.indexOf(param_node) > -1;
    }
}


Conclusion

Vous pourrez bien entendu trouver une petite application complète concoctée par mes soins (et commentée), à l’adresse suivante: https://github.com/thetinyspark/moocaccino/tree/pathfinding. Vous pourrez y voir un exemple d’application du pathfinding A* en temps réel avec un petit personnage qui doit retrouver un coffre au sein d’un labyrinthe végétal. Au passage, profitez-en pour jeter un œil au code permettant de générer le labyrinthe.

Trouvez le trésor avec la puissance du PathFinding!

C’est déjà la fin de ce tutoriel, j’espère qu’il vous aura plu et si c’est le cas, n’hésitez pas à le partager sur vos réseaux.
Quand à moi je vous dis à bientôt, devant un petit café, ciao!

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *