Pour le moment j'ai choisi le Sidewinder car je trouve le Recursive Backtracking excessivement facile à résoudre :
En rougele chemin.
En bleu claire les zones accessibles depuis un embranchement au bord du labyrinthe donc rien de plus simple pour choisir de quel côté aller si on a plus de 2 neurones !
En bleu foncé les zones accessibles depuis un embranchement donnant sur une zone entouré par le chemin que l'on vient de parcourir, il serait tout aussi stupide d'y aller.
Il n'y a donc aucun réel enjeu avec cet algorithme... Je ne comprends pas l'intérêt pour le Recursive Backtracking. La version Sidewinder me paraît plus complexe sauf à rebours ! Ce qui n'est pas possible dans le cadre de ce que je souhaite faire (sauf à être hacker).
Quand pensez-vous ? Le chemin de Sidewinder est plus court mais, au risque de me répéter, il me semble plus compliqué à trouver... J'ai également rajouté des passages interchemins dans mon labyrinthe de façon aléatoire histoire de pouvoir remonter par un autre chemin si nécessaire.
Drôle de hasarrd, je me posais justement la question. Voici un lien vers la méthode de sidewinder: https://hurna.io/fr/academy/algorithms/maze_generator/sidewinder.html En quoi le backtracking récursif est si simple si tu choisis aléatoirement la direction privilégiée? On pourrait faire un shuffle des directions possibles pour ne pas faire toujours les choix de la même manière. Un labyrinthe parfait n'admet qu'un chemin de retour, ou je me trompe?
@WhiteCrow - Mon labyrinthe est carré avec des chemins rectilignes. - Le joueur commence en haut à gauche et finit en bas à droite. - Le joueur n'a qu'une vue partielle du labyrinthe. - Les chemins peuvent se "rencontrer" ou non, peu importe.
- Je souhaite que le joueur ne se retrouve pas face à une bifurcation avec une voie évidemment mauvaise comme dans ma première image. - Je pense que les longs couloirs sont plus complexe à appréhender
- Pas réellement de limite en terme de performance du script. Il peut bien mettre 1h pour construire le labyrinthe s'il est vraiment complexe.
Je ne connais que python (très partiellement) malheureusement...
@PierrotLeFouJ'étais tombé sur le même lien que ton premier !
En quoi le backtracking récursif est si simple si tu choisis aléatoirement la direction privilégiée?
Le script que j'ai trouvé me donne systématique un labyrinthe avec les défauts que j'ai exposé là haut. J'ai créé un énorme labyrinthe avec cette méthode et c'est tellement facile de savoir où aller...
Un labyrinthe parfait n'admet qu'un chemin de retour, ou je me trompe? "Un labyrinthe "parfait" signifie un labyrinthe sans boucles ni circuits fermés, et sans zones inaccessibles. Également appelé labyrinthe simplement connecté. De chaque point, il y a exactement un chemin vers n'importe quel autre point. Le labyrinthe a exactement une solution. En termes informatiques, un tel labyrinthe peut être décrit comme un arbre couvrant l'ensemble des cellules ou des sommets."
Et un labyrinthe du genre, tu n'aimerais pas? - .*...*...*...*...*... ...*...*...*...*...*. ********************. ...*...*...*...*...*. .*...*...*...*...*... .******************** .*...*...*...*...*... ...*...*...*...*...*.
Le Tout est souvent plus grand que la somme de ses parties.
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Le Tout est souvent plus grand que la somme de ses parties.
Python c'est bon, mangez-en.
Le Tout est souvent plus grand que la somme de ses parties.