Génération Maze utilisant DFS

Question

J'essaye de générer un labyrinthe en Objective-C. J'ai construit un graphique et connecté tous les bords (je pense). Cependant, je suis coincé en essayant de faire le vrai labyrinthe.

Voici le code que je utilise:

- (void)visitFromCurrentPoint:(GridPoint *)point fromPreviousVertex:(Vertex *)prev { 

if ([grid allVerticiesVisited]) { 
    NSLog(@"done!"); 
    return; 
} 
Vertex *cur = [grid vertexAtPoint:point]; 
[grid setVertextVisited:cur]; 
NSArray *borderingVerticies = [grid verticiesBorderingPoint:point]; 
Vertex *randomVertex; 
int random = arc4random()%[borderingVerticies count]; 
randomVertex = [borderingVerticies objectAtIndex:random]; 
if (![randomVertex visited]) { 
    [cur.edgeList removeObject:prev]; 
    [prev.edgeList removeObject:cur]; 
    [self visitFromCurrentPoint:[randomVertex point] fromPreviousVertex:cur]; 
} 
else { 
    [self visitFromCurrentPoint:point fromPreviousVertex:cur]; 
} 
} 

Cependant, cela ne fonctionne pas et je reçois un débordement de pile. Pouvez-vous voir ce que je fais mal?

Merci d'avance!

Answer 1

Ceci est dû à trop de récursion. Essayez une solution itérative. Pour clarifier: chaque appel de fonction utilise un peu d'espace de pile pour transmettre des arguments et/ou enregistrer l'état des registres de CPU qui seront modifiés pendant la portée de la fonction appelée. Si vous faites une récursion vraiment profonde, vous pouvez finir par utiliser tout votre espace de pile, d'où le crash.

Une solution itérative évite le problème en remplaçant la pile système par une matrice ou une file d'attente de taille dynamique. Cela utilise la mémoire système au lieu de l'espace de pile.

(essentiellement une solution récursive où vous utilisez une file d'attente ou d'un tableau dans votre fonction pour prendre la place de la comptabilité automatique que vous obtenez via des appels de fonction récursive)

Une autre option pourrait être en largeur première récursion par rapport à la profondeur .