Wikipedia Algorytm poszukiwania ścieżki * zajmuje dużo czasu

Z powodzeniem zaimplementowałem wyszukiwanie ścieżek A * w języku C #, ale jest to bardzo wolne i nie rozumiem dlaczego. Próbowałem nawet nie sortować listy openNodes, ale nadal jest taka sama.

Mapa ma wymiary 80 x 80 i jest 10–11 węzłów.

Wziąłem pseudokod z tutaj Wikipedii

A to moja realizacja:

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

Oto heurystyka, której używam:

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

Co ja robię źle? Cały dzień patrzę na ten sam kod.

Widzę trzy rzeczy, jedną błędną, dwie podejrzaną.

1) Sortujesz według każdej iteracji. Nie rób Użyj kolejki priorytetowej lub przynajmniej przeprowadź wyszukiwanie liniowe, aby znaleźć minimum. W rzeczywistości przez cały czas nie potrzebujesz sortować całej listy!

2) openNodes.Contains () jest prawdopodobnie wolny (nie jestem pewien, co do specyfiki listy C #, ale założę się, że wykonuje wyszukiwanie liniowe). Możesz dodać flagę do każdego węzła i zrobić to w O (1).

3) GetNeighborNodes () może być powolny.

Oprócz tego, że już powiedziałeś, że powinieneś używać sterty priorytetowej, źle zrozumiałeś heurystykę. Ty masz

if (isCostBetter)
{
    ...
    neighbour.H = GetManhattanHeuristic (bieżący, sąsiad);
}

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

Kolejnym drobnym punktem jest uproszczenie A * poprzez odfiltrowanie nieprzekraczalnych węzłów GetNeighbourNodes().

Meta-odpowiedź: nigdy nie powinieneś spędzać dnia wpatrując się w kod w poszukiwaniu problemów z wydajnością. Pięć minut z profilerem pokaże dokładnie, gdzie są wąskie gardła. Możesz pobrać bezpłatną ścieżkę większości profilerów i podłączyć ją do swojej aplikacji w ciągu kilku minut.

Nie jest jasne, co porównujesz, porównując F różnych węzłów. Czy F jest właściwością zdefiniowaną jako G + H? Powinno być. (Side-rant: Jest to przykład tego, dlaczego zasada jednolitego dostępu to bzdura.)

Co ważniejsze, ponownie sortujesz węzły w każdej ramce. A * wymaga użycia kolejki priorytetowej , która umożliwia wydajne - O (lg n) - posortowane wstawianie pojedynczego elementu oraz zestawu, który umożliwia szybkie sprawdzanie zamkniętych węzłów. Gdy napisałeś algorytm, masz O (n lg n) wstawianie + sortowanie, co podnosi czas działania do bezużytecznych proporcji.

(Możesz uzyskać wstawienie O (n) + sortowanie, jeśli C # ma dobry algorytm sortowania. To wciąż za dużo. Użyj prawdziwej kolejki priorytetowej.)

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

• W jednym ekstremum, jeśli h (n) wynosi 0, to tylko g (n) odgrywa rolę, a A * zamienia się w algorytm Dijkstry, który gwarantuje znalezienie najkrótszej ścieżki.
• Jeśli h (n) jest zawsze niższe niż (lub równe) koszt przejścia od n do celu, A * gwarantuje znalezienie najkrótszej ścieżki. Im niższa h (n), tym bardziej węzeł A * rozszerza się, przez co jest wolniejszy.
• Jeśli h (n) jest dokładnie równe kosztowi przejścia od n do celu, A * podąży tylko najlepszą ścieżką i nigdy nie rozszerzy niczego innego, co czyni ją bardzo szybką. Chociaż nie możesz tego zrobić we wszystkich przypadkach, możesz to zrobić dokładnie w niektórych szczególnych przypadkach. Miło wiedzieć, że przy doskonałej informacji A * będzie się zachowywać idealnie.
• Jeśli h (n) jest czasami wyższy niż koszt przejścia od n do celu, A * nie ma gwarancji znalezienia najkrótszej ścieżki, ale może biegać szybciej.
• Z drugiej strony, jeśli h (n) jest bardzo wysokie w stosunku do g (n), wtedy tylko h (n) odgrywa rolę, a A * zamienia się w Najlepsze wyszukiwanie.

Używasz „dystansu manhattena”. Jest to prawie zawsze zła heurystyka. Ponadto, patrząc na te informacje z połączonej strony, możesz zgadywać, że heurystyka jest niższa niż rzeczywisty koszt.

Oprócz innych najważniejszych odpowiedzi (które są niewątpliwie ważniejsze niż ta sugestia), kolejną optymalizacją jest zmiana zamkniętej „listy” w pewnego rodzaju tablicę skrótów. Nie musisz być kolekcją uporządkowaną, aby móc szybko dodawać wartości i szybko sprawdzać, czy istnieją w kolekcji.

Twój koszt i heurystyka muszą mieć związek. Powinno być wskazówką, że H jest obliczane w dwóch różnych punktach, ale nigdy nie jest dostępne.