Pathfinding einmal anders!
-
Hi,
alos ich habe eine 2D Karte mit beliebig vielen festgelegten Punkten! Ein Punkt ist der Startpunkt ein Punkt ist das Ziel. Es können immer Pnunkte die weniger al 150 Pixel auseinander liegen verbinden werden! Wie finde ich möglichst schnell den kürzesten Weg? (Ich möchte möglichst nicht bei jedem Wegpunkt alle anderen ausprobieren und testen ob die Punkte 150px auseinander liegen!)A* und sowas geht da ja nicht, weil man da ja eine Karte braucht, die in Quadrate aufgeteilt ist!
Mir fehlt im Moment irgendwie der Ansatz...
MfG
Alexander Sulfrian
PS: Punkte liegen erstmal unsortiert in einem Array vor! Könnte da aber theoretisch noch sortieren (logisch
)
-
A* und sowas geht da ja nicht, weil man da ja eine Karte braucht, die in Quadrate aufgeteilt ist!
Das stimmt nicht.
Der A* Algorithmus hat erstmal überhaupt nichts mit Pathfinding wie es in Spielen gebraucht wird zu tun. Es ist ein viel allgemeinerer Algorithmus für Such- und Optimierungsprobleme.Insofern kann A* sehr wohl auch für wesentlich speziellere Aufteilungen der Karte genutzt werden. Nur ist es dann eben nicht mehr mit Cut&Pase getan und man muss sich je nach Aufgabenstellung überlegen wie der Algorithmus anzupassen ist.
EDIT: Hier findest du ein Skript: http://www-ag-mayer.informatik.uni-kl.de/~agmlehre/ws03/eaa/
In Kapitel 11.3 wird A* vorgestellt. Vielleicht kannst du ihn ja damit entsprechend optimieren.
-
schau dir mal den lee-algorithmus an..
der malt ne Welle...
-
A* und sowas geht da ja nicht, weil man da ja eine Karte braucht, die in Quadrate aufgeteilt ist!
Komisch, dann habe ich für mein Spiel wohl gerade einen neuen Algorithmus erfunden.
-
OK! Ich werde mir wohl den A* Algo noch mal genauer anschauen....
-
Hi,
wenn ich das richtig verstanden habe muss ich aber trotzdem erstmal alle Elemente die noch zur Verfügung stehen durchprobieren (ob sie z.B. in den 150px Abstand passen) und dann für jeden infrage kommenden Wegpunkt weiter suchen! Das wollte ich eigentlich irgendwie umgehen!
Mir ist jetzt so was eingefallen wie, erst alle Punkte nach den xWerten sortieren und dann den Bereich zw. aktuellerPunkt.x - 150 und aktuellerPunkt.x + 150 nach den y Werten sortieren. Und dann wieder die y Werte ausschließen die über 150px weit weg liegen... (so dass ich dann ein Quadrat von 300x300px um den aktuellen Punkt habe!)Meine Frage wäre jetzt ob man das irgendwie intelligenter und schneller lösen könnte.....
MfG
Alexander Sulfrian
-
Sooooo teuer ist eine Rechteckkollision doch gar nicht... du kannst es auch einfach gerade so lassen? Wenn du wirklich _sehr_ viele Punkte hast, dann musst du halt die Karte in Regionen aufteilen und nur in Frage kommende testen.
// Ich denke, sehr viel schneller geht es nicht. template<class T> inline bool Point<T>::rectCollide(const Point& other, T radius) const { if( x > other.x + radius ) return false; if( y > other.y + radius ) return false; if( other.x > x + radius ) return false; if( other.y > y + radius ) return false; return true; }Mich würde eigentlich mehr interressieren, wie du feststellst, dass zwischen zwei Punkten keine Hindernisse liegen? Hast du dir darüber schon mal Gedanken gemacht? Das ist nämlich ein bisschen komplizierter, bevor du dich jetzt schon daran verausgabst...
-
Wenn ich das richtig verstehe, musst Du doch einfach nur im Voraus zu jedem Punkt die erreichbaren Punkte berechnen und geeignet abspeichern. Insgesamt hast Du dann einen Graphen (= Kontenpunkte + (gewichtete) Verbindungslinien), auf dem Du den Standard-A*-Algorithmus anwenden kannst..
-
Exakt so verstehe ich das auch, die Punkte bewegen sich ja nicht, oder? Falls du diese Liste (weil z.b. zu groß) nicht explizit speichern möchtest, so hat diese Suche _nichts_ mit Pathfinding zu tun. So'n kostenloser Tipp für deine weitere google Recherche.
Bye, TGGC \-/
