Génération d'un labyrinthe parfait

Noxalus Messages postés 12 Date d'inscription jeudi 28 janvier 2010 Statut Membre Dernière intervention 24 avril 2011 - 6 janv. 2010 à 00:34
Noxalus Messages postés 12 Date d'inscription jeudi 28 janvier 2010 Statut Membre Dernière intervention 24 avril 2011 - 28 janv. 2010 à 00:15
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 ! ;)

5 réponses

krimog Messages postés 1860 Date d'inscription lundi 28 novembre 2005 Statut Membre Dernière intervention 14 février 2015 49
6 janv. 2010 à 09:32
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é. -
0
Noxalus Messages postés 12 Date d'inscription jeudi 28 janvier 2010 Statut Membre Dernière intervention 24 avril 2011
6 janv. 2010 à 12:57
Merci, je regarde ça de suite !
0
cs_Bidou Messages postés 5487 Date d'inscription dimanche 4 août 2002 Statut Membre Dernière intervention 20 juin 2013 61
6 janv. 2010 à 18:45
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-
0
cs_Bidou Messages postés 5487 Date d'inscription dimanche 4 août 2002 Statut Membre Dernière intervention 20 juin 2013 61
6 janv. 2010 à 18:46
Lien n'étant pas passé:
http://ilay.org/yann/articles/maze/


[hr]
-Blog-
-Site Perso-
0

Vous n’avez pas trouvé la réponse que vous recherchez ?

Posez votre question
Noxalus Messages postés 12 Date d'inscription jeudi 28 janvier 2010 Statut Membre Dernière intervention 24 avril 2011
28 janv. 2010 à 00:15
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 ! :)
0
Rejoignez-nous