Création labyrinthe

Signaler
Messages postés
72
Date d'inscription
mercredi 5 janvier 2005
Statut
Membre
Dernière intervention
22 mai 2009
-
Messages postés
3246
Date d'inscription
lundi 25 avril 2005
Statut
Modérateur
Dernière intervention
27 octobre 2012
-
Bonjour,
Je souhaite réaliser un petit jeux, qui utiliserais un labyrinthe.
Mon jeux est pret sauf le laby ^^

Je ne vois pas comment le réaliser.
Je suis sous un projert en mode console.
Il me faut une case de debut et une case de fin. Pas besoin de generer une solution.
J'ai cherché sur le net des algo et je suis tombé la dessus :

<hr />On part d'une case de départ dans le tableau. Chaque case possède 4 murs fermés, un marqueur 'visitée' et un id qui la rend unique.

Pour chaque case, s'il existe une case voisine qui n'a pas été visitée, on ouvre le mur entre ses deux cases (penser à l'ouvrir dans les deux cases). S'il n'y a pas de cases voisines libres, on repasse à la case précédente (penser à conserver l'historique de création quelque part).

S'il existe plusieurs cases voisines libres, on en choisit une au hasard.

Une fois qu'on a posé (m-1) (n-1) murs, on marque la dernière case comme case de sortie. Le labyrinthe est maintenant généré, avec un chemin unique reliant toutes les cases entre elles (si, si, essayez pour voir). Il ne reste qu'à parcourir la matrice pour initialiser les différentes cases avec au hasard un monstre, rien, un piège, un objet, à l'exception bien sûr, de la case d'entrée et de celle de sortie.

<hr />
Probléme : je n'arrive pas a l'appliquer.
Pourriez vous si quelqu'un a un bout de code plutot simple, m'en faire profiter svp.

En vous remerciant par avance.

ps: je ne savais pas trop ou poster ce genre de question. Désolé si ce post ne ce trouve pas au bon endroit :)
A voir également:

6 réponses

Messages postés
5487
Date d'inscription
dimanche 4 août 2002
Statut
Modérateur
Dernière intervention
20 juin 2013
49
Salut,
Je ne sais pas s'il s'agit du même algo que tu décris ici, mais le plus connu pour générer des labyrinthes est certainement l'algorithme de Kruskal .
Pour l'implémentation, à toi de faire des recherches pour voir si qqn l'a déjà fait et publié en C#, sinon va falloir que tu te lances dans la conception...

<hr />
-Blog-
Messages postés
3246
Date d'inscription
lundi 25 avril 2005
Statut
Modérateur
Dernière intervention
27 octobre 2012
34
Salut, je connais pas d'algo particulier, mais pour moi un labyrinthe c'est un tableau à 2 dimensions de 'bool', si c'est true tu peux passer, si c'est false c'est un mur.
Messages postés
5487
Date d'inscription
dimanche 4 août 2002
Statut
Modérateur
Dernière intervention
20 juin 2013
49
Lutinore> Oui mais le but c'est de pouvoir s'assurer qu'il y a toujours un chemin possible! Si tu génères aléatoirement des bool, tu auras pas des beaux chemins, et en plus tu peux pas être sûr d'avoir une solution.
Avec l'algorithme de Kruskal si

<hr />
-Blog-
Messages postés
72
Date d'inscription
mercredi 5 janvier 2005
Statut
Membre
Dernière intervention
22 mai 2009

Je ne connaissais pas l'algorithme de Kruskal.
Je sens que je vais devoir passer a la conception ^^
Messages postés
5487
Date d'inscription
dimanche 4 août 2002
Statut
Modérateur
Dernière intervention
20 juin 2013
49
Y'a une semaine environ, j'ai un copain qui me l'a montré (Kruskal), mais il l'avait fait en Java.
D'après ce que j'ai pu voir, c'est pas trop compliqué, tu devrais t'en sortir sans trop de problème...

<hr />
-Blog-
Messages postés
3246
Date d'inscription
lundi 25 avril 2005
Statut
Modérateur
Dernière intervention
27 octobre 2012
34
Bidou >> vi je suis d'accord dans le cas de la génération dynamique il faut effectivement un algo particulier. Mais maintenant pour toutes les questions j'ai une réponse qui marche à chaque fois : T'AS QU'A FAIRE UN WORKFLOW !!