A-Star（A*）和通用查找方法

Question

我在有效实现Eric Lippert介绍的通用方法方面遇到了困难。他的博客概述了创建A星算法的一种非常简单而有效的方法（在这里找到）。以下是快速摘要。

实际路径查找的代码：

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);
    }
}

优先队列代码：

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 IHasNeighbours<N>
{
    IEnumerable<N> Neighbours { get; }
}

这是我遇到的难题。我可以创建一个可用于路径查找的类，但查找附近节点变得很麻烦。本质上，我创建了一个类，在这种情况下，它被视为单个瓷砖。但是，为了获取所有附近的节点，我必须将一个值传递给该瓷砖，其中包括所有其他瓷砖的列表。这非常麻烦，让我相信必须有一种更简单的方法。

以下是我的实现，使用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); });
    }

- Direweasel

---

嗯...我理解得对吗，invalidPoints列表是一组不可遍历的瓦片位置（也就是说，A搜索需要绕过它们）？这里有一个想法：为什么不只保留一个NxN的节点数组，代表每个可能的瓦片，并且每个节点都有一个附加的“遍历成本”，表示穿过该瓦片需要多长时间。然后你的无效瓦片只是具有无限大成本的节点（或者为了简单起见，类似于cost = int.MaxValue），A会很好地绕过它们。 - Daniel Pryden

为什么不生成一个完整的瓦片位置集，其中每个瓦片都有指向其邻居的指针呢？然后您可以生成此集合一次，将其存储在某个地方以便从中获取初始点，然后只需继续使用它。将任何无效的邻居保留为 null（如果要条件性地获取不可用地形，则此方法行不通，但您可以沿着相同的路线进行 improvisation）。 - JonBWalsh

Jon - 这正是接口 IHasNeighbours 的设计目的。上面的示例只要通过 List<Point> 传递，就会给我提供这个选项，但我觉得这样非常低效。我考虑过使用实现 IHasNeighbours 接口的主类，但无法实现这个目标。 - Direweasel

你的实现不太符合我的意思，因为邻居（上、下、左、右）的 getter 方法返回的是新的 TDGrid 点，而不是之前可以初始化的那些点。如果你有一些生成结构并且负责设置邻居(或在TDGrid上调用某些初始化方法)的类，你就可以做到不传递任何东西的无效点了。所以请将邻居存储为变量，并添加 Up、down、left、right 的 setter。目前问题在于，你似乎不断地初始化新的 TDGrid 对象。 - JonBWalsh

好的，我在 https://learn.microsoft.com/en-us/archive/blogs/ericlippert/path-finding-using-a-in-c-3-0-part-one 找到了它。提前警告一下，这个教程有四个部分（至少？）。 - RBarryYoung

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;
                }
            }
        }
    }
}

- Special Touch

---

这正是我所需要的，我使用的实现非常相似。谢谢！ - Direweasel

Answer 2

这是我最终采用的实现方式，与Special Touch的解决方案非常相似。SpacialObject是一个点。

public class Tile : SpacialObject, IHasNeighbours<Tile>
{
    public Tile(int x, int y)
        : base(x, y)
    {
        CanPass = true;
    }

    public bool CanPass { get; set; }

    public Point GetLocation(int gridSize)
    {
        return new Point(this.X * gridSize, this.Y * gridSize);
    }

    public IEnumerable<Tile> AllNeighbours { get; set; }
    public IEnumerable<Tile> Neighbours { get { return AllNeighbours.Where(o => o.CanPass); } }

    public void FindNeighbours(Tile[,] gameBoard)
    {
        var neighbours = new List<Tile>();

        var possibleExits = X % 2 == 0 ? EvenNeighbours : OddNeighbours;
        possibleExits = GetNeighbours;

        foreach (var vector in possibleExits)
        {
            var neighbourX = X + vector.X;
            var neighbourY = Y + vector.Y;

            if (neighbourX >= 0 && neighbourX < gameBoard.GetLength(0) && neighbourY >= 0 && neighbourY < gameBoard.GetLength(1))
                neighbours.Add(gameBoard[neighbourX, neighbourY]);
        }

        AllNeighbours = neighbours;
    }

    public static List<Point> GetNeighbours
    {
        get
        {
            return new List<Point>
            {
                new Point(0, 1),
                new Point(1, 0),
                new Point(0, -1),
                new Point(-1, 0),
            };
        }
    }

    public static List<Point> EvenNeighbours
    {
        get
        {
            return new List<Point>
            {
                new Point(0, 1),
                new Point(1, 1),
                new Point(1, 0),
                new Point(0, -1),
                new Point(-1, 0),
                new Point(-1, 1),
            };
        }
    }

    public static List<Point> OddNeighbours
    {
        get
        {
            return new List<Point>
            {
                new Point(0, 1),
                new Point(1, 0),
                new Point(1, -1),
                new Point(0, -1),
                new Point(-1, 0),
                new Point(-1, -1),
            };
        }
    }
}

然后在主程序中我使用了：

    private void InitialiseGameBoard()
    {
        GameBoard = new Tile[_Width, _Height];

        for (var x = 0; x < _Width; x++)
        {
            for (var y = 0; y < _Height; y++)
            {
                GameBoard[x, y] = new Tile(x, y);
            }
        }

        AllTiles.ToList().ForEach(o => o.FindNeighbours(GameBoard));

        int startX = 0, endX = GameBoard.GetLength(0) - 1;
        int startEndY = GameBoard.GetLength(1) / 2;
        _StartGridPoint = new Point(startX, startEndY);
        _EndGridPoint = new Point(endX, startEndY);
        //GameBoard[startX, startEndY].CanPass = false;
        //GameBoard[endX, startEndY].CanPass = false;
    }

    private void BlockOutTiles()
    {
        GameBoard[2, 5].CanPass = false;
        GameBoard[2, 4].CanPass = false;
        GameBoard[2, 2].CanPass = false;
        GameBoard[3, 2].CanPass = false;
        GameBoard[4, 5].CanPass = false;
        GameBoard[5, 5].CanPass = false;
        GameBoard[5, 3].CanPass = false;
        GameBoard[5, 2].CanPass = false;
    }

    public IEnumerable<Tile> AllTiles
    {
        get
        {
            for (var x = 0; x < _Width; x++)
                for (var y = 0; y < _Height; y++)
                    yield return GameBoard[x, y];
        }
    }

- Direweasel