[Javascript] Stack Overflow (too much recursion)

[Jo3p789]

Ik vind het spelletje GoldStrike http://www.funnygames.nl/spelletjes/2374.html erg verslavend, maar erger me aan delen van de gameplay. Daarom besloot ik vanavond dat spelletje in Javascript opnieuw te bouwen, zoals ik het graag zou zien.

Ik stuit daarbij op een stack overflow (too much recursion) error in een recursieve functie die ik niet opgelost krijg. Ook in gevallen waarbij de functie zichzelf slechts 1 maal aanroept, geeft de browser deze fout.

Om de situatie zo goed mogelijk te begrijpen, is het handiger om even op bovenstaande link te klikken dan dat ik het hier probeer uit te leggen. Heb je meteen een momentje spelplezier

Het probleem doet zich voor wanneer de speler klikt op een stenengroep om deze te verwijderen. Het script zoekt naar de totale groep van gelijkgekleurde stenen, die naast, onder of boven elkaar kunnen liggen. Dit gebeurt door middel van een recursieve functie die respectievelijk checkt of de bovenliggende, rechter, onderliggende en/of linker steen hetzelfde is, en de functie opnieuw aanroept met de coordinaten van een gevonden steen. Vervolgens retourneert de functie een array met coordinaten, waaraan de huidige steen wordt toegevoegd. Uiteindelijk levert dit de totale array van stenen op, die, als deze 2 of meer elementen bevat, gewist moet worden. (Een enkele steen kan namelijk niet worden verwijderd.

code:

function search_group(row, column, backgroundcolor, group) {

    if (row>0 && document.getElementById((row-1)+"_"+column).style.backgroundColor==backgroundcolor ) {
        group =  search_group(row-1, column, backgroundcolor, group);
    }

    if (column<columns-1 && document.getElementById(row+"_"+(column+1)).style.backgroundColor==backgroundcolor ) {
        group = search_group(row, column+1, backgroundcolor, group);
    }

    if (row<rows-1 && document.getElementById((row+1)+"_"+column).style.backgroundColor==backgroundcolor ) {
        group = search_group(row+1, column, backgroundcolor, group);
    }

    if (column>0 && document.getElementById(row+"_"+(column-1)).style.backgroundColor==backgroundcolor ) {
        group =  search_group(row, column-1, backgroundcolor, group);
    }

    group[group.length]=row+"_"+column;

    return group;
}

De foutmelding ontstaat wanneer ik op een steen klik die in een groep hoort van meer dan 1 steen. Bij bijvoorbeeld een groep van twee stenen zal de functie zichzelf slechts 1 keer opnieuw aanroepen, maar daar ontstaat de fout al. Het meest vreemde is, dat als ik regel 11-17 (de check voor de onderliggende steen en de linker steen) verwijder, dan werkt de functie voor een geheel leeg veld wel (99 recursieve aanroepen!). Hetzelfde als ik regel 3-9 weghaal.

Ik snap er geen fluit van. Ik heb al geprobeerd om geen array te gebruiken, maar een string, en de coordinaten daar kommagescheiden aan toe te voegen, maar de foutmelding blijft. Het lijkt wel alsof de Javascript-interpreter vaststelt dat 2+ mogelijke recursieve aanroepen binnen een functie teveel zijn, ongeacht of deze ook daadwerkelijk gebruikt worden.

Je vindt het script op http://www.endlesscassettes.com/goldstrike/. Het belangrijkste verschil met het originele spel is dat nieuwe rijen niet automatisch ontstaan, maar moeten worden toegevoegd door op de '>>' knop te klikken.

Ik hoop dat iemand een idee heeft wat hier mis gaat, of een mogelijke oplossing weet. Ik kom er maar niet uit.

Groet,

Jo3p

[Blaise]

Als je alert(row + ',' + column); in de functie search_group() toevoegt zie je waarom. Hij gaat oneindig pingpongen tussen twee blokken omdat je niet checkt of een blok al geweest is.

[ Voor 8% gewijzigd door Blaise op 08-09-2006 01:25 ]

[MBV]

leuke is ook dat hij alle kanten op gaat pingpongen. Damn, wat een gigantische berg alerts levert dat op voor je teveel recursie krijgt...

offtopic:
ga jij eens niet vlak voor mij lopen posten

[crisp]

Dit soort dingen moet je ook niet recursief oplossen maar iteratief; dat is vele malen sneller, kost minder geheugen en je loopt niet tegen deze callstack-problemen aan (note dat in Safari een stack-depth van 99 ook echt de max is).
HIer een voorbeeld van het floodfill algorithme dat ik gebruik in mijn Crispy paint; dit is behoorlijk geoptimaliseerd though:

JavaScript:

function grid_floodfill(x, y, color)
{
    var old_color = grid[y][x].color;
    if (color == old_color) return;

    var stack = [{x:x, y:y}];
    var pixel, u, d;

    while ((pixel = stack.pop()))
    {
        x = pixel.x;
        y = pixel.y;
        u = d = 1;

        //-- go as far left as possible
        while (x-- && grid[y][x].color == old_color);

        //-- go right again and check for openings up and down
        while (x++ < grid_x && grid[y][x].color == old_color)
        {
            grid_drawpixel(x, y, color);

            if (y > 0)
            {
                if (grid[y-1][x].color != old_color) u = 1;
                else if (u) { stack.push({x:x, y:y-1}); u = 0; }
            }
            if (y < grid_y)
            {
                if (grid[y+1][x].color != old_color) d = 1;
                else if (d) { stack.push({x:x, y:y+1}); d = 0; }
            }
        }
    }
}

[Jo3p789]

Dank voor jullie oplossingen, ik heb er finaal overheen gekeken. Stom...

Ook ga ik me inderdaad eens verdiepen in die iteratieve mogelijkheid, niet in de laatste plaats omdat ik het heb overwogen, maar geen passend algoritme wist te bedenken.

Thanks!

[MBV]

wat doet deze code?

code:

    var stack = [{x:x, y:y}];

Die syntax ken ik niet.

offtopic:
ziet er strak uit. Nu moet je nog even het bewijs leveren dat hij hetzelfde doet als de recursieve variant Gewoon 3x omzetten naar staartrecursief, tuplen, kom je wel uit
* MBV studeert Computer Science & Engineering aan de TU/e[/ME]

[crisp]

MBV schreef op vrijdag 08 september 2006 @ 11:30:
wat doet deze code?

code:

    var stack = [{x:x, y:y}];

Die syntax ken ik niet.

Dat is object-notation, oftewel literal constructors:

JavaScript:

// array literal constructor:
var array = [1,2,3];
// object literal constructor:
var object = {prop1: 1, prop2: 2, prop3: 3};

Kortom: de stack wordt geinitialiseerd als zijnde een array met als eerste element een object met een x en y property

offtopic:
ziet er strak uit. Nu moet je nog even het bewijs leveren dat hij hetzelfde doet als de recursieve variant Gewoon 3x omzetten naar staartrecursief, tuplen, kom je wel uit
* MBV studeert Computer Science & Engineering aan de TU/e[/ME]

Dat bewijs laat ik dan graag over aan degenen die ervoor gestudeerd hebben