Labyrinth generator v1.0

Soyez le premier à donner votre avis sur cette source.

Vue 8 607 fois - Téléchargée 653 fois

Description

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

Source / Exemple :


Code + EXE + Lisezmoi.txt ---> ZZZip

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

Renfield
Messages postés
17280
Date d'inscription
mercredi 2 janvier 2002
Statut
Modérateur
Dernière intervention
21 juillet 2019
57 -
même genre, autre algo de génération. Il génère des laby dits parfaits (pas d'îlots) :

http://www.vbfrance.com/code.aspx?ID=42175
cs_DuFFBeeR
Messages postés
1
Date d'inscription
dimanche 6 août 2006
Statut
Membre
Dernière intervention
9 novembre 2006
-
10/10 j'ai cherché longtemps un algorithme similaire à celui-ci et je dois avouer qu'il est à la hauteur de mes attentes. Je l'ai porté en C avec une structure de "graphes" pour être facilement solutionable. Ceci dit, cet algorithme vaut tous les points que j'ai eu dans mon travail pratique pour ma fonction genererLabyrinthe :) Juste "légèrement" dommage qu'il n'est pas PARFAIT avec des tailles paires ...
cs_Zeroc00l
Messages postés
370
Date d'inscription
lundi 1 avril 2002
Statut
Membre
Dernière intervention
11 février 2010
-
ouais sauf que le probleme c'est que sous vb il fait pas le ET binaire ...
Il considère le 1 comme VRAI
Donc ta condition revient a savoir si nbr est =/= de 1 ou non !

A moins que je n'ai oublié une partie de la syntaxe du vb !
BruNews
Messages postés
21042
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
13 -
Tester parité ou non d'un nombre:

If nbr And 1 Then IMPAIR

se fait ainsi en 1 cycle processeur, +- 17 fois plus rapide qu'une division (modulo).
cs_Zeroc00l
Messages postés
370
Date d'inscription
lundi 1 avril 2002
Statut
Membre
Dernière intervention
11 février 2010
-
ok,
pk ne pas utiliser if truc mod 2 = 1 ?

merci Achenar... euh Cyrus ;)

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.