Единство: Как найти всех соседей рекурсивно (соседей соседей)?

Question

Я делаю игру Bubble Shooter в Unity. Я дошел до того, что смог ударить другой пузырь, и он уничтожил всех своих соседей.

Теперь я пытаюсь уничтожить всех соседей своих соседей, и это вызывает переполнение стека. Я использовал рекурсию.

Я сделал это без рекурсии и нашел соседей второго уровня, чтобы посмотреть, сработает ли логика. Оно делает. Проблема в том, как я использую рекурсию.

    private List<Bubble> FindAllRecursiveNeighbors(Vector2Int originPosition)
{
    List<Bubble> allNeighbors = FindNeighbors(originPosition);

    List<Bubble> result = new List<Bubble>();

    foreach (Bubble bubble in allNeighbors)
    {
        if (result.Contains(bubble)) { continue; }
        result.Add(bubble);
    }

    // Recursion starts here.
    foreach (Bubble bubble in result)
    {
        List<Bubble> neighbors = FindAllRecursiveNeighbors(FindPositionOfBubble(bubble));
        foreach (Bubble neighbor in neighbors)
        {
            if (result.Contains(neighbor)) { continue; }
            result.Add(neighbor);
        }
    }

    return result;
}

Я ожидал, что все пузырьки в линии будут уничтожены. Я получил ошибку переполнения стека. Если я удаляю рекурсивную часть, она работает, но только для ближайших соседей.

Ошибка заключается в следующем: StackOverflowException: запрошенная операция вызвала переполнение стека, и она находится в строке, где я вызываю FindAllRecursiveNeighborsеще раз.

Answer 1

Ваш шаблон правильный. Я полагаю, что исключение переполнения стека вызвано возвратом к уже посещенному узлу.

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

private List<Bubble> FindAllRecursiveNeighbors(Vector2Int originPosition, List<Bubble> result = null)
{
    List<Bubble> allNeighbors = FindNeighbors(originPosition);

    if (result == null)
        // Mark (see bellow)
        result = new List<Bubble>();

    var newBubbles = new List<Bubble>();
    foreach (Bubble bubble in allNeighbors)
    {
        if (!result.Contains(bubble))
        {
            result.Add(bubble);
            newBubbles.Add(bubble);
        }
    }

    // Recursion starts here.
    foreach (Bubble bubble in newBubbles)
    {
        List<Bubble> neighbors = FindAllRecursiveNeighbors(FindPositionOfBubble(bubble), result);
    }

    return result;
}

Хотя мне было непонятно одно. Проверьте, где я отметил в коде. Там вы должны добавить текущий узел в список, если ваша функция FindNeighbors не возвращает текущий узел.

В качестве окончательного объяснения, что происходит здесь, это: Предположим, у вас есть 3 узла, как этот 1 <-> 2<-> 3 Теперь вы начинаете с 1 и идете, чтобы проверить соседей 2, вы найдете 3, а также 1 снова, вы снова идете в цикле, чтобы проверить соседей 1, и этот цикл продолжается.

Лучший методЧтобы справиться с такой задачей, нужно иметь список неисследованных узлов и выбирать их с минимальной рекурсией. Но здесь я сохранил список уже посещенных узлов, который может увеличиваться в зависимости от количества узлов, которые вы хотите взорвать за одну операцию. Но это меньше изменений вашего исходного кода.