recursive + 900 elements + neighbor check = causes stackoverflow

Question

Hi,

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

Answer 3

An efficient, recursive algorithm should work provided you do clear the flags (I assume you're simply setting flags on whether a tile has power or not) before doing the recursion. Something like this:

void updateCell(position)
{
  for each direction (north, south, east, west) do the following:
  -- is there a cell there? (test for edges), if not, exit now;
  -- can it be powered? 
     false: exit now;
     true: set powered=true, call updateCell(this position);
}

void updatePowerGrid(start)
{
  clearPowerFlags();
  set powered=true for start;
  updateCell(start);
}

This should work well enough until you use really huge grid sizes.

Answer 4

You can make it iterative. Have two lists, one that keeps track of where you have been, and one that keeps track of where you are currently checking.

Psuedo Code with your code:

While(ToBeChecked is not empty) {
    //Note In python i'd be using a copy of the list so I could edit it without 
    //concequence during the iteration. ie for a in b[:]
    for each element in ToBeChecked
         updatePowerEnvironment(...);
         //Remove element you are checking        
         removeElementFromToBeChecked(...);
}

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);
        //call addElementToBeChecked instead and I beleive the above already 
        //makes sure it has not already been checked
        addElementToBeChecked(newId, elements);
    }
    newId = id + GameMap.mMapSize;
    if (newId < GameMap.mMapCells.size() && GameMap.mMapCells.get(newId).mPowerEnabled
            && !elements.contains(newId)) {
        elements.add(newId);
        addElementToBeChecked(newId, elements);
    }
    newId = id - 1;
    if (newId >= 0 && GameMap.mMapCells.get(newId).mPowerEnabled
            && !elements.contains(newId)) {
        elements.add(newId);
        addElementToBeChecked(newId, elements);
    }
    newId = id + 1;
    if (newId < GameMap.mMapCells.size()
            && GameMap.mMapCells.get(newId).mPowerEnabled
            && !elements.contains(newId)) {
        elements.add(newId);
        addElementToBeChecked(newId, elements);
    }
}

addElementToBeChecked(...) {
    ToBeChecked.add();
    //Some other stuff if needed
}
removeElemenToBeChecked(...) {
    ToBeChecked.remove();
    //Some other stuff if needed
}

Answer 5

The very first thing I would try is just to change the search order from North-South-West-East to North-East-South-West. Like this:

public void updatePowerEnvironment(int id, ArrayList<Integer> elements) { 
    if (!GameMap.ValidCellId(id))
        return;
    if (!GameMap.mMapCells.get(id).mPowerEnabled)
        return;
    if (elements.Contains(id))
        return;
    elements.Add(id);
    updatePowerEnvironment(id - GameMap.mMapSize, elements);
    updatePowerEnvironment(id + 1, elements);
    updatePowerEnvironment(id + GameMap.mMapSize, elements);
    updatePowerEnvironment(id - 1, elements);
}

This might reduce the recursion depth, depeding on the maps involved.