Comments on Labyrinthes

Je n'ai pas de recette miracle pour générer des labyrinthes ludiques mais je tente au cas où. En gros, il faudrait que la quête du bon chemin soit une énigme plaisante. Dans ce cas, plutôt que d'utiliser de l'aléatoire pour générer le labyrinthe, peut-être qu'utiliser de la théorie des groupes, un truc un peu plus "cristallin" pourrait être une piste. Un truc qui activerait dans la tête un peu les mêmes mécanismes que le Rubik's Cube ou le taquin.

Une autre piste, ça pourrait être de partir d'un labyrinthe absurdement difficile et inintéressant, et de lui rajouter des "indices" qui font que si on arrive à les lire convenablement, le bon chemin nous est plus ou moins révélé. Par exemple, on pourrait imaginer qu'on mette un certain nombre de "grandes places" (une zone de taille modérée sans mur à l'intérieur) et qu'on en mette plein le long du chemin optimal et très peu dans le reste. En dosant le ratio "plein" vs "très peu", on peut doser les indices qu'on donne et espérer trouver la juste difficulté…

Un autre type d'indice, ça peut être la couleur au sol. Si la couleur indique la distance à l'arrivée, alors l'indice trivialise le labyrinthe. Mais peut-être qu'une variante bruitée de cela peut donner une difficulté intermédiaire et plaisante ?

On peut également déguiser une énigme de reconnaissance en un labyrinthe. Du genre : il y a une vraie loop-erased random walk dans le dessin puis dessus un humain a essayé (avec une conviction modérée et sans assistance d'un ordi ni d'un dé ou d'une pièce de monnaie, peut-être même en temps limité) de dessiner plein de rameaux autour de cette marche qui sont censés "avoir la même tête que le chemin qu'on cherche à cacher". D'expérience, un humain mal entraîné a tendance à dessiner des choses qui ont des caractéristiques assez différentes d'un dessin choisi uniformément au hasard. La curiosité du joueur pourrait alors être titillée en mode "hmmm… OK, il faut que je remonte à la Source du Chaos et pour ce faire je dois choisir le seul chemin qui est vraiment chaotique, qui n'a pas les bribes d'ordre d'un cerveau encapsulés dans sa géométrie". Le jeu devient alors quasi-adversarial et réveille un peu des instincts de chasseur préhistorique qui piste sa proie.

Enfin, on peut imaginer une piste un peu fractale du type suivant. Imaginons un carré 4 par 4. Dans chaque carré, il y a 4 portes, qui sont reliées ou non entre elles d'une certain façon qui dépend du carré. On peut alors définir un labyrinthe fractal en subdivisant chaque carré à nouveau en 4 par 4 et en réalisant les connexions désirées par le meneur de jeu à l'échelle du dessus (pour peu qu'elles soient réalisables par un labyrinthe planaire) via les chemins du labyrinthes à l'échelle inférieure. Ca peut être rébarbatif tel quel mais si tous les carrés d'une échelle donnée sont simplement des versions tournées les unes des autres, il y a un côté "le travail fait sur un carré se répercute sur tous les autres", "cette familiarité acquise servira moultes fois".

Bref, c'était quelques idées en vrac, au cas où l'une d'entre elles pourrait par ricochet faire germer une idée pas mal.

PS : A titre informatif, l'algorithme de Wilson est assez important en mécanique statistique. Peut-être qu'une façon de s'en rendre compte, c'est de dire que non seulement les arbres couvrants uniformes sont très importants (liés, entre autres, aux réseaux électriques, donc aux marches aléatoires/fonctions harmoniques) mais que c'est en étudiant les marches à boucles effacées (qui interviennent dans cet algorithme) qu'a germé l'idée du processus SLE, qui est un des joyaux probabilistes des 20 dernières années.

Merci, je comprends mieux : il apparaîtrait donc qu'une approche de type arbre couvrant uniforme soit adaptée pour générer des labyrinthes difficiles mais pas pour fournir des labyrinthes ludiques.

Dans la veine percolation, as-tu déjà testé un arbre couvrant uniforme ? Par définition, entre deux points quelconques du labyrinthe, tu auras un unique chemin les reliant, et le superbe algorithme de Wilson permet de générer cela efficacement.

http://mypage.iu.edu/~rdlyons/maze/maze-bostock.html

"Congratulations! You found the exit!"

Glop, glop !
J'ai enfin trouvé ce mythique portail couleur bleu-azur, quelque part en z=7.
Pour savoir ce qu'il y a derrière (i.e. le légendaire trésor) : eh bien, "jouez" dès à présent.
Partage il y aura bien, mais selon un juste mérite (légitime).
Merci, malgré tout, aux Dieux pour avoir créé une cage néanmoins très "clean".

Bonsoir.
J'ai monté quelques étages (rapidement, et joyeusement même [sur tapis rouge]).
Fier et étonné, j'arrive au z=4, et là, paf, je me suis cogné à tous les murs.
Absolument tous.
C'est désespérant de sentir qu'il faut revenir (très loin ?) en arrière parfois.
Mais c'est le "jeu" (à présent je mets des guillemets).
Reviens le souvenir d'un professeur de maths qui s'exclamait (après l'épreuve, à l'époque) : "Mais tout était très facile !".
Pourtant, nos avenirs étaient là, en enjeu, et pilotés (étrangement) par le manque de bol (relatif).
Piment de l'existence : un autre, inconnu, avait gagné des millions d'euros à la Loterie Nationale (ou Européenne).
Humour, quand tu nous tiens ! Voyons : il y a souvent des suites positives dans toutes ces "fournaises sans noms".
Ce soir, la preuve en est faite; certes le temps a tellement passé…
{Infinite Dreams}

Quelqu'un qui aime aussi les labyrinthes (il aime aussi les miroirs et les grains de sable).

<URL: http://www.ciudadseva.com/textos/cuentos/esp/borges/dosreyes.htm >

Je n'ai pas compris où et quand se passait Doom.

Et il faudrait mettre des nazis.

Le père et le labyrinthe, de quoi permettre aux sociétés de psychanalyse de se crêper le chignon pendant encore un siècle….

Il faut mettre des monstres et un lance roquettes, puis nous voilà replongés dans Doom II.

Sur l'exploration de labyrinthes, un phénomène que je trouve marrant est à quel point l'algorithme utilisé pour générer les premiers niveaux de nethack est efficace pour donner envie d'explorer. C'est aussi un effet des objets au sol et des monstres que l'on peut rencontrer… mais c'est fou de voir à quel point, une fois atteint Gehennom où les niveaux ressemblent beaucoup plus à des labyrinthes classiques, l'exploration devient pénible. (À ce stade, généralement, on est allé trop loin pour vouloir abandonner, et on a juste envie d'en finir.) Je me demande ce qui rend les premiers niveaux de nethack, avec leur disposition en couloirs et en salles, aussi prenants à explorer par comparaison avec les labyrinthes normaux de la fin du jeu.

Une prison construite par les Dieux.

Aller de D à A, c'est passer des épreuves pour aller des ténèbres à la Lumière.
Les couloirs/salles du labyrinthe peuvent être vides… ou pas (rencontres d'alliés, découvertes d'objets divers et de monstruosités en tout genres [jusqu'à l'abominable Minotaure])
Cette prison est garante de la réalisation d'un parcours personnel, nommée "l'Aventure", et sur laquelle on sait finalement peu de choses à l'avance.
La grande sagesse des Divinités impose en effet un minimum d'efforts et de réflexions pour le personnage.
La Mort au sein de l'aventure n'est pas forcément synonyme d'échec, mais plutôt d'inconnu : téléportation (dans un autre labyrinthe ?), ou passage dans une direction (vers un autre "plan" ?) nouvelle (et orthogonale, si j'ose dire).
La connaissance progressive du labyrinthe (apprentissage par degrés, "backtracking") présente un parallèle avec ce dernier : l'on peut même perdre/oublier son chemin (ou pas : fil d'Ariane).
Cherchons, cherchons toujours la vérité et la sortie (vers l'Océan du Ciel) !
Mais, sur ce, j'entends au lointain le grondement d'un monstre : alors à plus tard (ou pas)…

J'aime aussi beaucoup les labyrinthes, les labyrinthes mouvants et les sorties plus ou moins optimisées de labyrinthes. Pour cela je vous conseille tout particulièrement : http://www.bricks-game.de/indexuk.html

D'ailleurs ,j'y ai composé certains puzzles particulièrement tordus.

Je ne sais pas si tu as déjà vu ce site, il est très complet :
http://www.astrolog.org/labyrnth/algrithm.htm

Yo david,
Sous Firefox 23, Ubuntu 12.04 64 bits - drivers nvidia proprios (304)
"Your navigator does not support the HTML5 WebGL context!"

Galad

Le livre « Clojure Programming » contient justement une implémentation d’un générateur de labyrinthes de dimension et forme de pièces arbitraires. Le code est concis grâce aux ensembles et aux dictionnaires qui sont fournis nativement par clojure, c’est très élégant :
https://gist.github.com/cgrand/792959