J'ai toujours été fasciné par les labyrinthes. Pas tant le genre de labyrinthes dessinés sur un papier et dont on doit trouver la solution au stylo, mais plutôt les labyrinthes dont on ne voit qu'un morceau, dans lesquels on s'immerge complètement, et qu'on doit explorer au fur et à mesure, ou les labyrinthes informatiques. Un des programmes que mon papa a écrit pour moi quand j'étais petit, en Basic sur le New Brain qui a été mon premier ordinateur (voir ici pour les détails) était un programme de labyrinthe, ou peut-être un programme de dessin un mode texte que j'utilisais comme programme de labyrinthe. C'est aussi un des premiers programmes que j'ai réécrits en Turbo Pascal 4 vers '88–'89, et c'est avec lui vers cette époque (la date du fichier dit 1989-01-03, mais je ne sais pas si elle est fiable) j'ai réalisé ce chef d'œuvre (dessiné à la main, pas généré par ordinateur, je précise) :
![[Un labyrinthe en mode texte CP437]](../images/laby89.png "Il faut aller du D à un des deux A !")
J'ai forcé des barres de défilement à l'image (cliquez dessus pour la voir complètement) parce que c'était important que sur la taille 100×100 carrés du labyrinthe on n'en voyait que la région 80×25 d'un écran de PC à l'époque (c'est normalement à peu près ce qu'on devrait voir de l'image en question — mais je ne peux pas régler exactement parce que CSS ne permet pas de tenir compte de la taille des ascenseurs). Le but était d'aller du ‘D’ qui est à peu près au centre vers l'un des deux ‘A’ qui sont à droite en haut et en bas, en déplaçant le carré blanc qui se trouve juste en-dessous du ‘D’, et en évitant les murs définis par le caractère 177 (▒) du jeu CP437.
Bref, je crois que j'ai la palme du labyrinthe le plus pourri de l'univers, mais ça n'empêche pas qu'ils me hantent jusque dans mes rêves.
Je me rappelle aussi avoir été fasciné par les jeux Ultima Underworld, justement par cet aspect d'un monde à explorer, un labyrinthe, et surtout, un labyrinthe en 3D, ce qui est tout de même bien plus intéressant qu'un labyrinthe en 2D, parce que c'est plus complexe et parce qu'on s'y immerge vraiment.
Les labyrinthes mentionnés ci-dessus sont générés à la main, cependant. Je me suis aussi demandé comment faire des labyrinthes procéduraux qui soient intéressants. La première idée, que j'ai eue quand j'étais petit, c'était de remplir le monde avec des murs aléatoires juste autour de la probabilité de percolation (c'est-à-dire celle qui fait la transition de phase où le labyrinthe acquiert une grosse composante connexe ; on la détermine empiriquement) et ensuite creuser un chemin du départ à l'arrivée avec une marche aléatoire un peu dirigée pour être sûr que le problème est résoluble. Ce n'est franchement pas terrible, parce qu'on voit immédiatement ce qui a été creusé en plus, et le labyrinthe est trop facile. Pour compenser, j'ai tenté de programmer des labyrinthes en 3D et même en 4D dont on ne voyait que des tranches, mais c'est très peu intéressant à jouer. Quand vers '97 j'ai écrit le programme XLaby, mon premier programme un petit peu sérieux sous Unix (et qui est toujours disponible sous Debian et Ubuntu, mais il n'a plus l'air de marcher très bien), j'ai tenté différents algorithmes de génération du labyrinthe, notamment toutes sortes de variations autour de l'algorithme consistant à faire « pousser un arbre » (creuser les murs aléatoirement sans jamais repasser par un endroit déjà creusé, de sorte qu'on ne crée pas de cycle), puis éventuellement retirer quelques murs supplémentaires au hasard pour ajouter quelques cycles. Mais je ne suis pas très satisfait de l'intérêt de ces labyrinthes non plus : ils ont trop de culs-de-sac qui les rendent pénibles mais pas vraiment intéressants à explorer. Pour moi, un labyrinthe intéressant devrait avoir beaucoup de cycles, devrait avoir une difficulté qui ne soit pas la simple répétition d'un million de culs-de-sac, mais je ne sais pas générer ça automatiquement.
❦
Toujours est-il que je voulais apprendre à programmer un peu en WebGL sous JavaScript, et je voulais voir si je pouvais fabriquer des mondes et des labyrinthes 3D à explorer : j'ai écrit ce petit jeu de labyrinthe simpliste en JavaScript. Qui ne marchera probablement pas chez la plupart des gens (déjà, je n'ai pu tester que sous Firefox et Chrome, et encore, Chrome, il faut vraiment le supplier pour qu'il accepte de considérer que les drivers Gallium pour ma carte graphique Radeon peuvent fonctionner).
Le but est de trouver la sortie du labyrinthe (généré aléatoirement quand on charge la page), laquelle sortie se trouve au niveau z=7 (tout en haut ; on commence en z=0, tout en bas), quelque part sur le mur sud. Il n'y a pas de passages secrets (encore moins de monstres, d'objets à ramasser, ou quoi que ce soit de ce genre). On se déplace avec les flèches (si je n'ai pas trop merdé dans la façon de les capturer en JavaScript, ce qui, soit dit en passant, est un cauchemar) : gauche et droite pour tourner, haut et bas pour avancer et reculer, et aussi insert et delete pour se décaler vers la gauche et la droite sans tourner ; on peut aussi consulter une carte de ce qu'on a vu du niveau en tapant F1. Les variations de couleur servent à la fois à aider le sens de l'orientation en brisant la monotonie, et aussi à fournir quelque indice sur le progrès qu'on fait dans le labyrinthe (les couleurs elles-mêmes n'ont aucune signification, mais le changement d'une déco à une autre a un sens).
Je ne suis pas trop mécontent de l'apparence (la partie WebGL) et de la navigation, disons que la structure du labyrinthe ne me déplaît pas, c'est simple comme je le voulais. Mais les labyrinthes générés sont malheureusement très peu intéressants : ils sont sans doute assez difficiles, mais juste parce qu'ils accumulent une quantité phénoménale de fausses pistes et de culs-de-sac, pas vraiment d'une manière qui suscite la curiosité ou l'envie d'explorer. J'ai tenté mille et une variations sur l'algorithme de génération, sans réussir à changer vraiment les choses.
J'aurais pu utiliser un générateur
pseudo-aléatoire déterministe (au lieu du Math.random()
du JavaScript) pour générer le labyrinthe, histoire qu'on puisse
retourner dans un labyrinthe déjà visité. Je pourrais encore ajouter
cette fonctionalité, mais il faut dire que le peu d'intérêt des
labyrinthes produits ne m'a guère incité à me fatiguer à ça.
Ajout () : J'ai ajouté une possibilité primitive de sauvegarder le labyrinthe et de recharger un labyrinthe sauvegardé.