spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Wenn man nen Weg abgeht, dann gibt es Orte von denen man kommt ("Vorgaenger") und Punkte zu denen man spaeter geht ("Nachgaenger").

Das ist doch dann trotzdem ein Graph.

Zitat von »MaZy«

Also ich habe diese Variable genommen: OpenList ClosedList OpenListPos ClosedListPos OpenListWPNo ClosedListWPNo G H. Das sind alle arrays. Ich benutze keine 2D Arrays, da ich mit minIndex einfach den kleinsten F wert raussuchen kann. Bei 2D geht das schlecht .

Ich habe mir den Algorithmus auch von dieser Seite beigebracht. Allerdings habe ich kein Array verwendet sondern eine Liste vielleicht solltest du mal nach Doubly linked list googeln dann wird vielleicht auch klarer was mit "vorgänger" und "nachgänger" gemeint ist.

Vorgaenger und Nachgaenger haben nichts mit der Anordnung in einer Liste oder Array zu tun, sondern nur mit der (potentiellen) Reihenfolge innerhalb des gesuchten Weges.

Hast du recht. Trotzdem finde ich das, dass ganze Konzept besser zu verstehen ist wenn man das mit listen umsetzt. Um ehrlich zu sein kann ich mir das gar net so recht vorstellen mit nem Array. Aufjedenfall stell ich es mir erheblich schwerer vor.
Mein Größtes Problem war damals die "Arbeitsweise" zu verstehen. Ich Denke Mal MaZy geht es da ähnlich (Vermutung). Und man kann einfach schlecht ein Konzept umsetzten wenn man es nicht verstanden hat.

Wie schon gesagt, hat Vorgaenger/Nachfolger bei A* nichts mit dem Vorgaenger/Nachfolger in einer Liste zu tun. insertBefore oder insertAfter ist daher nutzlos.

Ich kann gerade nicht dein Problem richtig nachvollziehen.

Aber vielleicht kann ich ja mit dem folgenden etwas Licht ins Duckel bringen...

Du hast bei einer Liste immer ein oder mehrere Objekte im Speicher liegen. Diese sind unter ein ander in bestimmter weise Verknüft, ch denke mal sehr häufig ist eine Doppelt verlinkte Liste. Es gibt immer eine "Schnittstelle" (Ich weis nicht ob man das auch so nennt ich habe mir den kram selber beigebracht.) zu diesen Speicher bereichen. Von dieser Schnittstelle kannst du dann zum nächsten Objekt (auch Knoten oder Node genannt) springen.
Bei einer Doppelt verlinkten Liste Kennt das Objekt seinen Vorderman und seinen Nachfolger. Das hat aber noch nichts mit A* zu tun sondern nur das die Objekte "wissen" wo im Speicher jeweils 2 andere Objekte zu finden sind.

= Node 1 <===> Node 2 <===> Node 3 =

So kann man sich das vielleicht etwas besser vorstellen. Node 1 weiß nicht das es Note 3 gibt weil die nicht "verlinkt" sind. Aber Node 2 kennt sein Vorderman (Node 1) und sein hinterman (Node 3).
Das Tolle ist ich kann jetzt auch die Reihenfolge ändern also z.B. Node 3 sagen es gibt Node 1, Node 2 sage ich du hast keinvorgänger und dein nachfolger ist Node 2, Node 1 sag ich du hast ein neuen nachfolger Node 3 und bekommst nen Vorderman Node 2.

= Node 2 <===> Node 1 <===> Node 3 =

dann sieht es so aus. So jetzt kann ich aber auch etwas in diese Liste einfügen (Die man sich übrigens vorstellen kann wie eine Kette).
Wenn ich jetzt mit meine Schnittstelle Node 1 ist (Liste so wie als letztes Dargestellt) und ich will ein neues Objekt einfügen kann ich den in die Liste vor die Schnittstelle (also Node 1) oder dahinter einfügen.

Davor:

= Node 2 <===>Node 4<===> Node 1 <===> Node 3 =

Dahinter:

= Node 2 <===>Node 1<===> Node 4 <===> Node 3 =

Soviel zu InsertAfter und InsertBefore. Es gibt auch noch andere möglichkeiten z.B. an den Anfang oder an das Ende der Liste einfügen.

Üblicher weiße haben die Nodes auch noch einen Inhalt z.B. stehen da die Coordinaten drin und/oder alles was so in A* reingehört F H und G ect. und jetzt kann man routinen schreiben die das einfügen und einsortieren nach einem bestimmten Parameter des inhalts z.B. H.

Wie das jetzt alles im einzelnen Aufgebaut ist läst sich auch im Netz rausfinden.

Ich hoffe damit konnte ich deine Verständnisprobleme lösen wenn nicht beschreib dein problem noch mal genauer.