C# 如何实现 A* 算法？

How to implement an A* algorithm?

提问by A New Chicken

Which should be the way to get a simple implementation of A* (A star) algorithm in C#?

哪种方法应该是在 C# 中简单实现 A*（A 星）算法的方法？

回答by Derlin

This articleexplains the basic implementation in length:

这篇文章详细解释了基本实现：

The goal of this blog post is to show the fundamentals of A* through a really simple C# implementation.

这篇博文的目标是通过一个非常简单的 C# 实现来展示 A* 的基础知识。

It also points to better implementations, more suitable for production use:

它还指出了更好的实现，更适合生产使用：

As for ways to find better routes, there are plenty of C# examples around that are far better and richer than this one. CastorTiuhas a really nice demo solution on CodeProject, A* algorithm implementation in C#, that animates the search algorithm and allows the user to tweak a few settings. [...]

EpPathFinding.cs- A Fast Path Finding Algorithm (Jump Point Search) in C# (grid-based). It has a nice, clear GUI and allows a few settings to be tweaked.

至于如何找到更好的路线，周围有很多 C# 示例，它们比这个更好、更丰富。CastorTiu在 CodeProject 上有一个非常好的演示解决方案，C# 中的 A* 算法实现，它为搜索算法设置动画并允许用户调整一些设置。[...]

EpPathFinding.cs - C#（基于网格）中的快速路径查找算法（跳转点搜索）。它有一个漂亮、清晰的 GUI，并允许调整一些设置。

回答by Lee.O.

In the function AStar, we start by creating a new matrixNode, with the parameters fromX and fromY. A matrixNode has properties, "fr" which is the distance of any given matrixNode from the starting node, a "to" property which is the distance of a given matrixNode from the destination matrixNode (would be 'E' at coordinates (3,3) in the unitTest's example), and a property "sum" which is the sum of "to" and "fr". The property parent, is a reference to the matrixNode that the given node was moved to in the path for reaching from the start node to the end node. The dictionaries greens and reds, are the openSet and closedSet respectively as described in the A* search algorithmpage on Wikipedia. The general idea with these sets, is that we are trying to find the matrixNode in the green/open set which has the lowest "sum" value, as "sum" was the sum of the distances of the node from the start node at (fromX,fromY) and the end node at (toX, toY)

在函数 AStar 中，我们首先创建一个新的 matrixNode，参数为 fromX 和 fromY。矩阵节点具有属性，“fr”是任何给定矩阵节点与起始节点的距离，“to”属性是给定矩阵节点与目标矩阵节点的距离（在坐标 (3,3 ) 在 unitTest 的示例中)，以及一个属性“sum”，它是“to”和“fr”的总和。属性 parent 是对给定节点在从开始节点到达结束节点的路径中移动到的 matrixNode 的引用。字典 greens 和 reds 分别是A* 搜索算法中描述的 openSet 和 closedSet维基百科页面。这些集合的一般思想是，我们试图在绿色/开放集合中找到具有最低“总和”值的矩阵节点，因为“总和”是节点到起始节点的距离总和（ fromX,fromY) 和 (toX, toY) 处的结束节点

    public static void unitTest_AStar()
    {
        char[][] matrix = new char[][] { new char[] {'-', 'S', '-', '-', 'X'},
                                         new char[] {'-', 'X', 'X', '-', '-'},
                                         new char[] {'-', '-', '-', 'X', '-'},
                                         new char[] {'X', '-', 'X', 'E', '-'},
                                         new char[] {'-', '-', '-', '-', 'X'}};

        //looking for shortest path from 'S' at (0,1) to 'E' at (3,3)
        //obstacles marked by 'X'
        int fromX = 0, fromY = 1, toX = 3, toY = 3;
        matrixNode endNode = AStar(matrix, fromX, fromY, toX, toY);

        //looping through the Parent nodes until we get to the start node
        Stack<matrixNode> path = new Stack<matrixNode>();

        while (endNode.x != fromX || endNode.y != fromY)
        {
            path.Push(endNode);
            endNode = endNode.parent;
        }
        path.Push(endNode);

        Console.WriteLine("The shortest path from  " +
                          "(" + fromX + "," + fromY + ")  to " +
                          "(" + toX + "," + toY + ")  is:  \n");

        while (path.Count > 0)
        {
            matrixNode node = path.Pop();
            Console.WriteLine("(" + node.x + "," + node.y + ")");
        }
    }

    public class matrixNode
    {
        public int fr = 0, to = 0, sum = 0;
        public int x, y;
        public matrixNode parent;
    }

    public static matrixNode AStar(char[][] matrix, int fromX, int fromY, int toX, int toY)
    {
        ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
        // in this version an element in a matrix can move left/up/right/down in one step, two steps for a diagonal move.
        ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

        //the keys for greens and reds are x.ToString() + y.ToString() of the matrixNode 
        Dictionary<string, matrixNode> greens = new Dictionary<string, matrixNode>(); //open 
        Dictionary<string, matrixNode> reds = new Dictionary<string, matrixNode>(); //closed 

        matrixNode startNode = new matrixNode { x = fromX, y = fromY };
        string key = startNode.x.ToString() + startNode.x.ToString();
        greens.Add(key, startNode);

        Func<KeyValuePair<string, matrixNode>> smallestGreen = () =>
        {
            KeyValuePair<string, matrixNode> smallest = greens.ElementAt(0);

            foreach (KeyValuePair<string, matrixNode> item in greens)
            {
                if (item.Value.sum < smallest.Value.sum)
                    smallest = item;
                else if (item.Value.sum == smallest.Value.sum
                        && item.Value.to < smallest.Value.to)
                    smallest = item;
            }

            return smallest;
        };


        //add these values to current node's x and y values to get the left/up/right/bottom neighbors
        List<KeyValuePair<int, int>> fourNeighbors = new List<KeyValuePair<int, int>>()
                                            { new KeyValuePair<int, int>(-1,0),
                                              new KeyValuePair<int, int>(0,1),
                                              new KeyValuePair<int, int>(1, 0),
                                              new KeyValuePair<int, int>(0,-1) };

        int maxX = matrix.GetLength(0);
        if (maxX == 0)
            return null;
        int maxY = matrix[0].Length;

        while (true)
        {
            if (greens.Count == 0)
                return null;

            KeyValuePair<string, matrixNode> current = smallestGreen();
            if (current.Value.x == toX && current.Value.y == toY)
                return current.Value;

            greens.Remove(current.Key);
            reds.Add(current.Key, current.Value);

            foreach (KeyValuePair<int, int> plusXY in fourNeighbors)
            {
                int nbrX = current.Value.x + plusXY.Key;
                int nbrY = current.Value.y + plusXY.Value;
                string nbrKey = nbrX.ToString() + nbrY.ToString();
                if (nbrX < 0 || nbrY < 0 || nbrX >= maxX || nbrY >= maxY
                    || matrix[nbrX][nbrY] == 'X' //obstacles marked by 'X'
                    || reds.ContainsKey(nbrKey))
                    continue;

                if (greens.ContainsKey(nbrKey))
                {
                    matrixNode curNbr = greens[nbrKey];
                    int from = Math.Abs(nbrX - fromX) + Math.Abs(nbrY - fromY);
                    if (from < curNbr.fr)
                    {
                        curNbr.fr = from;
                        curNbr.sum = curNbr.fr + curNbr.to;
                        curNbr.parent = current.Value;
                    }
                }
                else
                {
                    matrixNode curNbr = new matrixNode { x = nbrX, y = nbrY };
                    curNbr.fr = Math.Abs(nbrX - fromX) + Math.Abs(nbrY - fromY);
                    curNbr.to = Math.Abs(nbrX - toX) + Math.Abs(nbrY - toY);
                    curNbr.sum = curNbr.fr + curNbr.to;
                    curNbr.parent = current.Value;
                    greens.Add(nbrKey, curNbr);
                }
            }
        }
    }