Recursive Array Traversal Problems

Question

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?

chaos · Accepted Answer · 2009-06-10 21:50:29Z

2

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.

edited Jun 10, 2009 at 21:50

answered Jun 10, 2009 at 21:35

chaos

125k34 gold badges306 silver badges310 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

chaos Over a year ago

Oops. Missed that. Thanks. Trimmed the answer down to the relevant part.

Tom Hawtin - tackline · Accepted Answer · 2009-06-10 22:07:11Z

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.)

It was close enough, thanks a lot for taking the time to do it.

Collectives™ on Stack Overflow

Recursive Array Traversal Problems

2 Answers 2

1 Comment

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related