如何实现A*算法？

Question

如何在C#中实现简单的A*（A星）算法？

- A New Chicken

---

指针在C#中是不安全的。/笑话 - kennytm

谢谢您，我想我找到了它，这里是链接：http://www.policyalmanac.org/games/aStarTutorial.htm - A New Chicken

一年半后，将这句话粘贴到Google中，你应该会找到这个页面和一个刻薄的评论，告诉你去做你刚才做的事情。 - Isabelle Wedin

4年过去了，我们仍然会在谷歌搜索框输入这句话，并找到这个页面，看到你那带讽刺意味的评论告诉我们要做正是你刚才说应该做的事情。 - edthethird

6年后，完全相同的Google搜索结果带我们来到这个无用的帖子，里面充满了嘲讽的评论和失效的链接。太好了，伙计们，我们成功地建造了一台时光机回到了1996年。 - Paul Lammertsma

Answer 1

这篇文章详细介绍了基本实现:

本博客旨在通过一个非常简单的C#实现展示A*的基础知识。

它也指向更适合生产使用的更好实现:

关于寻找更好路径的方法，有许多C#例子比这个更好更丰富。CastorTiu在CodeProject上有一个真正不错的演示解决方案，C#中实现A*算法，可以动画显示搜索算法并允许用户调整一些设置。[...]

EpPathFinding.cs- A Fast Path Finding Algorithm (Jump Point Search) in C# (grid-based)。它具有良好、清晰的GUI界面，允许调整一些设置。

- Derlin

Answer 2

在函数AStar中，我们首先创建一个新的matrixNode，其中包含参数fromX和fromY。一个matrixNode具有属性"fr"，该属性是从起始节点到任何给定matrixNode的距离，"to"属性是给定matrixNode到目标matrixNode（例如在unitTest示例中坐标为(3,3)处的'E'）的距离，并且属性"sum"是"to"和"fr"的总和。属性parent是指从起始节点到终止节点路径中给定节点被移动到的matrixNode的引用。字典greens和reds分别是开放集和关闭集，如A*搜索算法页面上所述。这些集合的一般思想是，我们尝试找到具有最低"sum"值的绿色/开放集中的matrixNode，因为"sum"是从(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);
                }
            }
        }
    }

- Lee.O.

---

小错误： 字符串键 = startNode.x.ToString() + startNode.x.ToString(); 应更改为 字符串键 = startNode.x.ToString() + startNode.y.ToString(); - V319