¿Cómo implementar un algoritmo A *?

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

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

El objective 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 muy agradable en CodeProject, la implementación del algoritmo A * en C # , que anima el algoritmo de búsqueda y permite al usuario ajustar algunas configuraciones. […]

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

En la función AStar, comenzamos creando un nuevo matrixNode, con los parámetros desde X y desde Y. Un matrixNode tiene propiedades, “fr” que es la distancia de cualquier matrixNode dado desde el nodo de inicio, una propiedad “to” que es la distancia de un matrixNode dado desde el matrixNode de destino (sería ‘E’ en las coordenadas (3,3 ) en el ejemplo de unitTest), y una propiedad “sum” que es la sum de “a” y “fr”. El padre de la propiedad es una referencia al matrixNode al que se movió el nodo dado en la ruta para llegar desde el nodo de inicio al 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 con estos conjuntos es que estamos tratando de encontrar el matrixNode en el conjunto verde / abierto que tiene el menor valor de “sum”, ya que “sum” fue la sum 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 path = new Stack(); 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 greens = new Dictionary(); //open Dictionary reds = new Dictionary(); //closed matrixNode startNode = new matrixNode { x = fromX, y = fromY }; string key = startNode.x.ToString() + startNode.x.ToString(); greens.Add(key, startNode); Func> smallestGreen = () => { KeyValuePair smallest = greens.ElementAt(0); foreach (KeyValuePair 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> fourNeighbors = new List>() { new KeyValuePair(-1,0), new KeyValuePair(0,1), new KeyValuePair(1, 0), new KeyValuePair(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 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 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); } } } } 
    Intereting Posts