无法弄清楚我的 A* 算法出了什么问题

本文关键字:什么 问题 算法 弄清楚 我的 | 更新日期: 2023-09-27 18:36:05

我目前正在我的 2D 横向卷轴游戏中实现 A* 寻路算法,但我遇到了一些困难。

以为我正确地实现了它,但显然不是,因为它不起作用。

我使用优先级队列来提高效率,并遵循此处讨论的算法:

http://www.codeproject.com/Articles/5758/Path-finding-in-C

但是,我没有使用他们的优先级队列,因为许多评论指出它有一些问题。相反,我使用以下优先级队列:

https://bitbucket.org/BlueRaja/high-speed-priority-queue-for-c/src

这是我的函数,然后我将讨论这个问题:

List<Waypoint> FindPathTo(Waypoint Goal)
{
    TileMath goalMath = TileMath.GetTileMath((int)Goal.x, (int)Goal.y);
    Waypoint startPt = new Waypoint((Vector2)this.transform.position);
    HeapPriorityQueue<Waypoint> OpenList = new HeapPriorityQueue<Waypoint>(MAX_NODES);
    HeapPriorityQueue<Waypoint> ClosedList = new HeapPriorityQueue<Waypoint>(MAX_NODES);
    List<Waypoint> Solution = new List<Waypoint>();
    OpenList.Enqueue(startPt, openPriority);
    openPriority--;
    print(Goal.GetPoint()); //testing
    print(OpenList.Count); //testing
    while (OpenList.Count > 0)
    {
        Waypoint CurrNode = OpenList.Dequeue();
        TileMath currMath = TileMath.GetTileMath((int)CurrNode.x, (int)CurrNode.y);
        if (currMath.GetXY() == goalMath.GetXY() && currMath.GetBlockID() == goalMath.GetBlockID()) // checks if the current node is the goal
        {
            while (CurrNode != null)
            {
                Solution.Insert(0, CurrNode);
                CurrNode = CurrNode.prev;
            }
            break;
        }
        List<Waypoint> successors = CurrNode.GetSuccessors();
        print(successors.Count);
        foreach (Waypoint w in successors)
        {
            Waypoint OpenWp = null;
            Waypoint ClosedWp = null;
            if(OpenList.Contains(w))
            {
                IEnumerator<Waypoint> ie = OpenList.GetEnumerator();
                while((int)ie.Current.x != (int)w.x && (int)ie.Current.y != (int)w.y && ie.Current != null)
                {
                    ie.MoveNext();
                }
                if (ie.Current == null)
                    print("IE ERROR. CHECK CONTAINS IN OPENLIST.");
                else
                    OpenWp = ie.Current;

                if (OpenWp != null && w.totalCost > OpenWp.totalCost)
                    continue;

            }
            if(ClosedList.Contains(w))
            {
                IEnumerator<Waypoint> ie = ClosedList.GetEnumerator();
                while ((int)ie.Current.x != (int)w.x && (int)ie.Current.y != (int)w.y && ie.Current != null)
                {
                    ie.MoveNext();
                }
                if (ie.Current == null)
                    print("IE ERROR. CHECK CONTAINS IN CLOSEDLIST.");
                else
                    ClosedWp = ie.Current;

                if (ClosedWp != null && w.totalCost > ClosedWp.totalCost)
                    continue;
            }
            if (OpenWp != null)
                OpenList.Remove(OpenWp);
            if (ClosedWp != null)
                ClosedList.Remove(ClosedWp);
            OpenList.Enqueue(w, openPriority);
            openPriority--;
            ClosedList.Enqueue(w, closedPriority);
            closedPriority--;

        }
    }
    return Solution;
}

基本上,我有返回航点列表的方法(非常简单的类,如果您有兴趣,这里有一个粘贴:http://pastebin.com/Sch5vRY3),但是在我的函数中,列表在返回时计数为 0,因此(错误地)指示没有到达该点的路径。

我已经完成了通常的调试,但是 A* 对我来说有点混乱,所以如果有人可以帮助我解决常见的陷阱,我将不胜感激。

我绝对是人工智能和寻路的新手,所以如果你有任何其他杂项指示,我全听!

谢谢。

无法弄清楚我的 A* 算法出了什么问题

好吧,我不会告诉确切的代码,但我会告诉什么是 A* 算法以及它在你的情况下是什么:
在 A* 中,我们定义了状态的两个函数:成本和启发式,成本意味着"从当前状态转移到另一个状态的成本是多少",在您的情况下,它应该是当前点和我将尝试的点之间的路径距离。
启发式意味着"我离目标有多远",在您的情况下,从我的位置到目标的距离可能会很大。
写完这两个函数后,你写了一个函数,我们称之为"f",它将两者相加。
A* 算法实际上是一种贪婪的回溯算法,您在其中尝试最少的"f"。