O algoritmo A * pathfinding da Wikipedia leva muito tempo

Eu implementei com êxito o pathfinding A * em C #, mas é muito lento e não entendo o porquê. Eu até tentei não classificar a lista openNodes, mas ainda é a mesma.

O mapa é 80x80 e há 10 a 11 nós.

Peguei o pseudocódigo daqui Wikipedia

E esta é a minha implementação:

 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;
    }

Aqui está a heurística que estou usando:

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

O que estou fazendo errado? É um dia inteiro que continuo olhando para o mesmo código.

Eu vejo três coisas, uma errada, duas suspeitas.

1) Você está classificando em todas as iterações. Não. Use uma fila de prioridade ou, no mínimo, faça uma pesquisa linear para encontrar o mínimo. Na verdade, você não precisa que a lista inteira seja classificada o tempo todo!

2) openNodes.Contains () provavelmente é lento (não tenho certeza sobre as especificidades da lista de C #, mas aposto que faz uma pesquisa linear). Você pode adicionar um sinalizador a cada nó e fazer isso em O (1).

3) GetNeighborNodes () pode ser lento.

Além do argumento já mencionado de que você deve usar uma pilha prioritária, você entendeu mal a heurística. Você tem

if (isCostBetter)
{
    ...
    neighbour.H = GetManhattanHeuristic (atual, vizinho);
}

if (openNodes.Contains (vizinho) == false)
{
    neighbour.H = GetHeuristic (neighbour, mEnd);
    ...
}

E como outro ponto menor, você pode simplificar o A * filtrando nós intransponíveis GetNeighbourNodes().

A meta-resposta: você nunca deve passar um dia olhando o código procurando por problemas de desempenho. Cinco minutos com um criador de perfil mostrariam exatamente onde estão os gargalos. Você pode baixar uma trilha gratuita da maioria dos criadores de perfil e conectá-la ao seu aplicativo em alguns minutos.

Não está claro o que você está comparando ao comparar o F de diferentes nós. F é uma propriedade definida como G + H? Deveria ser. (Disposição lateral: este é um exemplo de por que o princípio do acesso uniforme é uma porcaria.)

Mais importante, porém, você está reorganizando os nós a cada quadro. A * exige o uso de uma fila prioritária , que permite a inserção eficiente - O (lg n) - classificada de um único elemento e um conjunto, que permite verificações rápidas de nós fechados. Como você escreveu o algoritmo, você tem O (n lg n) inserção + classificação, o que aumenta o tempo de execução para proporções inúteis.

(Você pode obter inserção de O (n) + classificação se o C # tiver um bom algoritmo de classificação. Ainda é demais. Use uma fila de prioridade real.)

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

• Em um extremo, se h (n) é 0, então apenas g (n) desempenha um papel, e A * se transforma no algoritmo de Dijkstra, que é garantido que encontra um caminho mais curto.
• Se h (n) for sempre menor que (ou igual a) o custo de passar de n para a meta, é garantido que A * encontre o caminho mais curto. Quanto mais baixo h (n), mais o nó A * se expande, tornando-o mais lento.
• Se h (n) for exatamente igual ao custo de passar de n para a meta, A * seguirá apenas o melhor caminho e nunca expandirá mais nada, tornando-o muito rápido. Embora você não possa fazer isso acontecer em todos os casos, você pode torná-lo exato em alguns casos especiais. É bom saber que, com informações perfeitas, o A * se comportará perfeitamente.
• Se h (n) às vezes for maior que o custo de passar de n para a meta, não é garantido que A * encontre um caminho mais curto, mas ele pode correr mais rápido.
• No outro extremo, se h (n) é muito alto em relação a g (n), então apenas h (n) desempenha um papel e A * se transforma na melhor primeira pesquisa.

Você está usando 'manhatten distance'. Isso quase sempre é uma heurística ruim. Além disso, olhando essas informações da página vinculada, você pode supor que sua heurística é menor que o custo real.

Além das outras respostas principais (que são indubitavelmente mais significativas que essa sugestão), outra otimização é alterar a 'lista' fechada em algum tipo de tabela de hash. Você não precisa ser uma coleção ordenada, apenas para poder adicionar rapidamente valores e ver rapidamente se eles existem na coleção.

Seu custo e sua heurística precisam ter um relacionamento. Deveria ser uma pista que H é calculado em dois pontos diferentes, mas nunca acessado.