我在尝试实现A*算法时，基本逻辑已经完成，但有一个问题我无法解决。

当请求路径时，Unity停止响应，我的电脑变得越来越慢，直到挂起，我不得不强制关闭。

这是简化的代码：

public static List<Node> ReturnPath(Vector3 pointA, Vector3 pointB){    /* 一系列初始化 */    while (!pathFound)     {        //将可行走的邻居节点添加到开放列表中        foreach (Node n in GetNeighbours(currentNode))         {            if (!n.walkable)                continue;            n.gCost = currentNode.gCost + GetManDist (currentNode, n);            n.hCost = GetManDist (n, B);            openList.Add (n);            n.parent = currentNode;        }        //在开放列表中查找fCost最低或hCost较低的节点        for (int i = 0; i < openList.Count; i++)         {            if ((openList [i].fCost < currentNode.fCost) || (openList [i].fCost == currentNode.fCost && openList [i].hCost < currentNode.hCost))             {                //将currentNode设置为fCost最低的节点                currentNode = openList [i];            }            openList.Remove (currentNode);            if(!closedList.Contains(currentNode))                closedList.Add (currentNode);        }        //检查当前节点是否为目标节点        if (currentNode == B)         {            Debug.Log ("路径已检测到");            path = RetracePath (A, B);            pathFound = true;        }    }    return path;}

只要目标节点距离两个节点以内，这段代码运行正常。如果距离更远，上述问题就会出现。这是为什么呢？我首先猜测是我在开放列表中放入了太多节点。

备注：我将一个30 x 30单位的平台（地板）分成1×1的方格，称为“节点”。GetManDist()用于获取两个节点之间的曼哈顿距离。

更新：这是可用的代码。评论区太长了无法放入

    public List<Node> ReturnPath(Vector3 pointA, Vector3 pointB){    List<Node> openList = new List<Node>();    List<Node> closedList = new List<Node>();    List<Node> path = new List<Node> ();    Node A = ToNode (pointA);    Node B = ToNode (pointB);    Node currentNode;    bool pathFound = false;    A.hCost = GetManDist(A, B);    A.gCost = 0;    openList.Add (A);    while (!pathFound) // while(openList.Count > 0) 可能更好，因为它处理了路径不存在的可能性    {        //设置为任意元素        currentNode = openList [0];        //在开放列表中查找fCost最低或hCost较低的节点        for (int i = 0; i < openList.Count; i++)         {            if ((openList [i].fCost < currentNode.fCost) || ((openList [i].fCost == currentNode.fCost && openList [i].hCost < currentNode.hCost)))             {                //将currentNode设置为fCost最低的节点                currentNode = openList [i];            }        }        //检查当前节点是否为目标节点        if (currentNode.hCost == 0) //比if(currentNode == B)更好        {            path = RetracePath (A, B);            pathFound = true;        }        //将可行走的邻居节点添加到开放列表中        foreach (Node n in GetNeighbours(currentNode))         {            //避免浪费时间检查不可行走的节点和已检查的节点            if (!n.walkable || closedList.Contains(n))                continue;            //移动到邻居节点的成本            int newGCost = currentNode.gCost + GetManDist (currentNode, n);            //计算g_Cost，如果新g_cost到邻居节点小于已计算的g_cost，则更新            if (n.gCost > newGCost || !openList.Contains (n))             {                n.gCost = newGCost;                n.hCost = GetManDist (n, B);                n.parent = currentNode; //以便我们可以回溯                openList.Add (n);            }        }        //我们不再需要你了...        openList.Remove (currentNode);        //避免closedList中节点的冗余        if(!closedList.Contains(currentNode))            closedList.Add (currentNode);    }    return path;}

回答：

问题出在currentNode的值上。由于我们在开放列表中检查f_Cost最低或h_Cost较低的节点与currentNode进行比较，在某些情况下，当路径查找遇到墙壁时，它必须返回或转弯，这会导致f_Cost和h_Cost增加（两者都大于currentNode的）。因此，开放列表中不再有f_Cost/h_Cost更低的节点，导致无限循环。简单的解决方案是在每次循环开始时将currentNode设置为开放列表中的任意元素。

添加

currentNode = openlist[0];

在循环开始时。