c# - A-Star (A*) 和通用查找方法

Question

我在有效实现 Eric Lippert 推荐的这个通用方法时遇到了问题。他的博客概述了创建 A 星算法的一种非常简单有效的方法 (found here)。这是快速运行。

实际寻路的代码:

class Path<Node> : IEnumerable<Node>
{
    public Node LastStep { get; private set; }
    public Path<Node> PreviousSteps { get; private set; }
    public double TotalCost { get; private set; }
    private Path(Node lastStep, Path<Node> previousSteps, double totalCost)
    {
        LastStep = lastStep;
        PreviousSteps = previousSteps;
        TotalCost = totalCost;
    }
    public Path(Node start) : this(start, null, 0) { }
    public Path<Node> AddStep(Node step, double stepCost)
    {
        return new Path<Node>(step, this, TotalCost + stepCost);
    }
    public IEnumerator<Node> GetEnumerator()
    {
        for (Path<Node> p = this; p != null; p = p.PreviousSteps)
            yield return p.LastStep;
    }
    IEnumerator IEnumerable.GetEnumerator()
    {
        return this.GetEnumerator();
    }
}

class AStar
{

    static public Path<Node> FindPath<Node>(
        Node start,
        Node destination,
        Func<Node, Node, double> distance,
        Func<Node, double> estimate)
        where Node : IHasNeighbours<Node>
    {
        var closed = new HashSet<Node>();
        var queue = new PriorityQueue<double, Path<Node>>();
        queue.Enqueue(0, new Path<Node>(start));
        while (!queue.IsEmpty)
        {
            var path = queue.Dequeue();
            if (closed.Contains(path.LastStep))
                continue;
            if (path.LastStep.Equals(destination))
                return path;
            closed.Add(path.LastStep);
            foreach (Node n in path.LastStep.Neighbours)
            {
                double d = distance(path.LastStep, n);
                if (n.Equals(destination))
                    d = 0;
                var newPath = path.AddStep(n, d);
                queue.Enqueue(newPath.TotalCost + estimate(n), newPath);
            }
        }
        return null;
    }

    /// <summary>
    /// Finds the distance between two points on a 2D surface.
    /// </summary>
    /// <param name="x1">The IntPoint on the x-axis of the first IntPoint</param>
    /// <param name="x2">The IntPoint on the x-axis of the second IntPoint</param>
    /// <param name="y1">The IntPoint on the y-axis of the first IntPoint</param>
    /// <param name="y2">The IntPoint on the y-axis of the second IntPoint</param>
    /// <returns></returns>
    public static long Distance2D(long x1, long y1, long x2, long y2)
    {
        //     ______________________
        //d = &#8730; (x2-x1)^2 + (y2-y1)^2
        //

        //Our end result
        long result = 0;
        //Take x2-x1, then square it
        double part1 = Math.Pow((x2 - x1), 2);
        //Take y2-y1, then sqaure it
        double part2 = Math.Pow((y2 - y1), 2);
        //Add both of the parts together
        double underRadical = part1 + part2;
        //Get the square root of the parts
        result = (long)Math.Sqrt(underRadical);
        //Return our result
        return result;
    }

    /// <summary>
    /// Finds the distance between two points on a 2D surface.
    /// </summary>
    /// <param name="x1">The IntPoint on the x-axis of the first IntPoint</param>
    /// <param name="x2">The IntPoint on the x-axis of the second IntPoint</param>
    /// <param name="y1">The IntPoint on the y-axis of the first IntPoint</param>
    /// <param name="y2">The IntPoint on the y-axis of the second IntPoint</param>
    /// <returns></returns>
    public static int Distance2D(int x1, int y1, int x2, int y2)
    {
        //     ______________________
        //d = &#8730; (x2-x1)^2 + (y2-y1)^2
        //

        //Our end result
        int result = 0;
        //Take x2-x1, then square it
        double part1 = Math.Pow((x2 - x1), 2);
        //Take y2-y1, then sqaure it
        double part2 = Math.Pow((y2 - y1), 2);
        //Add both of the parts together
        double underRadical = part1 + part2;
        //Get the square root of the parts
        result = (int)Math.Sqrt(underRadical);
        //Return our result
        return result;
    }

    public static long Distance2D(Point one, Point two)
    {
        return AStar.Distance2D(one.X, one.Y, two.X, two.Y);
    }
}

PriorityQueue代码:

class PriorityQueue<P, V>
{
    private SortedDictionary<P, Queue<V>> list = new SortedDictionary<P, Queue<V>>();
    public void Enqueue(P priority, V value)
    {
        Queue<V> q;
        if (!list.TryGetValue(priority, out q))
        {
            q = new Queue<V>();
            list.Add(priority, q);
        }
        q.Enqueue(value);
    }
    public V Dequeue()
    {
        // will throw if there isn’t any first element!
        var pair = list.First();
        var v = pair.Value.Dequeue();
        if (pair.Value.Count == 0) // nothing left of the top priority.
            list.Remove(pair.Key);
        return v;
    }
    public bool IsEmpty
    {
        get { return !list.Any(); }
    }
}

以及获取附近节点的接口(interface):

interface IHasNeighbours<N>
{
    IEnumerable<N> Neighbours { get; }
}

这是我难以有效实现的部分。我可以创建一个能够被路径查找使用的类，但是查找附近的节点变得很痛苦。本质上，我最终要做的是创建一个类，在这种情况下，该类被视为单个图 block 。但是，为了获得附近的所有节点，我必须将一个值传递到该图 block 中，其中包含所有其他图 block 的列表。这非常麻烦，让我相信一定有更简单的方法。

这是我使用 System.Drawing.Point 包装器实现的:

class TDGrid : IHasNeighbours<TDGrid>, IEquatable<TDGrid>
{
    public Point GridPoint;
    public List<Point> _InvalidPoints = new List<Point>();
    public Size _GridSize = new Size();
    public int _GridTileSize = 50;

    public TDGrid(Point p, List<Point> invalidPoints, Size gridSize)
    {
        GridPoint = p;
        _InvalidPoints = invalidPoints;
        _GridSize = gridSize;
    }

    public TDGrid Up(int gridSize)
    {
        return new TDGrid(new Point(GridPoint.X, GridPoint.Y - gridSize));
    }
    public TDGrid Down(int gridSize)
    {
        return new TDGrid(new Point(GridPoint.X, GridPoint.Y + gridSize));
    }
    public TDGrid Left(int gridSize)
    {
        return new TDGrid(new Point(GridPoint.X - gridSize, GridPoint.Y));
    }
    public TDGrid Right(int gridSize)
    {
        return new TDGrid(new Point(GridPoint.X + gridSize, GridPoint.Y));
    }

    public IEnumerable<TDGrid> IHasNeighbours<TDGrid>.Neighbours
    {
        get { return GetNeighbours(this); }
    }

    private List<TDGrid> GetNeighbours(TDGrid gridPoint)
    {
        List<TDGrid> retList = new List<TDGrid>();
        if (IsGridSpotAvailable(gridPoint.Up(_GridTileSize)))
            retList.Add(gridPoint.Up(_GridTileSize)); ;
        if (IsGridSpotAvailable(gridPoint.Down(_GridTileSize)))
            retList.Add(gridPoint.Down(_GridTileSize));
        if (IsGridSpotAvailable(gridPoint.Left(_GridTileSize)))
            retList.Add(gridPoint.Left(_GridTileSize));
        if (IsGridSpotAvailable(gridPoint.Right(_GridTileSize)))
            retList.Add(gridPoint.Right(_GridTileSize));
        return retList;
    }

    public bool IsGridSpotAvailable(TDGrid gridPoint)
    {
        if (_InvalidPoints.Contains(gridPoint.GridPoint))
            return false;

        if (gridPoint.GridPoint.X < 0 || gridPoint.GridPoint.X > _GridSize.Width)
            return false;
        if (gridPoint.GridPoint.Y < 0 || gridPoint.GridPoint.Y > _GridSize.Height)
            return false;

        return true;
    }

    public override int GetHashCode()
    {
        return GridPoint.GetHashCode();
    }

    public override bool Equals(object obj)
    {
        return this.GridPoint == (obj as TDGrid).GridPoint;
    }

    public bool Equals(TDGrid other)
    {
        return this.GridPoint == other.GridPoint;
    }
}

List _InvalidPoints 是我失败的地方。我可以将其传递给创建的每个 TDGrid，但考虑到所有其余代码的简单程度，这似乎是对资源的巨大浪费。我知道这对我来说是缺乏知识，但我无法搜索到它。

必须有另一种实现方式:

interface IHasNeighbours<N>
{
    IEnumerable<N> Neighbours { get; }
}

有人对此有任何想法吗？

编辑 -- 这是寻路代码:

    public void FindPath(TDGrid start, TDGrid end)
    {
        AStar.FindPath<TDGrid>(start, end, (p1, p2) => { return AStar.Distance2D(p1.GridPoint, p2.GridPoint); }, (p1) => { return AStar.Distance2D(p1.GridPoint, end.GridPoint); });
    }

Answer 1

听起来您在这里有两个不同的问题。您需要表示节点和节点本身之间的路径。您可能会发现分别表示这两个概念最简单。

例如，在下面的代码中，Grid 类跟踪节点的连接方式。这可能就像存储作为墙壁(即被阻挡)的瓷砖的散列集一样简单。要确定节点是否可达，请检查它是否在哈希集中。这只是一个简单的例子。还有许多其他方法可以表示图形，请参阅 Wikipedia .

单个节点可以表示为网格上的两个坐标，只需要三个值:行、列和网格本身。这允许动态创建每个单独的节点 (Flyweight pattern)。

希望对您有所帮助!

class Grid
{
    readonly int _rowCount;
    readonly int _columnCount;

    // Insert data for master list of obstructed cells
    // or master list of unobstructed cells

    public Node GetNode(int row, int column)
    {
        if (IsOnGrid(row, column) && !IsObstructed(row, column))
        {
            return new Node(this, row, column);
        }

        return null;
    }

    private bool IsOnGrid(int row, int column)
    {
        return row >= 0 && row < _rowCount && column >= 0 && column < _columnCount;
    }

    private bool IsObstructed(int row, int column)
    {
        // Insert code to check whether specified row and column is obstructed
    }
}

class Node : IHasNeighbours<Node>
{
    readonly Grid _grid;
    readonly int _row;
    readonly int _column;

    public Node(Grid grid, int row, int column)
    {
        _grid = grid;
        _row = row;
        _column = column;
    }

    public Node Up
    {
        get
        {
            return _grid.GetNode(_row - 1, _column);
        }
    }

    public Node Down
    {
        get
        {
            return _grid.GetNode(_row + 1,_column);
        }
    }

    public Node Left
    {
        get
        {
            return _grid.GetNode(_row, _column - 1);
        }
    }

    public Node Right
    {
        get
        {
            return _grid.GetNode(_row, _column + 1);
        }
    }

    public IEnumerable<Node> Neighbours
    {
        get
        {
            Node[] neighbors = new Node[] {Up, Down, Left, Right};
            foreach (Node neighbor in neighbors)
            {
                if (neighbor != null)
                {
                    yield return neighbor;
                }
            }
        }
    }
}