4. Probleme mit Pathfinding.

Probleme mit Pathfinding.

  • K

    Hi. Ein Bekannter hat mir gesagt ich soll hier deswegen mal vorbeischauen.
    Und zwar habe ich (wie der Titel sicher schon vermuten lässt) ein Problem mit Pathfinding. Es geht dabei nicht wie sonst darum den kürzesten Weg zwischen Startpunkt und Ziel zu errechnen, sondern überhaupt festzustellen welche Felder von der Zugreichweite her überhaupt begangen/fahren werden können.

    Bisher bin ich in einer Schleife durchgegangen und habe mit der Formel Wurzel((EinheitenX - FeldX)² + (EinheitenY - FeldY)²) jeweils die Distanz zwischen Einheit und den momentanen Feld errechnet, und je nachdem ob das Ergebniss kleiner oder gleich der Zugreichweite der Einheit ist Grafiken geändert.
    Das geht ja noch aber jetzt habe ich auch Objekte eingebaut die "Deckung" geben können, also nicht überfahren werden können. (bzw. nur von bestimmten Einheiten.)
    Hier ein einfaches in HTML nachgebautes Beispiel:

    http://666kb.com/i/ayheqcf65g04ben4n.png

    Es geht bei dem Bild um die Einheit die von einsen umgeben ist.
    Die Zahlen geben jeweils den Abstand zwischen dem momentanen Feld und der Einheit an. Sie sollte eigendlich nur 7 Felder weit fahren können. Also links sollte zwischen den Bergen Schluss sein. Durch meine momentane Formel werden die Berge aber nicht beachtet, und alle über 7 würden über die Berge (ohne Geschwindigkeitseinbußen) auch erreichbar sein.

    Hab mir Pathfindingtutorials angeschaut, aber habe keine Idee wie man es lösen könnte. Vor allem, da man ja nicht sagen kann wieviele Felder tatsächlich begehbar sind. Die einzige Möglichkeit die mir eingefallen ist alle Möglichkeiten die kommen können per Brute Force zu generieren und dann einfach durchsuchen zu lassen. Das wäre vielleicht hinterher eine Möglichkeit zur Leistungssteigerung, aber fürm Anfang imho quatsch.

    Hat da eventuell jemand eine Idee wie ich das machen könnte?
    Mir fällt absolut nichts brauchbares ein.

    MfG.

    0
  • U

    Hab leider auch keine andere praktikable Idee als so ne Art brute Force.
    Erstmal schaun wohin mit einem Feld Reichweite kommt, von allen Zielen wo man dort hinkommt schaun wo man mit einem hinkommt, von dort aus schaun...
    Dabei prüft man halt noch ob man auf einem möglichen Zielfeld schonmal war, um das ganze nicht allzusehr explodieren zu lassen.
    In ner art Pseudocode:

    struct Koordinaten {
int x;
int y;
}
vector<Koordinaten> alleMöglichenFelder;
vector<Koordinaten> aktuelleFelder;
vector<Koordinaten> neueMöglicheFelder;
for (int i = 0; i < maximaleReichweite;++i)
{
for (int j = 0; j < größe(aktuelleFelder); ++i)
{
if (feld über aktuelleFelder[j] kann begangen werden) 
{
if (aktuelleFelder[j] ist nicht in alleMöglichenFelder)
{
neueMöglicheFelder.push_back(feldkoordinaten);
alleMöglichenFelder.push_back(feldkoordinaten);
}
}
if (feld unter...);
//etc etc
}
schiebe Daten von "neueMöglicheFelder" in "aktuelleFelder"
}

    Ob du das mit vector machst oder ner map oder was auch immer is dir dann überlassen, aber so als anregung wär das meine idee.
    *umschau*
    jemand ne bessere? *hoff*

    0
  • J

    Im Prinzip brauchst Du genau eine Breitensuche bis zu einer gewissen maximalen Tiefe. http://de.wikipedia.org/wiki/Breitensuche

    Das dürfte nicht viel langsamer sein, als jedes Feld mit der Distanzformel zu testen. 🙂

    0
  • C

    Kai008 schrieb:

    ...

    http://666kb.com/i/ayheqcf65g04ben4n.png
    ...

    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

    0
  • K

    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?

    0
  • U

    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 in

    vector<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 :>

    0
  • J

    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.

    0
  • K

    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.

    0
  • K

    Oh, stimmt. War ein Denkfehler. Danke, ich werde die beiden Methoden mal versuchen.

    0
  • J

    Krux schrieb:

    http://de.wikipedia.org/wiki/Dijkstra-Algorithmus

    Disjkstra mit überall identischen Gewichten == Breitensuche

    0
  • C

    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.

    0
  • J

    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. 🙂

    0
  • C

    Diese Breitensuche scheint ne klasse Erfindung zu sein 😃

    0
  • S

    In Tat und Wahrheit, das ist sie. 🙂 👍

    0
Anmelden zum Antworten