Construire un espace, puis le parcourir
Cette démo tient en deux gestes que je trouve fondateurs en algorithmique : d'abord fabriquer une structure, ensuite la traverser. Espace génère un labyrinthe, S le résout — et les deux animations, volontairement lisibles, donnent à voir deux familles d'algorithmes distinctes appliquées au même terrain de jeu.
Un labyrinthe « parfait » par backtracking récursif
Je génère le labyrinthe par un parcours en profondeur : je pars d'une cellule, j'abats un mur vers une voisine encore vierge, je m'y déplace, et je recommence. Quand une cellule n'a plus de voisine libre, je reviens sur mes pas (le backtracking) grâce à une pile, jusqu'à ce que tout soit visité. Le résultat n'est pas décoratif : c'est un arbre couvrant de la grille, donc un labyrinthe dit parfait — sans boucle ni zone isolée, où il existe un unique chemin entre deux cellules quelconques. La cellule ambre qui avance à l'écran, c'est exactement le sommet de la pile qui se déplace.
Le résoudre par un front d'onde (BFS)
La résolution utilise un tout autre outil : un parcours en largeur. Depuis l'entrée, j'explore le labyrinthe par cercles concentriques — toutes les cellules à distance 1, puis 2, puis 3… — ce que l'on voit à l'écran comme un front d'onde indigo qui s'étale. Comme le BFS progresse par distance croissante, la première fois qu'il touche la sortie, il l'a atteinte par le plus court chemin : je n'ai plus qu'à remonter la chaîne des provenances pour tracer, en ambre vif, l'itinéraire optimal. Un A* ferait mieux encore en orientant l'exploration vers la sortie, mais sur cette grille sans pondération, le front d'onde suffit et se prête bien à la démonstration.
Deux algorithmes, une même grille
Générer et résoudre partagent le décor mais rien d'autre. Le premier crée de l'information — il décide où sont les murs — en creusant en profondeur ; le second la consomme — il subit les murs — en explorant en largeur. C'est une distinction que je retrouve partout : construire un modèle de données et l'interroger n'obéissent pas aux mêmes contraintes, et confondre les deux est une source classique de code lent ou fragile. Voir les deux tourner côte à côte, sur zéro dépendance et quelques kilo-octets, rend la nuance concrète.
Pourquoi ça compte pour vos projets
Derrière ce petit labyrinthe, il y a les mêmes structures — piles, files, arbres, graphes — qui décident, dans une application réelle, si un calcul répond en quelques millisecondes ou fait ramer une page : recherche d'itinéraire, dépendances de tâches, arborescences de catégories, moteurs de recommandation. Choisir la bonne représentation et le bon parcours, c'est souvent là que se joue la performance et la robustesse d'un produit. C'est précisément le niveau d'exigence algorithmique que j'apporte quand je conçois vos briques critiques — avec, à la clé, un code clair que vos équipes peuvent reprendre et faire durer.
