c# - ¿Cómo implementar un algoritmo A*?

algorithm a-star

Question

¿Cuál debería ser la forma de obtener una implementación simple del algoritmo A * (A star) en C #?

Answer 1

En la función AStar, comenzamos creando un nuevo matrixNode, con los parámetros fromX y fromY. Un matrixNode tiene propiedades, "fr", que es la distancia de cualquier matrixNode dado desde el nodo inicial, una propiedad "to" que es la distancia de un matrixNode dado desde el matrixNode destino (sería ''E'' en las coordenadas (3,3 ) en el ejemplo de unitTest), y una propiedad "sum" que es la suma de "to" y "fr". La propiedad padre, es una referencia al matrixNode al que se movió el nodo dado en la ruta para llegar desde el nodo de inicio hasta el nodo final. Los diccionarios greens y reds, son openSet y closedSet respectivamente como se describe en la página del algoritmo de búsqueda A * en Wikipedia. La idea general de estos conjuntos es que estamos tratando de encontrar el matrixNode en el conjunto verde / abierto que tiene el valor de "suma" más bajo, ya que "sum" era la suma de las distancias del nodo desde el nodo de inicio en ( desde X, desde Y) y el nodo final en (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);
                }
            }
        }
    }

Answer 2

Este artículo explica la implementación básica en longitud:

El objetivo de esta publicación de blog es mostrar los fundamentos de A * a través de una implementación C # muy simple.

También apunta a mejores implementaciones, más adecuadas para el uso de producción:

En cuanto a las formas de encontrar mejores rutas, hay muchos ejemplos de C # que son mucho mejores y más ricos que este. CastorTiu tiene una solución de demostración realmente agradable en CodeProject, la implementación del algoritmo A * en C # , que anima el algoritmo de búsqueda y permite al usuario modificar algunas configuraciones. [...]

EpPathFinding.cs- Un algoritmo de búsqueda de ruta rápida (búsqueda de punto de salto) en C # (basado en cuadrícula) . Tiene una GUI agradable y clara y permite ajustar algunas configuraciones.