Unity 内存不足异常 List.Add()

Question

我正在实现A*搜索算法用于Unity3D中的FPS游戏（版本4.6.1）。目前，我有一组敌人prefab在游戏开始时生成，并附带一个名为Pathfinder.cs的脚本。在我的Pathfinder类中，每秒钟（如果我的目标更改节点），它会调用AStar.cs中的FindPath()来查找从自身到目标的新路径。目前，玩家是目标，因此多个敌人可以找到通往同一位置的路径。

我已经把所有问题解决了，敌人可以按预期找到路径。问题在于当我的玩家走动一段时间后（有时几步，有时更长时间），游戏突然卡住，任务管理器中的Unity.exe进程内存使用量飙升到2GB+（从约230MB），如果我停止场景，内存使用量也不会下降。有时Unity会解冻一秒钟以记录控制台中的错误。

OutOfMemoryException: Out of memory
System.Array.Resize[Node] (.Node[]& array, Int32 length, Int32 newSize) (at /Users/builduser/buildslave/mono-runtime-and-classlibs/build/mcs/class/corlib/System/Array.cs:1928)
System.Array.Resize[Node] (.Node[]& array, Int32 newSize) (at /Users/builduser/buildslave/mono-runtime-and-classlibs/build/mcs/class/corlib/System/Array.cs:1912)
System.Collections.Generic.List`1[Node].set_Capacity (Int32 value) (at /Users/builduser/buildslave/mono-runtime-and-classlibs/build/mcs/class/corlib/System.Collections.Generic/List.cs:622)
System.Collections.Generic.List`1[Node].GrowIfNeeded (Int32 newCount) (at /Users/builduser/buildslave/mono-runtime-and-classlibs/build/mcs/class/corlib/System.Collections.Generic/List.cs:100)
System.Collections.Generic.List`1[Node].Add (.Node item) (at /Users/builduser/buildslave/mono-runtime-and-classlibs/build/mcs/class/corlib/System.Collections.Generic/List.cs:91)
AStar.CalculatePath (.Node node) (at Assets/Scripts/AStar.cs:152)
AStar.FindPath (Vector3 startPos, Vector3 endPos) (at Assets/Scripts/AStar.cs:109)
Pathfinder.FindPath () (at Assets/Scripts/Pathfinder.cs:64)
Pathfinder.Update () (at Assets/Scripts/Pathfinder.cs:35)

错误指向我的 AStar.cs 脚本中的 list.Add(node)：

private static List<Node> CalculatePath(Node node) {
    List<Node> list = new List<Node>();
    while (node != null) {
        list.Add(node); //Error here
        node = node.parent;
    }
    list.Reverse();
    return list;
}

一开始我用的是ArrayList，但仍然出现了相同的错误。

重要提示：

只有当场景中存在多个敌人寻路时才会出现此错误。当只有一个敌人时不会出现此错误。我认为这是因为AStar类、开放列表和封闭列表是静态的，所以我试图将它们更改为在非静态环境中使用，但错误仍然发生。

我已经将我的AStar、Pathfinder和Node类粘贴到pastebin上：http://pastebin.com/4pQU9Pwc

非常感谢任何帮助！谢谢。

- Paul B

---

节点可能构成一个环吗？ - Jeffrey Zhang

但这并不能解释为什么会在不止一个敌人时发生。 - Paul B

好的，我认为可能是当一个敌人的路径与另一个敌人的路径相交以到达目标时。当我排列两个敌人，然后在它们前面走时，我可以重现这个问题。你有什么建议我该如何解决这个问题？ - Paul B

Answer 1

看起来可能存在一种循环逻辑，你正在将节点添加到列表中？在添加之前，你是否尝试过检查列表是否已包含该节点？

while (node != null) {
        if (!list.Contains(node)) {
            list.Add(node);
            node = node.parent;
        }
        else {
            break;
        }
    }

- Atra Viator

Answer 2

感谢 @Altra Viator 找到问题的原因，但最终路径仍然产生了奇怪的结果。我更改了 CalculatePath 方法，包括一个起始节点（敌人当前节点），并添加了一个简单的检查：

if(node == start) {
    break;
}

现在的方法看起来像这样：

private static List<Node> CalculatePath(Node node, Node start) {
    //Retrace the path back through each of the goal nodes parents (to the start node)
    List<Node> list = new List<Node>();
    while (node != null) {
        if (!list.Contains(node)) {
            list.Add(node);
            if(node == start) {
                break;
            }
            node = node.parent;
        }
        else {
            break;
        }
    }
    list.Reverse();
    return list;
}

- Paul B