时间戳

首页 > 解决方案 > Unity：如何递归找到所有邻居（邻居的邻居）？

c# - Unity：如何递归找到所有邻居（邻居的邻居）？

问题描述

我正在 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 的行中。

标签： c#unity3drecursionstack-overflownearest-neighbor

解决方案

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

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

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

处理此类任务的最佳方法是拥有一个未搜索节点的列表，并从中选择几乎没有递归。但是，在这里我保留了一个已经访问过的节点的列表，根据您想要在单个操作中爆炸的节点数量，它可能会变得很重。但这对您的原始代码的更改较少。

推荐阅读