A* 路径查找算法并不总是找到最短路由 C# XNA

Question

我正在创建一个简单的XNA C#自上而下的游戏。在游戏中，您将在迷宫般的地图周围跟随一个敌人。自动取款机 我设置了它，以便在游戏开始时敌人找到通往您的最短路径（确实如此）。如果玩家移动了，则每秒都会找到一条新路径。

游戏总能找到一条通往你的路线，但似乎很难找到到达移动目标的最短路线，有时会在你移动时进入一个循环，当你停下来时，敌人会绕着地图走一半找到你，即使你只有几步之遥。它似乎不是启发式的，因为我删除了它（使其成为 dijkstra），它似乎仍然存在同样的问题。我认为这是我忽略的简单事情，但很难弄清楚是什么。

提前致谢

 class PathFinder
{
    private Cell[,] map = Game1.cellArray;

    public List<Cell> calculate(int currX, int currY, int destX, int destY)
    {
        resetMap();
        Debug.WriteLine("starting over");
        List<Cell> path = new List<Cell>();
        List<Cell> openList = new List<Cell>();
        List<Cell> closedList = new List<Cell>();
        Cell startPos = map[currY, currX];
        Cell endPos = map[destY, destX];
        startPos.closed = true;
        closedList.Add(startPos);

        Cell curPos = startPos;
        while (!closedList.Contains(endPos))
        {
            //add adjacent nodes to list, discover their scores
            foreach (Cell v in getAdj(curPos))
            {
                if (v.walkable == true && v.closed == false)
                {
                    if (!openList.Contains(v))
                    {
                        v.parent = curPos;
                        v.H = getH(v, endPos);
                        v.G = v.parent.G + 10;
                        v.F = v.G + v.H;
                        openList.Add(v);

                    }
                        //if square already on list would benefit from current tile being parent, make it so
                    else if (curPos.G + 10 < v.G)
                    {
                        v.parent = curPos;
                        v.G = v.parent.G + 10;
                        v.F = v.G + v.H;
                    }
                }
            }
            if (openList.Count <= 1) {/*Console.WriteLine("Returned NULL");*/ return null; }
            curPos = openList[1];
            curPos.closed = true;
            closedList.Add(curPos);
            openList[1] = openList[openList.Count - 1];
            openList.RemoveAt(openList.Count - 1);
            openList.OrderBy(o => o.F);
            openList.Reverse();
        }
        //backtrack to discover path
        Cell curNode = endPos;
        path.Add(endPos);
        while (curNode != startPos)
        {
            curNode = curNode.parent;
            path.Add(curNode);
            Debug.WriteLine("Path// X: " + curNode.xLocation + " Y: " + curNode.yLocation);
        }
        path.Reverse();
        return path;
    }
    //finds heuristic of current square by checking distance to destination ignoring walls 
    private int getH(Cell curPos, Cell endPos)
    {
        int diffX = curPos.xLocation - endPos.xLocation;
        int diffY = curPos.yLocation - endPos.yLocation;
        if (diffX < 0)
        {
            diffX *= -1;
        }
        if (diffY < 0)
        {
            diffY *= -1;
        }
        return ((diffX + diffY) * 10);
    }
    //get list of adjacent Cells
    private List<Cell> getAdj(Cell curPos)
    {
        List<Cell> adjList = new List<Cell>();
       if (curPos.xLocation - 1 >= 0){
            adjList.Add(map[curPos.yLocation, curPos.xLocation - 1]);
        }
        if (curPos.xLocation < 19)
        {
            adjList.Add(map[curPos.yLocation, curPos.xLocation + 1]);
        }
        if (curPos.yLocation - 1 >= 0)
        {
            adjList.Add(map[curPos.yLocation - 1, curPos.xLocation]);
        }
        if (curPos.yLocation < 19)
        {
            adjList.Add(map[curPos.yLocation + 1, curPos.xLocation]);
        }

        return adjList;
    }
    private void resetMap()
    {
        //reset Cells to default values
        for (int r = 0; r < map.GetLength(1); r++)
        {
            for (int c = 0; c < map.GetLength(0); c++)
            {
                map[r, c].reset();
            }
        }
    }
}

Answer 1

刚刚解决了问题。在更改当前选定的磁贴之前未排序。我以为我给他们打错了分数，哈哈。