recursive + 900 elements + neighbor check = causes stackoverflow

Question

I have a city simulation game and try to find a way to check the flow of our power system. The basics: The map for the city is based on tiles (30 by 30 tiles = 900 tiles). Now i start at a power plant and do a recursive neighbor check (top, left, right, bottom) to check if there is something that will transport the power. If there is something, I start checking this tiles for neighbors, too. To prevent double checks and/or infinite recursive calls, I fill a ArrayList with processed tiles and check if a new tile was already processed and added to the ArrayList...

Recursively started:

public void updatePowerEnvironment(int id, ArrayList<Integer> elements) {
    Log.w("GT", "update env for id: " + id);
    int newId = id - GameMap.mMapSize;
    if (newId >= 0 && GameMap.mMapCells.get(newId).mPowerEnabled
            && !elements.contains(newId)) {
        elements.add(newId);
        updatePowerEnvironment(newId, elements);
    }
    newId = id + GameMap.mMapSize;
    if (newId < GameMap.mMapCells.size() && GameMap.mMapCells.get(newId).mPowerEnabled
            && !elements.contains(newId)) {
        elements.add(newId);
        updatePowerEnvironment(newId, elements);
    }
    newId = id - 1;
    if (newId >= 0 && GameMap.mMapCells.get(newId).mPowerEnabled
            && !elements.contains(newId)) {
        elements.add(newId);
        updatePowerEnvironment(newId, elements);
    }
    newId = id + 1;
    if (newId < GameMap.mMapCells.size()
            && GameMap.mMapCells.get(newId).mPowerEnabled
            && !elements.contains(newId)) {
        elements.add(newId);
        updatePowerEnvironment(newId, elements);
    }
}

If I can trust the log output, no tile was tried to processed twice. That means, that I have no errors in the recursive calls. Which also means, the stack is simply too small.

Does someone have an idea how to avoid the stack limit?

[Update and my code as a result of Erics answer]

public void updatePowerEnvironment(int id, ArrayList<Integer> elements) {
    Stack<Integer> toProcess = new Stack<Integer>();
    toProcess.push(id);
    int mapSize = GameMap.mMapCells.size();
    while (!toProcess.empty()) {
        id = toProcess.pop();
        Log.e("GT", "id to process: " + id);
        if (elements.contains(id)) {
            continue;
        }
        int[] neighborIds = computeNeighbors(id);
        for (int neighbor : neighborIds) {
            if (neighbor < 0 || neighbor >= mapSize) {
                continue;
            }
            if (!GameMap.mMapCells.get(neighbor).mPowerEnabled) {
                continue;
            }
            toProcess.push(neighbor);
        }
        elements.add(id);
    }
}

private int[] computeNeighbors(int id) {
    return new int[] {id + GameMap.mMapSize, id - GameMap.mMapSize, id + 1, id - 1};
}

Answer 1

If I understand your problem correctly you are attempting to compute the transitive closure of the "is powered by" relation between two tiles. It is certainly possible to compute a transitive closure non-recursively.

Here's a non-recursive algorithm that computes the transitive closure of a relation in C#. You should be able to adapt that to the language of your choice.

http://blogs.msdn.com/b/ericlippert/archive/2010/02/08/making-the-code-read-like-the-spec.aspx

Note that basically what I'm doing here is avoiding the stack limit by allocating my own stack on the heap. That thing can grow as big as you like. (If you run out of heap memory then you've got bigger problems!)

Note also that it would be wise to choose a data structure that makes the "is a member of?" predicate extremely cheap. An array list of size n is usually O(n) to answer the question "is this element a member of this collection?" which means your algorithm is O(n^2) overall. Can you use a collection like a set or a hash table that has O(1) containment testing?

Also, on a purely "code quality" level, this method could use some work. The fact that there is so much duplicated code in there is a red flag. I would be inclined to write this method like this sketch:

Set<int> PoweredTiles(int powersource)
{
    Set<int> result = an empy set;
    Stack<int> stack = an empty stack;
    stack.Push(powersource);
    while (stack is not empty)
    {
        int current = stack.Pop();
        if (result.Contains(current)) continue;
        result.Add(current);
        int[] neighbours = { compute the neighbours }
        foreach(int neighbour in neighbours)
        {
            if (neighbour is not in range of grid) continue;
            if (neighbour is not a power carrier) continue;
            stack.Push(neighbour);
        }
    }
    return result;
}

Short, to the point, not recursive, no duplicated code, and O(n).

Answer 2

You just need to convert your recursive implementation into an iterative one (as theory tells us is always possible).

For example, you could:

• maintain a queue of cells-to-be-checked
• while this queue is not empty, process the front element
  • to process a cell, do whatever you have to do to the cell itself, then for each of its four nneighbours
  • if they are not already in the queue, add them to the queue
• repeat until the queue is empty