递归+ 900个元素+邻居检查=导致stackoverflow

Question

我有一个城市模拟游戏,并试图找到一种方法来检查我们的电力系统的流量.基础知识:城市地图基于图块(30 x 30个图块= 900个图块).现在我从一家发电厂开始,做一个递归的邻居检查(上,左,右,下),检查是否有东西会传输电力.如果有什么东西,我也开始检查邻居的这个瓷砖.为了防止双重检查和/或无限递归调用,我使用已处理的tile填充ArrayList并检查是否已经处理了新tile并将其添加到ArrayList ...

递归开始:

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);
    }
}

如果我可以信任日志输出,则没有尝试过两次瓷砖.这意味着,我在递归调用中没有错误.这也意味着,堆栈太小了.

有人知道如何避免堆栈限制吗？

[更新和我的代码作为Erics答案的结果]

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

如果我正确理解你的问题,你试图计算两个瓦片之间"由...驱动"关系的传递闭包.当然可以非递归地计算传递闭包.

这是一个非递归算法,用于计算C#中关系的传递闭包.您应该能够根据您选择的语言进行调整.

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

请注意,基本上我在这里做的是通过在堆上分配我自己的堆栈来避免堆栈限制.那东西可以随你想的那样大.(如果你的堆内存耗尽,那么你就会遇到更大的问题!)

还要注意,选择一个使"成为？"的数据结构是明智的.谓词非常便宜.大小为n的数组列表通常是O(n)来回答问题"这个元素是这个集合的成员吗？" 这意味着你的算法总体上是O(n ^ 2).你可以使用像集合或散列表那样的集合来进行O(1)包含测试吗？

此外,在纯粹的"代码质量"级别上,此方法可以使用一些工作.事实上,存在如此多的重复代码是一个红旗.我倾向于像这个草图一样编写这个方法:

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;
}

简而言之,不是递归的,没有重复的代码和O(n).