LABYRINTH GENERATOR v1.0
Prog/dev : Cyrus the great
Description :
-------------
Labyrinth Generator est un programme permettant de générer, selon une clef aléatoire, des labyrinthes d'apparence classique.
Note de l'auteur :
------------------
Jeux & Stratégies était un magasine sur les jeux de rôles, jeux de société et jeux vidéos. Dans ce mag, il y avait également un concours de prog permanent, qui consistait en la création du meilleur algorithme de génération de labyrinthes. Alors que j'étais encore gamin, ce concours me passionnait. C'est pour cela que j'ai créé ce programme. Je trouve d'ailleurs que le résultat est plus que potable, donnant au labyrinthe un bon aspect, et sachant qu'il est possible de le parcourir en tout point, je pense que c'est une réussite. Mais bon, passons aux exlications techniques, car il n'y a que ça de vrai.
Principe de génération du labyrinthe :
--------------------------------------
Voici l'idée de base :
1 - On crée 2 tableaux de la dimension du labyrinthe :
1er tableau : Murs
2eme tableau : Cases initialisées
2 - On initialise ces tableaux en disant qu'il y a partout des murs et qu'aucune case n'est initialisée.
3 - On recherche une case non initialisée dans la table des "Cases initialisées".
4 - Sur cette case, on lâche une taupe virtuelle qui va creuser (détruire les murs) au hasard, en prenant à chaque case une direction aléatoire vers une case non initialisée. Partout où elle passe, on dit que les case sont initialisées. Lorsque la taupe se bloque (lorsqu'elle n'a plus aucune direction vers une case non initialisée où aller), on reboucle en 3.
5 - Si on ne trouve plus de case non initialisée, cela veut dire que C'EST FINI !
Voilà pour l'idée de base, qui est relativement simple. Voici les problèmes rencontrés par cet algorithme et leur solution :
- Pb : Il y a des blocs isolés, qui ne sont pas très esthétiques dans le labyrinthe.
> Sol : On fait une recherche de ces blocs, et pour chacun de ceux-ci, on les relie par un mur au reste du labyrinthe.
- Pb : On ne peut pas aller partout dans le labyrinthe.
> Sol : Sur la case où la taupe est lancée, (juste avant de la lancer) on détruit un mur vers une case déjà initialisée.
- Pb : Il n'y a toujours qu'un seul chemin possible d'un point à un autre du labyrinthe. Ce serait bien de pouvoir tourner en rond.
> Sol : Sur la case où la taupe se bloque, on détruit un mur vers une case déjà initialisée.
Interface :
-----------
/// Menu principal ///
- "Name" : Nom du labyrinthe. Il est affiché sur la barre de titre de la fenêtre du labyrinthe.
- "X Dimension" : Dimension horizontale du labyrinthe en cases. Seules les valeurs impaires sont acceptées. Remarque : j'ai volontairement non bridé le maximum, mais gare aux plantages mémoire.
- "Y Dimension" : IDEM pour la dimension verticale.
- "Random key" : C'est la clef aléatoire qui permet d'initialiser les tables de hasard utilisées.
- "Labyrinth always possible" : Cochez ça pour pouvoir aller partout dans le laby.
- "Different itineraries" : Cochez ça pour casser la linéarité du laby.
- "Forbid isolated squares" : Cochez ça pour qu'il n'y ai pas de petits blos isolés dans le laby.
- "Make it !!!" : Lancement de la génération du labyrinthe. A la fin de la génération, la fenêtre de labyrinthe apparait.
/// Fenêtre du labyrinthe ///
- Menu contextuel : Cliquer sur le bouton droit de la souris pour le faire apparaître.
- "Copy to clipboard" : Permet de copier le labyrinthe dans le presse-papier, pour le retravailler avec d'autres outils graphiques après.
- "Close this window" : Fermeture de la fenêtre du labyrinthe.
A propos du logiciel :
----------------------
Ce petit programme peut être utilisé pour créer des labyrinthes pour des jeux. Donc si vous vous en sentez le courage, tout est prêt pour l'export. J'ai commenté le programme entièrement en anglais, ce qui est toujours mieux pour le portage dans des programmes externes. Tous les modules et procédures sont expliquées clairement, donc cela ne devrait pas poser de problème majeur. Pour ma part, je ne compte pas améliorer l'algorithme, que je trouve suffisament performant, mais je pense l'utiliser pour créer un petit jeu de desktop labyrinth sympathique, en rajoutant peut-être clefs, portes et temps limit. A méditer.
Sur ce, bon courage et bonne prog !
Cyrus the great