Stack OverFlow et récursivité
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:
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
|
/** 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 !
