XNA A*算法实现太耗时

Question

在我的 XNA 游戏中，我将 A* 实现为敌人行为的一部分，使用我自己的通用 PriorityQueue class。然而，实现方式太耗时了——以至于不到一秒的游戏时间需要大约 5 秒的实时时间。究竟是什么原因如此耗时，如何改变？

优先级表示为 int 而不是 float，因为当我尝试使用 float 时，游戏甚至无法开始。

我怀疑是操作次数的问题。在最后一帧结束时，在我更改了网格正方形的大小之后，评估节点的数量（用于找到从 (100, 100) 到 (0,0) 的无障碍路径）约为 800 或 305大小从 1 到 5。这改善了帧率下降，但仍然远不平滑。

关于该主题的大多数文章和堆栈交换问题都建议实施决胜局，我尝试将我的 h() 分数乘以 1.1、1.01 和 1.0001，none 改变了结果。可能我误解了什么。

另一个可能的选择是我的 PriorityQueue 效率不够高。诚然，我不知道如何提高效率，希望得到建议。

敌方成员及追击方法：

    #region data
    private IFocusable Target { get; set; }
    private Map WorldMap { get; set; }
    #endregion

    #region methods
    protected void Chase(GameTime gameTime)
    {
        PriorityQueue<Vector2> openSet = new PriorityQueue<Vector2>();
        List<Vector2> closedSet = new List<Vector2>();
        Dictionary<Vector2, Vector2> cameFrom = new Dictionary<Vector2, Vector2>();
        Dictionary <Vector2, int> gScores = new Dictionary<Vector2, int>();
        openSet.Enqueue(Heuristic(Position, Target.Position), Tools.RoundDown(Position));
        gScores.Add(Position, 0);
        while(openSet.Count != 0)
        {
            Vector2 current = openSet.Dequeue();
            if (current == Tools.RoundDown(Target.Position))
            {
                Position = ReconstructPath(cameFrom, current);
                break;
            }
            closedSet.Add(current);
            List<Vector2> neighbours = WorldMap.GetNeighbours(current, Speed);
            foreach (Vector2 neighbour in neighbours)
            {
                if (closedSet.Contains(neighbour))
                    continue;
                int tenativeGScore = gScores[current] + (int)Vector2.Distance(current, neighbour);
                if (openSet.Contains(neighbour) == -1 || tenativeGScore < gScores[neighbour])
                {
                    cameFrom[neighbour] = current;
                    gScores[neighbour] = tenativeGScore;
                    int fScore = tenativeGScore + Heuristic(neighbour, Target.Position);
                    openSet.Enqueue(fScore, neighbour);
                }
            }
        }
    }

    private Vector2 ReconstructPath(Dictionary<Vector2, Vector2> cameFrom, Vector2 currentNode)
    {
        if (cameFrom[currentNode] == Position)
            return currentNode;
        else
            return ReconstructPath(cameFrom, cameFrom[currentNode]);
    }

    //Heuristic: distance between neighbour and target, rounded down.
    private int Heuristic(Vector2 current, Vector2 goal)
    {
        return (int)Vector2.Distance(current, Tools.RoundDown(goal));
    }
    #endregion
}

优先队列：

public class PriorityQueue<T> where T : IEquatable<T>
{
    #region data
    private List<Tuple<int, T>> Items { get; set; }
    public int Count {get{return Items.Count;}}
    private bool Sorted { get; set; }
    #endregion

    #region c'tor
    public PriorityQueue()
    {
        this.Items = new List<Tuple<int,T>>();
        this.Sorted = true;
    }
    #endregion

    #region methods
    private int SortingMethod(Tuple<int, T> x, Tuple<int, T> y)
    {
        if (x == null || y == null)
            throw new ArgumentNullException();
        return x.Item1 - y.Item1;
    }
    public void Enqueue(Tuple<int, T> item)
    {
        int index = Contains(item.Item2);
        if (index == -1)
        {
            Items.Add(item);
            Sorted = false;
        }
        else
            Items[index] = item;
    }
    public void Enqueue(int key, T value)
    {
        Enqueue(new Tuple<int,T>(key, value));
    }
    public T Dequeue()
    {
        if(!Sorted)
        {
            Items.Sort(SortingMethod);
            Sorted = true;
        }
        Tuple<int, T> item = Items[0];
        Items.RemoveAt(0);
        return item.Item2;
    }
    public int Contains(T value)
    {
        for (int i = 0; i < Items.Count; i++ )
            if (Items[i].Equals(value))
                return i;
        return -1;
    }
    #endregion
}

Map 的相关成员（class 代表敌人导航的正方形地图。我没有来实现敌人避开被阻挡的正方形的机制。）：

    #region data
    private int SquareSize { get; set; }
    private List<Vector2> BlockedSquares { get; set; }
    private Rectangle Bounds { get; set; }
    #endregion

    public List<Vector2> GetNeighbours(Vector2 vector, int speed)
    {
        Vector2[] directions = new Vector2[8];
        List<Vector2> neighbours = new List<Vector2>();
        directions[0] = Tools.RoundDown(Vector2.UnitX);//right
        directions[1] = Tools.RoundDown(Vector2.UnitX);//left
        directions[2] = Tools.RoundDown(Vector2.UnitY);//down
        directions[3] = Tools.RoundDown(Vector2.UnitY);//up
        directions[4] = Tools.RoundDown(Vector2.UnitX + Vector2.UnitY);//down right
        directions[5] = Tools.RoundDown(-Vector2.UnitX + Vector2.UnitY);//down left
        directions[6] = Tools.RoundDown(Vector2.UnitX - Vector2.UnitY);//up right
        directions[7] = Tools.RoundDown(-Vector2.UnitX - Vector2.UnitY);//up left
        for (int i = (int)vector.X - speed; i <= (int)vector.X + speed; i += SquareSize)
        {
            for(int j = (int)vector.Y - speed; j <= (int)vector.Y + speed; j += SquareSize)
            {
                Vector2 point = new Vector2(i, j);
                if (point == vector)
                    continue;
                else if (Vector2.Distance(vector, point) <= speed)
                    neighbours.Add(point);
            }
        }
        return neighbours;
    }

    public Vector2 InSquare(Vector2 vector)
    {
        int x = (int)vector.X, y = (int)vector.Y;
        x -= x % SquareSize;
        y -= y % SquareSize;
        return new Vector2(x, y);
    }

希望这个答案不仅对我有帮助，而且对以后遇到类似问题的许多程序员也有帮助。

提前致谢。

Answer 1

尝试将 this.isFixedTimeStep = false; 放入您的 Initialize() 方法中。

Answer 2

减速的原因是使用低效的收容检查。具有快速包含检查的数据类型，如二叉搜索树、HashSet 等

在 closedSet 的情况下，我使用了 List 而不是 HashSet：

List<Vector2> closedSet = new List<Vector2>();

将更改为：

HashSet<Vector2> closedSet = new HashSet<Vector2>();

关于 closedSet 无需更改任何其他内容，因为这两种类型都具有 Add 和 Contains 函数。

对于 gScores，问题是我使用 ContainsKey 而不是更高效的 TryGetValue。基于 this answer.

if (openSet.Contains(neighbour) == -1 || tenativeGScore < gScores[neighbour])

需要改为：

float gScore;//Current gScores[neighbour] value, if there's any.
if(gScores.TryGetValue(neighbour, out gScore) || tenativeGScore < gScore)

XNA A*算法实现太耗时

XNA A* algorithm implementation too time-consuming

c#

performance

xna

a-star