Probleme mit Pathfinding.
-
Kai008 schrieb:
...
omg, sag nicht du hast die Zahlen per Hand da reingemalt
btw: Ich hab maln kleines Tutorial über den A-Star Pathfinder geschrieben:
http://home.arcor.de/cppjunky/prog_tutorials.htm
-
Danke, aber bei Breitensuche bleibt noch das Problem das ich nicht feststellen kann wann alle möglichen Feldern gefunden werden, da ich ja nicht die Anzahl kenne.
Wenn ich Uchuujinsans Source richtig verstanden habe fügt er immer alle angrenzenden Felder in einen Vektor ein, und geht dann weiter, fügt wieder alle angrenzenden ein usw, bis er keine mehr hat? (Ja, ich verstehe fremde Source nur schwer und bin ein mießer Programmierer.)
Das würde theoretisch gehen, aber ist das nicht ein wenig langsam?
-
Ich denke prinzipiell hast du meinen code schon richtig verstanden (nicht vergessen das ich bereits gefundene Felder nicht mehr einfüge, also nicht wirklich alle), und vom tempo...:
Du gehst durch die innere Schleife, wenn keine kollision auftritt etwa 3 * (maximaleReichweite-1)² oft durch, genauer gesagt also genausooft, wieviele begehbare Felder du hast, mit ausnahme derer, die du als letztes gefunden hast.
Es sollte eigentlich gehen, das größte Problem dürfte wohl die Speicherverwaltung sein - falls es dir also zu langsam geht kannst du da ansetzen.
Aber ich hab mal einen ganz interessanten Text gelesen, der eine Regel aufgestellt hat: Optimiere erst, wenn du weißt wo es sich auch lohnt.
P.S.:
Mir fällt noch auf, du solltest invector<Koordinaten> aktuelleFelder;und evtl
vector<Koordinaten> alleMöglichenFelder;noch am anfang der doppelten for-schleife deine aktuelle koordinate (wo deine einheit steht) als startwert reinschreiben :>
-
Kai008 schrieb:
Danke, aber bei Breitensuche bleibt noch das Problem das ich nicht feststellen kann wann alle möglichen Feldern gefunden werden, da ich ja nicht die Anzahl kenne.
Du hast doch eine maximal-distanz, die du laufen darfst, sagen wir x. Immer wenn Du ein Feld findest, dann schaust du von wo aus du es gefunden hast, und auf welche tiefe du es gefunden hast. das neu entdeckte feld liegt dann eins tiefer. Wenn dir das schon zu tief ist hängst du es einfach nicht mehr in die queue rein. So mußt du einfach nur die queue leerlaufen lassen um alle felder zu finden.
@cpp_junky: das ist aber nicht das problem: A* findet kürzeste pfade zwischen zwei punkten, hier ist aber ein wegebaum von einem einzelnen festen startknoten gesucht. Im Prinzip mußt Du also Dijkstra machen. Außerdem sind hier die Kantengewichte alle gleich, jedes Feld braucht gleichlang zum durchqueren (zumindest in dem Beispiel), damit degeneriert Dijkstra zu einer Breitensuche.
-
http://de.wikipedia.org/wiki/Dijkstra-Algorithmus
Als knoten könntest du dann deine Tiles Betrachten.
als Nebenprodukt berechnet der Dijkstra auch noch die Pfade zu den anderen Knoten. Mit leichten Änderungen kannst du den Algorithmus auch so umbasteln, dann du alle mit einer bestimmten Pfadlänge erreichbaren Knoten finden kannst.
-
Oh, stimmt. War ein Denkfehler. Danke, ich werde die beiden Methoden mal versuchen.
-
Krux schrieb:
Disjkstra mit überall identischen Gewichten == Breitensuche
-
Könnte man für sowas nicht auch einfach einen Füll-Algorithmus verwenden? Um die Zugreichweite zu bestimmen, müsste man nur das als letzte gefüllte Feld in Reichweite suchen und einen Zug aufaddieren.
-
Cpp_Junky schrieb:
Könnte man für sowas nicht auch einfach einen Füll-Algorithmus verwenden? Um die Zugreichweite zu bestimmen, müsste man nur das als letzte gefüllte Feld in Reichweite suchen und einen Zug aufaddieren.
Herzlichen Glückwunsch, das ist schon wieder eine Breitensuche.
-
Diese Breitensuche scheint ne klasse Erfindung zu sein
-
In Tat und Wahrheit, das ist sie.
