STL Container und Vorgehen bei A*

[BeRsErKeR]

Ich bau mir grad einen kleinen A*-Algo für mein RPG. Ich wollte für die OpenList und ClosedList eigentlich STL Container nutzen (also kein boost oder andere libs). Natürlich dachte ich zuerst an std::priority_queue. Prinzipiell eine schöne Sache und mit einem eigenen kleinen Comparator kann man auch die Node-Zeiger richtig sortieren. Problematisch ist, dass es keine contains-Methode oder ähnliches gibt um festzustellen, ob ein Node bereits in der Liste ist. Daher hatte ich mich für ein std::set entschieden. Hier wird ja auch sortiert und ich kann den selben Comparator nutzen um sicher zu stellen, dass das "beste" Node immer vorn (oder hinten) ist.

Mein Problem ist nun folgendes: Wenn ich ein Node (die sind bei mir an Positionen bzw. Tiles gebunden) prüfe, muss ich ja gucken ob es schon in der ClosedList oder OpenList ist. In den Listen speichere ich Pointer auf Nodes. Allerdings kenne ich bei der Prüfung nur den Pointer auf das aktuell zu prüfende Node und nur die Positionen der umliegenden Felder (Nodes) [Hinweis: Ich prüfe hier ob die 8 umliegenden Felder/Nodes bereits in der OpenList oder ClosedList sind um zu entscheiden ob ich sie hinzufügen muss, ihre Werte anpasse oder sie nicht nochmals prüfe]. Wie soll ich also feststellen ob das Node schon in der Liste ist, wenn ich die Pointeradresse nicht kenne?

Dazu hatte ich dann folgende Ideen (das Node speichert übigrens intern die Position). Ich nutze eine std::map mit der Position als Key. Nachteil: Die Elemente werden nicht mehr nach Node-Priorität, sondern nach Position geordnet. Ich komme im Comparator von den Positionen (welche ja die Parameter sind) nicht an die zugehörigen Node-Pointer ran. Und aus dem Comparator auf die map zuzugreifen ist sehr böse bzw. ruft dann weitere Mal den Comparator auf. Hab schon viel rumgetrickst aber das muss doch einfacher gehen.

Ich weiß ich kann mir da selbst was bauen, aber würd gern die STL Container nutzen.

Mein Problem ist einfach, dass ich Node-Pointer im Container nach der Priorität (g-Wert) ordnen will, aber auch prüfen können muss, ob ein Node (anhand der Position!) bereits in der Liste ist. Ich habe beim Check ob das Node in der Liste ist also nur die Position.

Steh vermutlich gerade etwas auf dem Schlauch.

Danke für Hinweise.

[Jonathan]

Hm, du speicherst Pointer auf die Nodes in dem set, und wilslt prüfen ob ein Pointer in dem set drinn ist? Irgendwie versteh ich nicht ganz das Problem.

Notfalls könnte es eine Idee sein, 2 Container anzulegen, einem mit dem du schnell prüfen kannst, ob Elemente nach Pointer enthalten sind und einen, auf den du über die Position zugreifen kannst. Solange du Elemente immer in beiden hinzufügst oder löschst, kannst du dann den ersten dazu benutzen, zu prüfen ob ein Element im zweiten enthalten ist. Dieses Objekt hast du davon zwar noch nicht, aber du musst ja scheinbar nur wissen, ob du es irgendwo im Container hast.

[waigie]

Wenn ich mich da recht an meine Erfahrungen mit dem A* erinner, wirst du bei einfachen Containern aus der STL immer dieses Problem haben. Die sind auf eine bestimmt Zugriffsart optimiert. Also entweder über einen Schlüssel (map) oder sortiert (priority queue) beides ist da nicht möglich.
Auch wenn du dir deine Container selbst implementierst wirst du da einige Probleme bekommen um das ganze möglichst performant hinzubekommen. Genau das gleiche hast du wenn du 2 Container nutzt.

Ich hab das ganze auf einen recht kleinen Terrain gemacht 127*127 Felder, dabei konnte ich einiges an Performance, indem ich Container nutze die auf die Inhaltsprüfung optimiert waren. Du prüfst pro Feld 8 (im worst case) Nachbarfelder ob sie in einer der 2 Listen vorhanden sind, macht also 16 contains Operationen. Daher ist es wichtig das gerade diese Prüfung sehr schnell läuft, das ermitteln des geringsten G Wertes machst du nur 1 mal pro Feld, das war bei mir mit einem einfachen Bubblesort gerade noch schnell genug, auch wenn es sicherlich auch hier Optimierungsaufwand gab.

Was ich damit ausdrücken will. Versuch einfach mal eine nur auf eine Zugriffsart ausgelegte Liste zu verwenden. Bei mir war es eine Map bzw. Hashmap (man kann für jedes Feld einen eindeutigen Hash berechnen). Ich denke das du so schon genug performance erhält um die 2 Abfrage einfach mit einem Iterator implementieren kannst.
Dazu muss man immer bedenken das eine Struktur die Positions- und Sortierungsinformationen speichert beim Einfügen und Löschen recht lange braucht, da die Bäume neu ausbalanciert werden müssen. Das alles kostet wieder extra Zeit und steigt mit komplexeren Strukturen an.

[BeRsErKeR]

Danke erstmal für die Antworten.

Hm, du speicherst Pointer auf die Nodes in dem set, und wilslt prüfen ob ein Pointer in dem set drinn ist? Irgendwie versteh ich nicht ganz das Problem.

Notfalls könnte es eine Idee sein, 2 Container anzulegen, einem mit dem du schnell prüfen kannst, ob Elemente nach Pointer enthalten sind und einen, auf den du über die Position zugreifen kannst. Solange du Elemente immer in beiden hinzufügst oder löschst, kannst du dann den ersten dazu benutzen, zu prüfen ob ein Element im zweiten enthalten ist. Dieses Objekt hast du davon zwar noch nicht, aber du musst ja scheinbar nur wissen, ob du es irgendwo im Container hast.

Ich möchte nicht prüfen ob ein Pointer drin ist. Ich habe eine Liste mit Pointern, will aber wissen ob ein Node mit einer bestimmten Position (ist eine Member der Node) in der Liste ist.

Wenn ich mich da recht an meine Erfahrungen mit dem A* erinner, wirst du bei einfachen Containern aus der STL immer dieses Problem haben. Die sind auf eine bestimmt Zugriffsart optimiert. Also entweder über einen Schlüssel (map) oder sortiert (priority queue) beides ist da nicht möglich.
Auch wenn du dir deine Container selbst implementierst wirst du da einige Probleme bekommen um das ganze möglichst performant hinzubekommen. Genau das gleiche hast du wenn du 2 Container nutzt.

Ich hab das ganze auf einen recht kleinen Terrain gemacht 127*127 Felder, dabei konnte ich einiges an Performance, indem ich Container nutze die auf die Inhaltsprüfung optimiert waren. Du prüfst pro Feld 8 (im worst case) Nachbarfelder ob sie in einer der 2 Listen vorhanden sind, macht also 16 contains Operationen. Daher ist es wichtig das gerade diese Prüfung sehr schnell läuft, das ermitteln des geringsten G Wertes machst du nur 1 mal pro Feld, das war bei mir mit einem einfachen Bubblesort gerade noch schnell genug, auch wenn es sicherlich auch hier Optimierungsaufwand gab.

Was ich damit ausdrücken will. Versuch einfach mal eine nur auf eine Zugriffsart ausgelegte Liste zu verwenden. Bei mir war es eine Map bzw. Hashmap (man kann für jedes Feld einen eindeutigen Hash berechnen). Ich denke das du so schon genug performance erhält um die 2 Abfrage einfach mit einem Iterator implementieren kannst.
Dazu muss man immer bedenken das eine Struktur die Positions- und Sortierungsinformationen speichert beim Einfügen und Löschen recht lange braucht, da die Bäume neu ausbalanciert werden müssen. Das alles kostet wieder extra Zeit und steigt mit komplexeren Strukturen an.

Ich habe nun eine Lösung gefunden mit 2 Containern. Meine Hilfs-Container-Klasse kapselt eine std::priority_queue und bietet als Schnittstelle die nötigen Methoden an. Zusätzlich kapselt die Klasse eine std::map, die als Mapping von Position auf Node-Pointer fungiert. Die std::priority_queue sortiert korrekt und über die std::map kann ich prüfen ob eine Node mit einer bestimmten Position existiert.