CODEWITHSUNDEEP
javascriptalgorithmrecursiongraphicsrendering
user3421907
user3421907

Reputation: 17

End Recursion in Javascript

So I've tried to implement the floodfill algorithm in js and came up with the following:

function floodAreaFromPoint(x,y) {

    if(typeof pixel[x] == "undefined") pixel[x] = [];
    pixel[x][y] = 1; // 1 for alpha

    if(!coordsInPixelArray(x + 1,y)) floodAreaFromPoint(x + 1,y);
    if(!coordsInPixelArray(x,y + 1)) floodAreaFromPoint(x,y + 1);
    if(!coordsInPixelArray(x - 1,y)) floodAreaFromPoint(x - 1,y);
    if(!coordsInPixelArray(x,y - 1)) floodAreaFromPoint(x,y - 1);

}

It works kinda fine but I have some issues with filling larger areas (10000x10000) where this alogrithm results in the error "maximum call stack exceeded". I understand the meaning of this error but I have no idea how i could possibly fix this...

I am willing to replace this function with a more efficient algorithm but I think the solution to this problem could be end recursion (which I have no idea how to correctly implement in js).

Edit: The pixel array contains the pixels that should be filled. When the function is called it already holds all border pixels.

Solution: 

function flood(x,y) {
    var nodes = [];
    nodes.push({"x":x,"y":y});

    while(nodes.length > 0) {
        var p = nodes[nodes.length - 1];
        if(coordsInPixelArray(p.x, p.y)) {
            nodes.pop();
            continue;
        }

        if(typeof pixel[p.x] == "undefined") pixel[p.x] = [];
        pixel[p.x][p.y] = 1; // 1 for alpha

        if(!coordsInPixelArray(p.x + 1, p.y)) nodes.push({"x": p.x + 1,"y": p.y});
        if(!coordsInPixelArray(p.x - 1, p.y)) nodes.push({"x": p.x - 1,"y": p.y});
        if(!coordsInPixelArray(p.x, p.y + 1)) nodes.push({"x": p.x,"y": p.y + 1});
        if(!coordsInPixelArray(p.x, p.y - 1)) nodes.push({"x": p.x,"y": p.y - 1});
    }
}

Upvotes: 0

Views: 83

Answers (1)

user4668606
user4668606

Reputation:

The solution is pretty simple: remove the recursion. You can aswell use a stack and push the nodes to the stack instead of a recursive call. pseudocode:

stack nodes//create a new stack
add(nodes , startNode)//initialize the stack with the first node

while ! isEmpty(nodes)//still nodes available that haven't been processed
    node p = peek(nodes)

    if ! nodeInArray(p) OR getColor(p) == 1
        //this node has already been visited or is not in the array
        //continue with the next node in the stack
        pop(nodes)
        continue

    color(p , 1)//mark the node as visited
    push(nodes , node(x(p) - 1 , y(p))//add node to be processed in the future
    ...//push all other neighbours to the stack

Upvotes: 2

Related Questions