El algoritmo de búsqueda de ruta de Wikipedia A * lleva mucho tiempo

He implementado con éxito la ruta de acceso A * en C # pero es muy lento y no entiendo por qué. Incluso intenté no ordenar la lista openNodes pero sigue siendo la misma.

El mapa es 80x80, y hay 10-11 nodos.

Tomé el pseudocódigo de aquí Wikipedia

Y esta es mi implementación:

 public static List<PGNode> Pathfind(PGMap mMap, PGNode mStart, PGNode mEnd)
    {
        mMap.ClearNodes();

        mMap.GetTile(mStart.X, mStart.Y).Value = 0;
        mMap.GetTile(mEnd.X, mEnd.Y).Value = 0;

        List<PGNode> openNodes = new List<PGNode>();
        List<PGNode> closedNodes = new List<PGNode>();
        List<PGNode> solutionNodes = new List<PGNode>();

        mStart.G = 0;
        mStart.H = GetManhattanHeuristic(mStart, mEnd);

        solutionNodes.Add(mStart);
        solutionNodes.Add(mEnd);

        openNodes.Add(mStart); // 1) Add the starting square (or node) to the open list.

        while (openNodes.Count > 0) // 2) Repeat the following:
        {
            openNodes.Sort((p1, p2) => p1.F.CompareTo(p2.F));

            PGNode current = openNodes[0]; // a) We refer to this as the current square.)

            if (current == mEnd)
            {
                while (current != null)
                {
                    solutionNodes.Add(current);
                    current = current.Parent;
                }

                return solutionNodes;
            }

            openNodes.Remove(current);
            closedNodes.Add(current); // b) Switch it to the closed list.

            List<PGNode> neighborNodes = current.GetNeighborNodes();
            double cost = 0;
            bool isCostBetter = false;

            for (int i = 0; i < neighborNodes.Count; i++)
            {
                PGNode neighbor = neighborNodes[i];
                cost = current.G + 10;
                isCostBetter = false;

                if (neighbor.Passable == false || closedNodes.Contains(neighbor))
                    continue; // If it is not walkable or if it is on the closed list, ignore it.

                if (openNodes.Contains(neighbor) == false)
                {
                    openNodes.Add(neighbor); // If it isn’t on the open list, add it to the open list.
                    isCostBetter = true;
                }
                else if (cost < neighbor.G)
                {
                    isCostBetter = true;
                }

                if (isCostBetter)
                {
                    neighbor.Parent = current; //  Make the current square the parent of this square. 
                    neighbor.G = cost;
                    neighbor.H = GetManhattanHeuristic(current, neighbor);
                }
            }
        }

        return null;
    }

Aquí está la heurística que estoy usando:

    private static double GetManhattanHeuristic(PGNode mStart, PGNode mEnd)
    {
        return Math.Abs(mStart.X - mEnd.X) + Math.Abs(mStart.Y - mEnd.Y);
    }

¿Qué estoy haciendo mal? Es un día entero que sigo mirando el mismo código.

Veo tres cosas, una equivocada, dos sospechosas.

1) Estás ordenando en cada iteración. No lo hagas Utilice una cola de prioridad o, como mínimo, realice una búsqueda lineal para encontrar el mínimo. ¡En realidad no necesita que se ordene toda la lista en todo momento!

2) openNodes.Contains () es probablemente lento (no estoy seguro acerca de los detalles de la Lista de C #, pero apuesto a que hace una búsqueda lineal). Puede agregar una bandera a cada nodo y hacer esto en O (1).

3) GetNeighborNodes () podría ser lento.

Además del punto ya señalado de que debe usar un montón prioritario, ha entendido mal la heurística. Tienes

if (isCostBetter)
{
    ...
    neighbour.H = GetManhattanHeuristic (actual, vecino);
}

if (openNodes.Contains (vecino) == falso)
{
    vecino.H = GetHeuristic (vecino, mEnd);
    ...
}

Y como otro punto menor, podría simplificar el A * al filtrar los nodos intransitables GetNeighbourNodes().

La meta respuesta: nunca debes pasar un día mirando el código buscando problemas de rendimiento. Cinco minutos con un perfilador le mostrarán exactamente dónde están los cuellos de botella. Puede descargar un rastro gratuito de la mayoría de los perfiladores y conectarlo a su aplicación en unos minutos.

No está claro qué está comparando cuando compara la F de diferentes nodos. ¿Es F una propiedad definida como G + H? Debería ser. (Incitación lateral: este es un ejemplo de por qué el principio de acceso uniforme es una mierda).

Sin embargo, lo más importante es que está reordenando los nodos en cada cuadro. A * requiere el uso de una cola prioritaria , que permite la inserción ordenada eficiente - O (lg n) de un único elemento, y un conjunto, que permite verificaciones rápidas para nodos cerrados. Como ha escrito el algoritmo, tiene O (n lg n) inserción + clasificación, lo que eleva el tiempo de ejecución a proporciones inútiles.

(Es posible que obtenga O (n) inserción + clasificación si C # tiene un buen algoritmo de clasificación. Todavía es demasiado. Utilice una cola de prioridad real).

http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html

• En un extremo, si h (n) es 0, entonces solo g (n) juega un papel, y A * se convierte en el algoritmo de Dijkstra, que garantiza encontrar el camino más corto.
• Si h (n) es siempre menor (o igual) al costo de pasar de n a la meta, entonces A * tiene garantizado encontrar el camino más corto. Cuanto menor es h (n), más se expande el nodo A *, haciéndolo más lento.
• Si h (n) es exactamente igual al costo de pasar de n a la meta, entonces A * solo seguirá el mejor camino y nunca expandirá nada más, lo que lo hace muy rápido. Aunque no puede hacer que esto suceda en todos los casos, puede hacerlo exacto en algunos casos especiales. Es bueno saber que, dada la información perfecta, A * se comportará perfectamente.
• Si h (n) es a veces mayor que el costo de pasar de n a la meta, entonces A * no tiene la garantía de encontrar el camino más corto, pero puede correr más rápido.
• En el otro extremo, si h (n) es muy alto en relación con g (n), entonces solo h (n) juega un papel, y A * se convierte en Mejor-Primera-Búsqueda.

Estás utilizando 'distancia de manhatten'. Esto casi siempre es una mala heurística. Además, al mirar esa información desde la página vinculada, puede adivinar que su heurística es más baja que el costo real.

Además de las otras respuestas principales (que sin duda son más significativas que esta sugerencia), otra optimización es cambiar la 'lista' cerrada en algún tipo de tabla hash. No es necesario que sea una colección ordenada, solo para poder agregar valores rápidamente y ver rápidamente si existen en la colección.

Su costo y su necesidad heurística de tener una relación. Debería ser una pista de que H se calcula en dos puntos diferentes pero nunca se accede.