Unity气泡射击游戏递归查找所有邻居引发栈溢出问题求助

嘿，我一眼就看出问题所在了——你的递归代码完全没有标记哪些气泡已经被处理过，导致同一个气泡会被反复递归调用，无限循环下去，最终触发StackOverflowException。比如气泡A的邻居是B，B的邻居又包含A，递归就会在A和B之间来回跳，直到栈被撑爆。

咱们来拆解下你现有代码的核心问题：

• 每次递归调用都会重新查找当前气泡的邻居，但没有任何机制记录哪些气泡已经被处理过，重复递归在所难免。
• result是每个递归栈帧里的局部列表，没法在递归调用之间共享已访问的状态，这就导致同一个气泡会被多次加入递归流程。

修复方案：添加已访问集合跟踪状态 #

最直接的解决办法是给递归方法加一个HashSet<Bubble>参数，用来记录已经处理过的气泡，避免重复递归。修改后的代码如下：

private List<Bubble> FindAllRecursiveNeighbors(Vector2Int originPosition, HashSet<Bubble> visited = null) {
    // 第一次调用时初始化已访问集合
    if (visited == null) {
        visited = new HashSet<Bubble>();
    }

    List<Bubble> result = new List<Bubble>();
    List<Bubble> directNeighbors = FindNeighbors(originPosition);

    foreach (Bubble bubble in directNeighbors) {
        // 跳过已访问过的气泡，避免重复递归
        if (visited.Contains(bubble)) {
            continue;
        }
        // 标记为已访问，防止后续递归再处理它
        visited.Add(bubble);
        result.Add(bubble);
        // 递归处理当前气泡的邻居，传递同一个已访问集合
        List<Bubble> recursiveNeighbors = FindAllRecursiveNeighbors(FindPositionOfBubble(bubble), visited);
        result.AddRange(recursiveNeighbors);
    }

    return result;
}

为什么这样能解决问题？

1. HashSet的高效查询：它的Contains方法是O(1)时间复杂度，比你原来用的List.Contains（O(n)）高效得多，尤其是气泡数量多的时候。
2. 共享已访问状态：所有递归调用共用同一个visited集合，确保每个气泡只会被处理一次，从根源上切断了无限递归的可能。
3. 友好的调用方式：我们给visited设置了默认值null，第一次调用方法时不需要传这个参数，内部会自动初始化。

额外建议：考虑非递归遍历（更稳定） #

递归虽然代码简洁，但如果你的气泡链特别长（比如几百个连续的气泡），还是有可能触发栈溢出（因为C#的栈深度有限）。这种情况下，非递归的广度优先搜索（BFS）或者深度优先搜索（DFS）会更稳定，比如用队列实现BFS：

private List<Bubble> FindAllNeighborsNonRecursive(Vector2Int originPosition) {
    List<Bubble> result = new List<Bubble>();
    HashSet<Bubble> visited = new HashSet<Bubble>();
    Queue<Vector2Int> queue = new Queue<Vector2Int>();

    queue.Enqueue(originPosition);

    while (queue.Count > 0) {
        Vector2Int currentPos = queue.Dequeue();
        List<Bubble> neighbors = FindNeighbors(currentPos);

        foreach (Bubble bubble in neighbors) {
            if (!visited.Contains(bubble)) {
                visited.Add(bubble);
                result.Add(bubble);
                queue.Enqueue(FindPositionOfBubble(bubble));
            }
        }
    }

    return result;
}

这种方式完全不会受栈深度限制，适合处理大规模的节点遍历场景。

内容的提问来源于stack exchange，提问作者e-mag