Hallo Leute,
da ist so ein Progrämmchen, was mir ein 3D-Labyrinth erstellen soll mit folgendem Algo:
Code:
// 1. alle Raeume ohne Durchgang kreieren
// 2. Start in beliebigem Raum
// 3. Weg bahnen: ist ein beliebiger der Nachbarraum ohne Gang, Weg dahin bahnen,
// sonst den bisher gebahnten Weg zurückgehen, bis ein unberührter Nachbarraum vorhanden ist,
// 4. weiter mit 3, bis kein Weg bahnen mehr möglich ist.
Mit Firefox3.0b5/Linux läuft das Ganze problemlos, aber mit Konqueror 3.8.5 und IE6/Wine scheitert das Ganze kläglich bei der Rekursion, dann gibt es bei größeren Systemen den Stack Overflow.
Der verantwortliche Codeteil dazu:
Code:
function weg_bahnen(ind)
{ var i=-1;
get_nachbar(ind);
if (liste[0]>0)
{ i=liste[Math.floor(liste[0]*Math.random())+1]; // einen Nachbarn herauspicken
// Nachbarschaft bestimmen, Wände öffnen:
if (i==ind-1) { f[ind]=f[ind]+8; f[i]=f[i]+2; } // links
else if (i==ind+1) { f[ind]=f[ind]+2; f[i]=f[i]+8; } // rechts
else if (i==(ind-xmax)) { f[ind]=f[ind]+1; f[i]=f[i]+4; } // vorne
else if (i==(ind+xmax)) { f[ind]=f[ind]+4; f[i]=f[i]+1; } // hinten
else if (i==(ind-xmax*ymax)) { f[ind]=f[ind]+32; f[i]=f[i]+16; } // oben
else if (i==(ind+xmax*ymax)) { f[ind]=f[ind]+16; f[i]=f[i]+32; } // unten
else alert('Fehler bei Nachbarbestimmung Zelle '+ind+' nach '+i);
add_liste(i,gang);
}
else
{ do
{ gang[0]--;
if (gang[0]>0) get_nachbar(gang[gang[0]]);
}
while ((liste[0]==0) && (gang[0]>0));
if (gang[0]>0) i=gang[gang[0]];
}
if (i>=0) weg_bahnen(i);
}
liste ist ein counted array, global, und wird mit get_nachbar gefüttert.
gang ist auch ein globales counted array, was sich die Verzweigungen merkt.
Beide können nicht über xmax*ymax*zmax+1 (Zellenanzahl+1) hinaus wachsen.
Ja, und dann sind da noch die xmax*ymax*zmax Zellen im globalen Array f.
Bisher versucht, aber ohne Erfolg:
1. Variable i als outer_i global gemacht
2. Schwanz geändert in obigen Quellcode, die Absprünge in die Rekursion waren vorher jeweils am Ende der äußeren if-else-Blöcke
Da ergab sich aber auch *exakt* das gleiche Verhalten bei der Rekursion: Firefox war kein Thema, den habe ich bis zu 4600 Zellen gequält, Konqueror und IE6 machten jedoch nach 450, spätestens 480 Zellen schlapp.
Das Programm dazu:
Labyrinth-Generator 3D
Irgendwelche Ideen, wie man den beiden eine ähnliche Performance wie dem Firefox beibringen kann?
so long,
BlueJay
Lesezeichen