统一A*寻路崩溃

Question

所以我试着实现A*算法。基本逻辑几乎完成了，但有一个问题，我就是不能解决。

当请求路径，统一停止响应，我的PC一直变慢，直到它挂起，我不得不强制关闭。

以下是简化的代码：

public static List<Node> ReturnPath(Vector3 pointA, Vector3 pointB)
{
    /* A Bunch of initializations */

    while (!pathFound) 
    {
        //add walkable neighbours to openlist
        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;

        }

        //check openList for lowest fcost or lower 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)) 
            {
                //make the currentNode = node with lowest fcost
                currentNode = openList [i];
            }
            openList.Remove (currentNode);
            if(!closedList.Contains(currentNode))
                closedList.Add (currentNode);
        }

        //Check if the currentNode it destination
        if (currentNode == B) 
        {
            Debug.Log ("Path Detected");
            path = RetracePath (A, B);
            pathFound = true;
        }

    }
    return path;
}

只要目标在两个节点之外，就可以正常工作。如果不是这样，就会出现上面提到的问题。为什么会这样呢？我最初的猜测是，我把太多的钱投入了openList。

注意:我把一个30×30单元的平台(地板)分成1x1个正方形，称为“节点”( 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) might be better because it handles the possibility of a non existant path
    {
        //Set to arbitrary element
        currentNode = openList [0];

        //Check openList for lowest fcost or lower 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))) 
            {
                //Make the currentNode = node with lowest fcost
                currentNode = openList [i];
            }
        }

        //Check if the currentNode is destination
        if (currentNode.hCost == 0) //Better than if(currentNode == B)
        {
            path = RetracePath (A, B);
            pathFound = true;
        }

        //Add walkable neighbours to openlist
        foreach (Node n in GetNeighbours(currentNode)) 
        {
            //Avoid wasting time checking unwalkable and those already checked
            if (!n.walkable || closedList.Contains(n))
                continue;

            //Movement Cost to neighbour
            int newGCost = currentNode.gCost + GetManDist (currentNode, n);

            //Calculate g_Cost, Update if new g_cost to neighbour is less than an already calculated one
            if (n.gCost > newGCost || !openList.Contains (n)) 
            {
                n.gCost = newGCost;
                n.hCost = GetManDist (n, B);
                n.parent = currentNode; //So we can retrace
                openList.Add (n);
            }
        }
        //We don't need you no more...
        openList.Remove (currentNode);

        //Avoid redundancy of nodes in closedList
        if(!closedList.Contains(currentNode))
            closedList.Add (currentNode);

    }

    return path;
}

Answer 1

问题在于currentNode的价值。由于我们正在检查f_Cost最低或h_Cost较低的节点( openlist against currentNode )，在某些情况下，当路径发现遇到墙壁时，它必须返回或转弯，从而导致f_Cost和h_Cost增加(两者都大于currentNode)。因此，开放列表中不再有任何节点具有较低的f_成本/h_成本，从而导致无限循环。简单的解决方案是每次将currentNode设置为openList中的任意元素。

添加

currentNode = openlist[0];

在循环开始的时候。