Stack OverFlow et les joies de la récursivité

Fermé
Noxalus Messages postés 12 Date d'inscription jeudi 28 janvier 2010 Statut Membre Dernière intervention 24 avril 2011 - 28 janv. 2010 à 01:47
Edwyn Messages postés 105 Date d'inscription vendredi 20 juin 2008 Statut Membre Dernière intervention 31 mars 2011 - 28 janv. 2010 à 13:11
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

Edwyn Messages postés 105 Date d'inscription vendredi 20 juin 2008 Statut Membre Dernière intervention 31 mars 2011 14
28 janv. 2010 à 13:11
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
0