STL Container und Vorgehen bei A*
Verfasst: 10.08.2011, 20:31
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.
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.