c# - 统一: How to find all neighbors recursively (neighbors of neighbors)?

Question

我正在 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 的邻居，这个循环继续。

解决此类任务的最佳方法是拥有一个未搜索节点的列表，并从中选择很少的递归。但是，在这里我保留了一个已经访问过的节点的列表，这可能会变得很重，具体取决于您要在单个操作中分解的节点数量。但这对您的原始代码更改较少。