A* Pathfinding

[Airblader]

Hi
Ja, ich habe bereits gesucht und bin hier durch die DP-Suche auch fündig geworden

Ich habe eig. nur 2 Fragen:

1)
Hab ich das jetzt so richtig verstanden (habs mir mal selber auf Deutsch aufgeschrieben)?

Zitat:

http://nopaste.php-q.net/173975

--- Der Übersicht halber den Text ins No-Paste geschoben ---

Und wenn ja,

2) Ist es hier auch am besten wirklich TList zu verwenden? Evtl. jmd mit Erfahrungen?
Das ganze soll nämlich logischerweise auch schnell berechnet werden und die Position d. Zielpunktes kann sich immer verändern

air
Edit:
Also das ist die Zusammenfassung die es dort auch gibt.
Das mit der Open/Closed List ist mir - denke ich - klar

[Corelgott]

also wenn ich das richtig verstehe sollte es passen...

aber du kannst noch überlegen, ob du wirklich alle 8 Felder prüfen musst...

von einem kommst du ja her....
Mache sind ja nicht begehbar... (somst wäre die wegfindung sinnlos...)

aber sonst...
ich persönlich würde die daten offscreen verwalten... mit ner TObjectList und dann postitions-objekte reinlegen...

aber das ist geschmackssache ^^

cya
Corelgott

[Airblader]

Die wichtigste Frage die sich mir stellt ist vor allem, was die beste Performance hat
Wie ich z.b. noch den H-Wert berechnen soll ist eine Frage, die sich zwar lösen lässt, aber bei der man drauf achten muss, wie man es macht.
Meine Idee wäre da z.B.:

Ich habe (X1/Y1) - die Koord. des Startpunktes.
Außerdem habe ich (X2/Y2), die Koord. des Zielpunktes.

Das Ergebnis wäre also eine Strecke von (X1-X2 / Y1-Y2) = (X3/Y3), wobei natürlich ein positives Ergebnis
rauskommen muss (sprich abs()).

Der H-Wert wäre dann also X3+Y3, oder?

--------------------------------

Edit
Bei TObjectList hätte ich noch ein Problem:
Kann ich anstatt TObject bei den Items auch eine eigene Klasse verwenden? (Ich muss ja irgendwo den F-,G- und H-Wert zwischenspeichern ).
Ich kann zwar eine Klasse erzeugen von TObject aber TObjectList will ja ein TObject - vllt. bin ich aber grad auch zu durcheinander und vergess was *fg*

Edit2:
Ok..hat sich glaube ich erledigt die Frage

Edit3:
Ich muss doch umsteigen, da ich ja Sublisten brauche, die wieder Sublisten haben, ...

air

[Airblader]

*push*

Mir stellt sich jetzt eine ganz elementare Frage.
Ich hab begonnen, bin mir aber nichtmehr ganz so sicher, ob das so die beste Idee ist.

Wie würdet ihr an die Sache rangehen?
Ich hab versucht das in eine Klasse zu kapseln. Dann hab ich mir 2 Laufzeit-TreeViews angelegt für die Listen und eben einen record als Pointer auf einen record für die Daten (in TTreeNode.Data wird das abgelegt).

Ich frage mich, ob eine Klasse aber so sinnvoll ist, da es eig. keinen großen Vorteil bietet in dem Fall, oder?


Also nochmal konkret: Wie würdet ihr das in etwa lösen (auch von wegen Performance).

air

[Corelgott]

hmm

tja die performance...

also ich würde das "spiel"-feld einmal komplett vorberechnen...
Soll heißen ein array anlegen, mit den daten die du schon hast:
z.b. x & y kooerdinate, ob begehbar oder nicht usw.

in das array schickst du dann die rotine rein.

Am besten kann man dann wohl mit nem pointer auf die einzelnden felder zugreifen. (schönn flink)
...
Ich persönlich würde es weitestgehend vermeiden zur berechnung visuelle komponenten zu benuzten... d.h. ein treeView ist zwar ganz hübsch und vielleicht auch bunt. Aber jedes ändern in dem teil kostet verdammt viel zeit. (Immer wieder neu zeichnen usw.)

Also am besten alles offscreen machen und dann das fertige anzeigen...
Da das ganze ja an sich gesehen nicht viel tun muss sollte das recht flink sein.
Was man auch gut einbauen kann, ist beim vergleich der kosten der felder quicksort zu benutzen.

Erst die felder raus schmeißen, die nicht mehr in frage kommen...
Blockiert oder ned... Kommt man von dort... bzw war man schon mal da...

dann dieses kleine pointer array mit den potenziellen kandidaten, sofern es einen gibt, per quicksort durchrattern...
Das oberste abschöpfen, weil der ja dann der mit den niedrigsten kosten wäre...
Den start-pointer von oben wieder verbiegen (auf das neue "ausgangsfeld") und das ganze dann wieder von neuem...

sollte also an sich nicht soo zeit aufwendig sein...
habe das zwar noch nie gebaut...
aber ist glaube ich recht performant zu lösen...

Ich hoffe meine paar stichworte helfen dir ein bissel weiter...
vielleicht fehlt hier und da mal ein verb... bin gerade zu faul darüber nach zu denken... ^^

cya
Corelgott

[Airblader]

Das Spielfeldarray hab ich vorliegen
Ich hab TreeView auch nicht visuell benützt sondern zur Laufzeit erzeugt - ich weiß, dass es nicht optimal ist, darum frage ich ja *fg*
Aber was soll ich sonst nehmen (wo ich auch Sublisten hab)?

Sooo aufwenidg dürfte es eh nicht werden, da die Routine erst eingesetzt wird, wenn sich der Player in einem gedachten Kreis des NPCs befindet (dafür dann aber recht oft...).


air

[Airblader]

*leider nochmal pushen tut*

[Khabarakh]

Ich würde kein TTreeView benutzen, wenn er nicht angezeigt werden soll. Bau die Baumstruktur lieber gleich in deine Klasse ein, dann hast du auch kein Pointer-Gefummel .

Delphi-Quellcode:

type
  TNode = class
  private
    FChildNodes: TObjectList; // oder ein Array, hab mich jetzt nicht mit dem Algorithmus auseinandergesetzt
  [...]

[Airblader]

Mhm und dann als Objekte für die ObjectList wiederum TNode?
Klingt schlau *fg*


Werd ich mir mal genauer anschauen, leider grad keine Zeit, aber Danke schonmal

[alzaimar]

Ick stell mich jetz mal ganz dumm und frage: Du hast einen (gerichteten) Graphen und willst einen Weg von a nach b finden? Oder den Kürzesten? Und Du brauchst eine geeignete Datenstruktur? Sehe ich das richtig?
If Antwort = Nein Then ClickWeg Ansonsten hilft hier die 'mathematische' Definition eines Graphen. Das ist ein Tupel, bestehend aus Knoten (Nodes) und Kanten (Edges). Knoten könnten man einfach als Zahlen von 0...N-1 definieren. Die Kanten als Matrix E [0..N-1,0..N-1]. E[i,j] beschreibt dann die Entfernung, um von i nach j zu gelangen, also die 'Länge' der Kante von i nach j. Ein Wert von +Maxint würde z.B. bedeuten, das man gar nicht direkt von i nach j gelangen kann. Achtung: Wir definieren hier wirklich nur die Kanten des Graphen, also nicht Wege über diverse Knoten.

Damit kann man dann sehr schnell arbeiten. Ein Weg von i nach j würde z.B. als ein Array of Integer definiert. Ein Weg von Knoten #1 zum Knoten #5 würde z.B. so aussehen: [1,2,8,5]. Ich komme also von 1 über 2 und 8 nach 5.

Ich kenne den A*-Algorithmus leider nicht, und ich schäme mich dafür, weil es zur Allgemeinbildung gehört, sonst könnte ich Dir hier besser helfen. Ich weiss nur, das der A* der derzeit beste Algorithmus ist, um das Problem des 'shortest Path' zu lösen. Es gibt aber noch recht einfache Alternativen...