Création labyrinthe

Question

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 :

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.

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 :)

cs_Bidou · Answer

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-

Lutinore · Answer

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.

cs_Bidou · Answer

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-

cs_ChamY · Answer

Je ne connaissais pas l'algorithme de Kruskal.
Je sens que je vais devoir passer a la conception ^^

cs_Bidou · Answer

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-

Lutinore · Answer

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 !!

Création labyrinthe

6 réponses

Votre réponse

Discussions similaires