Génération d'un labyrinthe parfait

Question

Bonjour à toutes et à tous ! :) Je suis en train de créer un jeu dans lequel un labyrinthe parfait et généré. Seulement, je ne stocke pas le labyrinthe de la même façon que ceux que l'on peut trouver sur le net: ceux dont les cases possèdent chacune 4 murs => murs qu'on enlève au fur et à mesure: Non, mon labyrinthe est en fait représenté sous la forme d'un tableau à 2 dimensions. Chaque case peut être identifiée par ses coordonnées en X et en Y de cette façon là: maze[x, y]. Lors de la génération aléatoire, ces cases prennent donc une valeur, soit 0, ce qui correspond à une case vide, soit 1 => qui représente un mur. Vous l'aurez compris, c'est un peu le principe du tout ou rien. Pour chaque case on a un mur ou on en a pas. Or, et c'est là qu'est mon problème, j'ai besoin de générer un labyrinthe parfait, et avec cette représentation, je ne sais pas du tout comment faire :( Pour que vous voyez plus précisément ma façon de voir les choses, voici un petit bout de code: // Variable aléatoire Random rand = new Random(); // Taille du labyrinthe size = new Point(20, 20); // Création de la structure du labyrinthe maze = new int[size.X, size.Y]; // On place la sortie sortie = new Vector2(rand.Next(size.X), rand.Next(size.Y)); // On place les murs for (int x = 0; x < size.X; x++) { for (int y = 0; y < size.Y; y++) { maze[x, y] = rand.Next(2); } } Comme vous pouvez le constater, ce code ne fait que générer un labyrinthe totalement aléatoirement. Si vous savez comment faire pour générer un labyrinthe parfait à partir de ce code, je suis preneur ! Merci d'avance pour votre aide et bonne soirée ! ;)

krimog · Answer

Salut

Si je comprends bien, ton problème est qu'avec ta méthode, tes murs ont l'épaisseur d'une case.

Dans ce cas, tu peux passer par la solution d'un graphe, dont j'ai parlé dans un post précédent : Lien.

Krimog : while (!(succeed = try())) ;
- Nous ne sommes pas des décodeurs ambulants. Le style SMS est prohibé. -

Noxalus · Answer

Merci, je regarde ça de suite !

cs_Bidou · Answer

Salut,
Regarde du côté de l'algo de Kruskal
Une implémentation en C# sur csharpfr: http://www.csharpfr.com/codes/GENERATEUR-LABYRINTHES-ALEATOIRE_44802.aspx
Plus d'info: 

[hr]
-Blog-
-Site Perso-

cs_Bidou · Answer

Lien n'étant pas passé:
http://ilay.org/yann/articles/maze/


[hr]
-Blog-
-Site Perso-

Noxalus · Answer

Merci à tous pour votre aide !

Je me suis grandement inspiré de l'algo qu'on peut voir sur Wikipedia, et je me suis lancé dans le code. Ce qui fait que j'ai un truc totalement à ma sauce, mais qui fonctionne (et que je comprend surtout). Seul hic, c'est du récursif, et la pile d'appel atteint rapidement sa limite de capacité (impossible de générer des labyrinthe supérieur à 80*80 :().

J'ai entendu dire que passer le tout en itératif suffirait à résoudre le problème, et qu'il faudrait gérer nous même cette pile d'appel. Seulement, je ne sais pas du tout comment faire  Je vous met la fonction "principale" qui est appelée à répétition:


        /** Génére un layrnithe parfait **/
        public void GenLabyParfait()
        {
            // On réinitialise le tableau
            for (int i = 0; i < 4; i++)
            {
                casespossibles[i] = false;
            }
            // On recherche les cases possibles
            casespossibles = RechercheCasesPossibles();

            int j = 0;
            for (int i = 0; i < 4; i++)
            {
                if (casespossibles[i] == false)
                    j++;
            }
            // Si aucune case n'est possible
            if (j == 4)
            {
                // On regarde qu'on se retrouve pas à la case initiale 
                // (auquel cas la génération du labyrinthe est finie)
                if (!(pos_actuelle == sortie_position))
                {
                    // On retourne à la case précédente
                    pos_actuelle = pos_prec.Pop();
                    // Et on rappelle l'algorithme de génération avec la nouvelle position
                    GenLabyParfait();
                }
            }
            // Si au moins un case est possible 
            // => on en choisi une au hasard
            else
            {
                int mur_alea = random.Next(4);
                while (casespossibles[mur_alea] == false)
                {
                    mur_alea = random.Next(4);
                }

                // Haut
                if (mur_alea == 0)
                {
                    // On pose un chemin
                    Carte[pos_actuelle.X, pos_actuelle.Y - 1] = 0;
                    // On stocke notre position actuelle
                    pos_prec.Push(pos_actuelle);
                    // On avance sur cette case
                    pos_actuelle.Y--;
                }
                // Droite
                else if (mur_alea == 1)
                {
                    // On pose un chemin
                    Carte[pos_actuelle.X + 1, pos_actuelle.Y] = 0;
                    // On stocke notre position actuelle
                    pos_prec.Push(pos_actuelle);
                    // On avance sur cette case
                    pos_actuelle.X++;
                }
                // Bas
                else if (mur_alea == 2)
                {
                    // On pose un chemin
                    Carte[pos_actuelle.X, pos_actuelle.Y + 1] = 0;
                    // On stocke notre position actuelle
                    pos_prec.Push(pos_actuelle);
                    // On avance sur cette case
                    pos_actuelle.Y++;
                }
                // Gauche
                else if (mur_alea == 3)
                {
                    // On pose un chemin
                    Carte[pos_actuelle.X - 1, pos_actuelle.Y] = 0;
                    // On stocke notre position actuelle
                    pos_prec.Push(pos_actuelle);
                    // On avance sur cette case
                    pos_actuelle.X--;
                }
                // Et on rapelle l'algorithme
                GenLabyParfait();
            }
        }


Voilà, merci d'avance pour votre aide ! :)

Génération d'un labyrinthe parfait

5 réponses

Votre réponse