L'algorithme implémenté dans Maze Solver est une variante "maison" intelligente de l'algorithme Depth-first search aussi appelé DFS pour simplifier. Il faut savoir qu'il ne trouve pas forcèment le chemin le plus court. La manière dont il a été implémenté ne fait pas lui un algorithme qui supporte les poids.
DFS visite un chemin pris au hasard et si celui-ci mène à un cul-de-sac, il rebrousse chemin jusqu'à trouver un chemin non visité. La différence entre DFS et notre petit algorithme, c'est que le nôtre ne prend pas un chemin par hasard. Lorsqu'il a le choix entre plusieurs chemins, il choisra systèmatiquement la case la plus proche de la sortie. Cela évitera ainsi les cul-des-sac inutiles.

Nous n'allons pas nous intéresser à la génération du labyrinthe, qui utilise un algorithme dit backtrack. Cet algorithme permet obligatoirement qu'un chemin vers la cible existe.

Pour commencer, un peu de vocabulaire. Dans des algorithmes concernant la théorie des graphes (comme résoudre un labyrinthe), nous n'appelerons pas les cellules des cases mais des noeuds.

Il faut tout d'abord savoir que chaque cellule peut être dans 4 états différents. L'état ouvert (rouge), l'état neutre (bleu), l'état fermé (vert) ou l'état banni (noir).
- Ouvert = Noeud actuel
- Neutre = Noeud pas encore visité et donc atteignable
- Fermé = Noeud déjà visité faisant apparemment parti du chemin final
- Banni = Noeud déjà visité mais menant à un cul-de-sac

Voici une image pour vous appuyez dans la compréhension :

Et donc voici un pseudo-code très fancisé pour une compréhension optimale :

• Définir le point de départ (noeud actuel)
• Tant que la noeud actuel n'est pas la cellule cible
• Ferme le noeud actuel (plus atteignable)
• S'il n'y a qu'un voisin atteignable
• Noeud actuel = voisin
• S'il y en a plusieurs
• Noeud actuel = voisin le plus proche de la cellule cible
• S'il n'y en a aucun
• Noeud actuel banni (cul-de-sac)
• Noeud actuel = Noeud parent du noeud actuel (retour en arrière)

                
currentNode = cells[0][0];

while (!isSolved) {
    currentNode.open = -1; // ferme le noeud
    let neighbours = currentNode.getReachableNeighbours();

    if (neighbours) {
        // s'il n'y a qu'une possibilité
        if (neighbours.length == 1) {
            neighbours[0].parent = currentNode;
            neighbours[0].open = 1; // ouvre le noeud
            currentNode = neighbours[0];
        } else {
            let dist = Infinity;
            // choisis le noeud le plus près de la cible
            for (let i = 0; i < neighbours.length; i++) {
                if (dist > distance(neighbours[i], targetNode)) {
                    dist = distance(neighbours[i], targetNode);
                    bestCell = neighbours[i];
                }
            }
            bestCell.parent = currentNode;
            bestCell.open = 1; // ouvre le noeud
            currentNode = bestCell;
        }
    } else {
        // s'il n'y a aucun voisin libre
        currentNode.open = 2; // on bannit la cellule, car cul-de-sac
        currentNode = currentNode.parent;
    }
    
    // si le noeud obtenu est la cible, on arrête
    if (currentNode === targetNode) {
        currentNode.open = -1; // ferme le noeud
        isSolved = true;
    }
}
                
            

Le lien du code de ce site complet est disponible sur GitHub : https://github.com/hugoducom/MazeSolver