Unity：如何递归查找所有邻居（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;
}

我预计一行中的所有气泡都会被破坏。我收到堆栈溢出错误。如果我删除它的递归部分，但只适用于直接邻居。

错误是这样的：WhosebugException：请求的操作导致堆栈溢出，它在我再次调用 FindAllRecursiveNeighbors 的行中。

Answer 1

你的模式是正确的。我相信堆栈溢出异常是由 returning 到一个已经访问过的节点引起的。

您可能想要保留一个已经访问过的节点的列表，然后不要将它们 return 作为邻居。您已经拥有所需的东西，只需要进行装配即可。下面的代码可能对你有用

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 函数不是 return 当前节点，您应该将当前节点添加到列表中。

作为最终解释，这里发生的是：假设您有 3 个这样的节点 1 <-> 2 <-> 3 现在你从 1 开始，去检查 2 的邻居，你找到 3，然后又是 1，你再次进入循环检查 1 的邻居，这个循环继续。

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

Unity：如何递归查找所有邻居（neighbors of neighbors）？

Unity: How to find all neighbors recursively (neighbors of neighbors)?

c#

unity3d

recursion

stack-overflow

nearest-neighbor