Génération d'un labyrinthe parfait

Signaler
Messages postés
12
Date d'inscription
jeudi 28 janvier 2010
Statut
Membre
Dernière intervention
24 avril 2011
-
Messages postés
12
Date d'inscription
jeudi 28 janvier 2010
Statut
Membre
Dernière intervention
24 avril 2011
-
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 ! ;)
A voir également:

5 réponses

Messages postés
1860
Date d'inscription
lundi 28 novembre 2005
Statut
Modérateur
Dernière intervention
14 février 2015
41
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é. -
Messages postés
12
Date d'inscription
jeudi 28 janvier 2010
Statut
Membre
Dernière intervention
24 avril 2011

Merci, je regarde ça de suite !
Messages postés
5487
Date d'inscription
dimanche 4 août 2002
Statut
Modérateur
Dernière intervention
20 juin 2013
49
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-
Messages postés
5487
Date d'inscription
dimanche 4 août 2002
Statut
Modérateur
Dernière intervention
20 juin 2013
49
Lien n'étant pas passé:
http://ilay.org/yann/articles/maze/


[hr]
-Blog-
-Site Perso-
Messages postés
12
Date d'inscription
jeudi 28 janvier 2010
Statut
Membre
Dernière intervention
24 avril 2011

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