Stack OverFlow et les joies de la récursivité [Fermé]

Signaler
Messages postés
12
Date d'inscription
jeudi 28 janvier 2010
Statut
Membre
Dernière intervention
24 avril 2011
-
Edwyn
Messages postés
105
Date d'inscription
vendredi 20 juin 2008
Statut
Membre
Dernière intervention
31 mars 2011
-
Bonjour à toutes et à tous ! :)

J'ai réussi il y a peu de temps à coder un algorithme de génération de labyrinthes parfaits. Celui-ci fonctionne très bien, mais comme j'ai utilisé la récursivité, celui-ci arrive rapidement en dépassement de mémoire, et je ne peux pas générer des labyrinthe de plus de 80*80. En effet, la pile d'appel à la fonction devient tellement grand qu'elle dépasse sa capacité maximum.

J'ai entendu dire qu'il fallait passer en itératif pour résoudre ce problème, mais je ne vois pas du tout comment faire. Faudrait connaître le nombre d'appel à la fonction, non ?

Je vous met la fonction "principale" qui est appelée à à répétition et qu'il faudrait modifier:

        
        /** 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();
            }
        }

Merci d'avance pour votre aide !

1 réponse

Messages postés
105
Date d'inscription
vendredi 20 juin 2008
Statut
Membre
Dernière intervention
31 mars 2011
14
Salut,

une solution rapide et facil a implementer mais pas super belle serait d'encadrer ta fonction dans
un while(true) et d'utiliser continue qd tu as de la recursion et break qd ton lab est fini

mais bon le mieux serait que tu determine la condistion d'arret de ta recursivite, que tu l'utilises dans une loop ;)

j'espere que ca t'aideras...

bye