Recursive Array Traversal Problems

Question

Hello everyone,

I am having some stackoverflow issues and hopefully someone can give me some insight into a non/less-recursive solution.

Ident[][] map = ...

private int explore(Ident item, int xcoord, int ycoord) {
    if ((map[xcoord][ycoord] == null) || !map[xcoord][ycoord].equals(item))
             return 0;

    map[xcoord][ycoord] = null;
    int sumX, sumY, counter = 1;
    item.translate(xcoord, ycoord);

    for (int y = -1; y <= 1; y++)
        for (int x = -1; x <= 1; x++) {
             sumX = x + xcoord;
             sumY = y + ycoord;
            if (((y != 0) || (x != 0)) && (sumX >= 0) && (sumX < map.length) && 
                     (sumY >= 0) && (sumY < map.[0].length))
                     counter += explore(item, sumX, sumY);
             }
        }
    }
    return counter;
}

This method is given a 2-dimensional array of Ident Objects, a target Ident and a starting position within the array. It recursively traverses the array counting how large of a continuous area the Ident occupies. It also centers the inputted Ident item in the middle of the area.

By looping through the map array and calling the explore method on any non null elements I can construct an array of Ident items centered in their areas, and with sizes relative to their areas.

One can see that with anything but small maps, the stack will overflow.

Anyone have an alternate method of accomplishing the same task? Or some insight to help me find one?

Answer 1

To eliminate recursion, make a list of coordinates to explore and loop while it contains any items; in your loop, build a new list of coordinates to explore, and at the end of the loop, replace the old list with the new list.

Answer 2

This take me back to the mid-80's. Any flood fill algorithm is going to require a certain amount of state. I unfortunately don't remember the algorithms. What's efficient for a large expanse probably isn't going to efficient for a maze.

To avoid recursion, instead of recursing, just add the data that you would have called to a stack. Loop around popping the next unexplored coordinate from the top of the stack. Using a stack rather than a FIFO queue improves locality a bit, although it probably isn't going to make a huge difference here.

private int explore(Ident item, int xcoord, int ycoord) {
    int counter = 0;

    Queue<Point> stack = Collections.asLifoQueue(new ArrayDeque<Point>());
    stack.add(new Point(xcoord, ycoord));

    while (!stack.isEmpty()) {
        Point point = stack.remove();
        xcoord = point.x;
        ycoord = point.y;

        if (!item.equals(map[xcoord][ycoord])) {
            continue;
        }

        ++counter;
        map[xcoord][ycoord] = null;
        item.translate(xcoord, ycoord);

        for (int y = -1; y <= 1; y++)
            for (int x = -1; x <= 1; x++) {
                 int sumX = x + xcoord;
                 int sumY = y + ycoord;
                 if (
                     !(x == 0 && y == 0) &&
                     0 <= sumX && sumX < map.length &&
                     0 <= sumY && sumY < map[0].length
                 ) {
                     stack.add(new Point(sumX, sumY));
                 }
            }
        }
    }
    return counter;
}

In the best traditions of stackoverflow this has not seen a compiler. (It's also retains much of the original algorithm.)