c# - C# AStar 问题，不会正确执行

Question

我目前正在研究 A* 寻路，但我遇到了一些问题。在采取最佳路径之前，它会走错路。我究竟做错了什么？

源代码：http ://basic.apayostudios.com/AStar.zip

在线的：

Game.cs http://pastie.org/1656955

Node.cs http://pastie.org/1656956

枚举：

public enum NodeType
{
    None,
    Solid,
    Start,
    End
}

谢谢！

Answer 1

这是我的 A-star 路径查找器，它可以工作，你可以自由地使用它来学习和比较你的解决方案，如果你愿意，可以把我撕掉。但是这段代码中缺少一些依赖项，我正在使用定点算术。如果不进行一些更改，这将无法构建。此代码级别相对较高，应该很容易进行逆向工程。

public class AgentPathfinder
{
    class SolutionComparer : IComparer<Solution>
    {
        public int Compare(Solution x, Solution y)
        {
            return x.Cost.CompareTo(y.Cost);
        }
    }

    class Solution 
    {
        public List<FixedVector> Path { get; private set; }

        public FixedVector LastPosition { get { return Path[Path.Count - 1]; } }

        public Fixed32 Heuristic { get; set; }
        public Fixed32 Cost { get; set; }

        public Solution(FixedVector position, Fixed32 heuristic)
        {
            Path = new List<FixedVector>(2) { position };
            Heuristic = heuristic;
            Cost = Path.Count + heuristic;
        }

        public Solution(FixedVector position
            , Fixed32 heuristic
            , List<FixedVector> path)
        {
            Path = new List<FixedVector>(path) { position };
            Heuristic = heuristic;
            Cost = Path.Count + heuristic;
        }
    }

    // TODO: replace with pathable terrain data
    public Map Map { get; set; }

    public FixedVector Position { get; set; }
    public FixedVector Destination { get; set; }

    public List<FixedVector> Path { get; set; }

    public void Compute()
    {
        var visited = new bool[(int)Map.Size.Width, (int)Map.Size.Height];

        var pq = new PriorityQueue<Solution>(new SolutionComparer());

        var bestFit = new Solution(new FixedVector((int)(Position.X + 0.5)
            , (int)(Position.Y + 0.5))
            , (Destination - Position).Length
            );

        pq.Enqueue(bestFit);

        while (pq.Count > 0)
        {
            var path = pq.Dequeue(); // optimal, thus far
            if (path.Heuristic < bestFit.Heuristic) // best approximation?
            {
                // if we starve all other paths we
                // fallback to this, which should be the best
                // approximation for reaching the goal
                bestFit = path;
            }
            for (int i = 0; i < FixedVector.Adjacent8.Length; i++)
            {
                var u = path.LastPosition + FixedVector.Adjacent8[i];
                if (Map.Size.Contains(u))
                {
                    if (Map.IsPathable(u))
                    {
                        if (!visited[(int)u.X, (int)u.Y])
                        {
                            // heuristic (straight-line distance to the goal)
                            var h = (Destination - u).Length; 
                            var solution = new Solution(u, h, path.Path);
                            if (h < 1)
                            {
                                Path = solution.Path;
                                return; // OK, done
                            }
                            else
                            {
                                // keep looking
                                pq.Enqueue(solution);
                            }
                            visited[(int)u.X, (int)u.Y] = true;
                        }
                    }
                }
            }
        }

        Path = bestFit.Path;
    }
}