A-Star Pathfinding optimieren



  • Mahlzeit 🙂

    Ist hier jemand der mit dem A* Algorithmus vertraut ist und mir Tipps geben kann ? Meine Implementierung von A* ist mir viel zu langsam 😞
    Ich habe mal testweise auf einer 100 x 100 Tile Map zwei Schikanen eingebaut.
    Zwei horizontale Reihen mit Hindernissen. Am Ende ist gegenĂŒber jeweils 5 Tiles platz zum durchkommen (Man betrachte die "Skizze" zum besseren VerstĂ€ndnis)

    S.....................
    ......................
    XXXXXXXXXXXXXXXXX.....
    ......................
    ......................
    .....XXXXXXXXXXXXXXXXX
    ......................
    ......................
    .....................Z
    

    S = Start
    Z = Ziel
    . = Begehbares Feld
    X = Hindernis

    FĂŒr dieses Terrain (In der GrĂ¶ĂŸe 100 x 100) braucht mein Algo ~60 msec um den Pfad zu ermitteln. Bei einer 500 x 500 Map dauert es ewig.
    Einige Optimierungen habe ich bereits eingebaut: Die Open-Node Liste ist nach "Bewegungskosten" sortiert und alle Nodes können durch die Verwendung von Maps (MFC) schnell aus den Listen ermittelt und zugeordnet werden. Dennoch geht der Algo bei grossen Maps in die Knie. Was kann man dagegen tun ?
    Was gibt es fĂŒr Alternativen zu A* ?


  • Mod

    1
    schneller ist es wenn man vorher nodes verteilt (viel gröber als die eigentliche auflösung des spielfeldes) und dann diese z.b. beim spielstart initialisiert.

    eine node ist dabei ein knoten der in nord,sued,ost,west sich merkt ob er zur dortigen nachbarnode eine verbindung hat oder nicht (es muss keine direckte verbindung sein, aber z.b. eine deren weg maximal 50% ĂŒberm direckten weg ist... das ist ne frage der balance)

    wenn man dann einen weg finden möchte, sucht man sich den weg zur nÀchersten möglichen node und von der aus dann (relativ schnell) einen zu der Node die am nachesten zum ziel liegt. dann muss sich jede einheit nurnoch von node zur node hangeln und das ist recht performant zu machen.

    2
    bei manchen playstation2 spielen verwendet man eine art portal-technik. dabei unterteilt man vor dem spielbeginn das spielfeld in gebiete und merkt sich die verbindungen zwischen den gebieten (die portale). um dann den weg zu finden muss man (wie bei dem node system) nur den weg zum nachesten portal suchen und hangeld sich dann zum nÀchsten... bis man am zielgebiet ankommt.
    das ist recht fix und speichersparend. aber vielleicht nicht sooo einfach zu implementieren.

    rapso->greets();



  • rapso AnsĂ€tze sind schon ok. Aber eigentlich reicht auch schon der Sichtbarkeitsgraph der gesamten Welt aus, in den dann nur Start und Ziel einfĂŒgt werden. Bewiesener Massen sind alle inneren Kanten des kĂŒrzesten Weges Kanten des Sichtbarkeitsgraphen. (Ich kann mich irren, aber das hatten wir schonmal?!)

    Was ist bei dir jetzt die "Open Node"-List? Bei A* brauchst du doch, wenn du eine konstante SchÀtzfunktion, nur eine Menge (genau wie bei Dijkstra) und die speichert man normal in einen Heap, z.b. Fibonnacci Heap.

    Bye, TGGC (Der Held bei Dir!)



  • Also der Algorithmus sieht in etwa so aus:

    Pseudo

    Startfeld in Open-List packen
    Wiederholen bis Pfad gefunden:
        Suche das Feld aus der Open-List mit der besten Bewertung (Bewegungspunkte)
        Dieses ist das zu betrachtende, aktuelle Feld
        Pack dieses Feld in die Closed-Liste
        Betrachte alle anliegenden Felder
        FĂŒr jedes Feld wird folgendes geprĂŒft:
            Auf der Closed-Liste ?
                Dann nÀchstes Feld
            Auf der Open-Liste ?
                Ist die Entfernung vom aktuellen Feld zu diesem Feld gĂŒnstiger
                als seine aktuelle ? Dann mach das aktuelle Feld zu seinem Parent
                und berechne die Bewegungspunkte neu
            Nicht auf der Open-Liste ?
                Setz das Feld auf die Open-Liste, mach das aktuelle Feld zu seinem
                Parent und berechne die Bewegungspunkte
                Ist das Feld das Zielfeld, dann beende die suche
    Schleifen-Ende
    

    Die Suche endet, wenn das Ziel-Feld auf der Open-Liste landet, oder die Open-Liste irgendwann leer ist (Pfad nicht berechenbar)



  • Cpp_Junky schrieb:

    Mahlzeit 🙂

    S.....................
    ......................
    XXXXXXXXXXXXXXXXX.....
    ......................
    ......................
    .....XXXXXXXXXXXXXXXXX
    ......................
    ......................
    .....................Z
    

    S = Start
    Z = Ziel
    . = Begehbares Feld
    X = Hindernis

    lass doch beim laden der map noch einen algo durchlaufen, der aus der map sowas macht:
    S = Start
    Z = Ziel
    . = Begehbares Feld
    X = Hindernis
    N = Node

    S.....................
    .................N....
    XXXXXXXXXXXXXXXXX.....
    .................N....
    ....N.................
    .....XXXXXXXXXXXXXXXXX
    ....N.................
    ......................
    .....................Z
    

    der A* algorithmus sucht dann nichtmehr alle felder des weges, sondern nurnoch alle Ns, die ihn um die hindernisse rumfĂŒhren



  • Das mit der "open" und "closed" Listen doch aber sinnlos? Wenn es einen Parent hat, und nicht in der zu untersuchenden Menge (hier "open" genannt), dann ist es "closed", warum extra verwalten?

    Bye, TGGC (Der Held bei Dir!)



  • Ich brauche die Listen, damit ich nicht bei jedem mal wenn ich das Pathfinding ausfĂŒhre die Nodes neu initialisieren muss. Bei einer kleinen 100 x 100 Map sind das immerhin schon 10.000 Objekte. Es ist wesentlich schneller einmal die Open/Closed Listen zu bereinigen. Wobei die Closed Liste dennoch etwas ĂŒberflĂŒssig ist. Man kann genauso gut fragen ob ein Node nicht in der Open-Liste steht. Aber das ist Performance-Technisch irrelevant und kostet höchstens ein Paar Bytes vom Speicher. Ich brauchs aber schneller :p



  • Cpp_Junky schrieb:

    Ich brauche die Listen, damit ich nicht bei jedem mal wenn ich das Pathfinding ausfĂŒhre die Nodes neu initialisieren muss.

    Na wenn du meinst.

    Bye, TGGC (Der Held bei Dir!)


Log in to reply