Ich habe A * Pathfinding erfolgreich in C # implementiert, aber es ist sehr langsam und ich verstehe nicht warum. Ich habe sogar versucht, die openNodes-Liste nicht zu sortieren, aber sie ist immer noch dieselbe.
Die Karte ist 80x80 und es gibt 10-11 Knoten.
Ich habe den Pseudocode von hier Wikipedia genommen
Und das ist meine Implementierung:
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;
}
Hier ist die Heuristik, die ich verwende:
private static double GetManhattanHeuristic(PGNode mStart, PGNode mEnd)
{
return Math.Abs(mStart.X - mEnd.X) + Math.Abs(mStart.Y - mEnd.Y);
}
Was mache ich falsch? Es ist ein ganzer Tag, an dem ich immer wieder denselben Code betrachte.
Antworten:
Ich sehe drei Dinge, eines falsch, zwei verdächtig.
1) Sie sortieren nach jeder Iteration. Tu es nicht. Verwenden Sie entweder eine Prioritätswarteschlange oder führen Sie zumindest eine lineare Suche durch, um das Minimum zu finden. Sie müssen nicht immer die gesamte Liste sortieren!
2) openNodes.Contains () ist wahrscheinlich langsam (nicht sicher über die Besonderheiten der C # -Liste, aber ich wette, es wird eine lineare Suche durchgeführt). Sie können jedem Knoten ein Flag hinzufügen und dies in O (1) tun.
3) GetNeighborNodes () kann langsam sein.
quelle
Zusätzlich zu dem bereits erwähnten Punkt, dass Sie einen Prioritätshaufen verwenden sollten, haben Sie die Heuristik falsch verstanden. Du hast
if (isCostBetter) { ... neighbour.H = GetManhattanHeuristic (aktuell, Nachbar); }}Die Heuristik soll jedoch eine Schätzung für die Entfernung zum Ziel sein. Sie sollten es einmal einstellen, wenn Sie den Nachbarn zum ersten Mal hinzufügen:if (openNodes.Contains (Nachbar) == false) { neighbour.H = GetHeuristic (Nachbar, mEnd); ... }}Und als weiteren kleinen Punkt könnten Sie das A * vereinfachen, indem Sie unpassierbare Knoten herausfiltern
GetNeighbourNodes().quelle
Die Meta-Antwort: Sie sollten niemals nur einen Tag damit verbringen, auf Code zu starren, um nach Leistungsproblemen zu suchen. Fünf Minuten mit einem Profiler zeigen Ihnen genau, wo die Engpässe liegen. Sie können einen kostenlosen Trail der meisten Profiler herunterladen und ihn in wenigen Minuten an Ihre App anschließen.
quelle
Es ist nicht klar, was Sie vergleichen, wenn Sie das F verschiedener Knoten vergleichen. Ist F eine Eigenschaft, die als G + H definiert ist? Es sollte sein. (Side-Rant: Dies ist ein Beispiel dafür, warum das Prinzip des einheitlichen Zugangs Mist ist.)
Wichtiger ist jedoch, dass Sie die Knoten in jedem Frame neu sortieren. A * erfordert die Verwendung einer Prioritätswarteschlange , die das effiziente Einfügen eines einzelnen Elements nach O (lg n) ermöglicht, und einer Menge, die eine schnelle Überprüfung auf geschlossene Knoten ermöglicht. Während Sie den Algorithmus geschrieben haben, haben Sie O (n lg n) Einfügung + Sortierung, was die Laufzeit auf nutzlose Proportionen erhöht.
(Sie erhalten möglicherweise O (n) Einfügung + Sortierung, wenn C # über einen guten Sortieralgorithmus verfügt. Es ist immer noch zu viel. Verwenden Sie eine Warteschlange mit echter Priorität.)
quelle
http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html
Sie verwenden "Manhatten-Abstand". Dies ist fast immer eine schlechte Heuristik. Wenn Sie sich diese Informationen auf der verlinkten Seite ansehen, können Sie außerdem erraten, dass Ihre Heuristik niedriger ist als die tatsächlichen Kosten.
quelle
Zusätzlich zu den anderen Top-Antworten (die zweifellos wichtiger sind als dieser Vorschlag) besteht eine weitere Optimierung darin, die geschlossene "Liste" in eine Art Hash-Tabelle zu ändern. Sie müssen keine geordnete Sammlung sein, nur um schnell Werte hinzufügen und schnell feststellen zu können, ob sie in der Sammlung vorhanden sind.
quelle
Ihre Kosten und Ihre Heuristik müssen eine Beziehung haben. Es sollte ein Hinweis darauf sein, dass H an zwei verschiedenen Stellen berechnet wird, aber nie abgerufen wird.
quelle