рекурсивный + 900 элементов + проверка соседей = вызывает переполнение стека

Question

У меня есть игра-симулятор города, и я пытаюсь найти способ проверить работу нашей энергосистемы.Основы: карта города основана на тайлах (30 на 30 тайлов = 900 тайлов).Теперь я начинаю на электростанции и выполняю рекурсивную проверку соседей (сверху, слева, справа, снизу), чтобы проверить, есть ли что-то, что будет передавать энергию.Если что-то есть, я тоже начинаю проверять эту плитку на соседей.Чтобы предотвратить двойные проверки и / или бесконечные рекурсивные вызовы, я заполняю ArrayList обработанными плитками и проверяю, была ли новая плитка уже обработана и добавлена ​​в 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).

Answer 2

Вам просто нужно преобразовать вашу рекурсивную реализацию в итеративную (как говорит теория, это всегда возможно).

Например, вы могли бы:

• поддерживать очередь проверяемых ячеек
• пока эта очередь не пуста, обработайте передний элемент
  • чтобы обработать ячейку, сделайте все, что вам нужно сделать с самой ячейкой, затем для каждой из четырех ее соседей
  • если их еще нет в очереди, добавьте их в очередь
• повторять до тех пор, пока очередь не станет пустой

Answer 3

Самое первое, что я бы попробовал, это просто изменить порядок поиска с Север-Юг-Запад-Восток на Север-Восток-Юго-Запад.Примерно так:

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

Это может уменьшить глубину рекурсии, углубляясь в соответствующие карты.

Answer 4

Вы можете сделать это итеративным. Имейте два списка, один, который отслеживает, где вы были, и другой, который отслеживает, где вы проверяете.

Код Psuedo с вашим кодом:

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

Эффективный рекурсивный алгоритм должен работать при условии, что вы очищаете флаги (я полагаю, вы просто устанавливаете флаги на то, имеет ли плитка мощность или нет) перед выполнением рекурсии. Примерно так:

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

Это должно работать достаточно хорошо, пока вы не используете очень большие размеры сетки.