2D einheit um gegenstände herumlaufen

otze

besser als A*? nicht wirklich

TGGC

Sgt. Nukem schrieb:

Viele posten dann immer: A* !

Ohne zu wissen, was genau das ist...

Bye, TGGC Deine Unterstützung wird gebraucht!

Sgt. Nukem

TGGC schrieb:

Sgt. Nukem schrieb:

Viele posten dann immer: A* !

Ohne zu wissen, was genau das ist...

Darauf wollte ich hinaus...

Deutschland sucht den A-Star...

DocJunioR

Was mich immer irritiert ist folgendes :

Ich habe ein Raster mit 2 zu erreichenden Punkten und ein hindernis :

*********************
*                   *
*           B       *
*                   *
*     xxxx          *
*        x          *
*    A              *
*                   *
*********************

wenn ich nun von Punkt A in sämtliche nachbarn in denen nichts steht eine - hmm mindestens 3 rein schreibe. Dann in sämtliche leeren Nachbarn der Teile eine 2 und dann eine 1, anschließend geht das wieder bei 3 los :

*********************
*22222222132        *
*33333332132B       *
*3111113213332      *
*31222xxxx1132      *
*31233321x2132      *
*3123A32132132      *
*3123332132132      *
*********************

und zwar angefangen im Urzeigersinn bei 12 Uhr bis ich auf Punk B treffe.

anschließend suche ich genauso, nur zahlenmäßig anders herum die Nachbarn ab.
In diesem Falle wäre ich be einer 2 auf mein B gestoßen, ergo würde ich entgegen des Urzeigersinn nach einer 3 als Nachbarn suchen, dann nach einer 1 und dann eine2, etc:

*********************
*                   *
*           B       *
*           3       *
*     xxxx 1        *
*        x2         *
*    A3213          *
*                   *
*********************

Den Algorithmus nennt man Lee und er funktioniert sdeit je her.. für sämtliche Platinenlayoutprogramme... beidseitig
Hab irgendwo so nen Ding rumzuliegen. War eigenltich nur zu faul, ein Layoutprogramm dafür zu schreiben ^^

Hab ich doch vergessen, zu schreiben, was mich irritiert..

Wo ist der Unterschied zu A* ? Die beiden Algorithmen sind sich doch schonmal ziemlich ähnlich, oder nicht ?

Nein, sind sie nicht. Aber die allzu offensichtlichen Unterschiede kannst du wirklich auf eigene Faust herausfinden.

DocJunioR

Hmm.. Im Gegensatz zu Lee werden beim A* Knotenpunkte vergeben, über die Gegangen wird. Hierdurch ist die Wegekarte nicht so fein gerastert, wie die Spielkarte.. Weiterhin wird die Welle nicht rückwärts gezählt, sondern vorwärts.. Ansonsten ist A* nichts weiter als ne Adaption des Lee..

Das stimmt aber nicht wirklich.

Wie fein das Raster ist, hat mit A* nichts zu tun. A* ist ein abstrakter Algorithmus zum Lösen von beliebigen Problemen (beliebtes Beispiel: Schiebepuzzles), die bestimmte Eigenschaften aufweisen.
Außerdem hast du bei diesem Lee (den ich gar nicht kenne) wohl offensichtlich auch Knotenpunkte, die selben kannst du für den A* verwenden, außer du hast ein besseres System.

Der Hauptunterschied besteht immer noch darin, dass A* mit einer heuristischen Funktion arbeitet, die den verbleibenden Aufwand schätzt.

Cpp_Junky

Das schlimme ist, das im Netz hunderte Algorithmen kursieren die alle vorgeben A* zu sein. Ich habe für meine A* Implementierung folgendes Tutorial durchgeackert: http://www.gamedev.net/reference/articles/article2003.asp
Da ist alles ganz gut erklärt.
Momentan versuche ich noch "Binary Heaps" zu verwenden (Im Grunde genommen eine Art Quick-Sort-Insertion-Sort Mutation zum Sortieren und schnellen Auffinden der Open-List Elemente).

DocJunioR

hmm..
Das ist natürlich möglich.
Das Tutorial das ich gelesen habe, war mehr auf das Pathfinding ausgerichtet, als auf die entsprechende heuristische Suchmethode. Dementsprechend muss ich wohl meine Aussage (nach meinem Verständnis) insofern abändern, als dass A* nicht der Pathfinding-Algorithmus ist, sondern ein Aufsatz zur Optimierung eines Problems, im Pathfinding-Falle auf einen Lee ..

Werd mich aber mal genauer informieren - obwohl ich's bereuen werde, da mich solch eine Problematik im Moment nicht wirklich tangiert..

TGGC

A* kann beliebige Kantengewichte und Lee nicht.

@Cpp_Junky: Ich denk Fibonacci Heaps sind am effizientesten für Dijkstra und Konsorten?

Bye, TGGC (Dem beste BdT)

Cpp_Junky

@TGGC: Effizient ist es allemal. Wo ich früher durch die halbe Open-List suchen musste, muss ich jetzt vielleicht noch 3-4 vergleiche machen, dann weiss ich welches der nächstbeste Wegpunkt ist.

DocJunioR

TGGC schrieb:

A* kann beliebige Kantengewichte und Lee nicht.

Definiere "Kantengewichte"

Er meint verschiedene Kosten zum nächsten Wegknoten. Beispielsweise kann man, so wie ich, ein freies System haben, wo die Knoten nicht in einem Gitter liegen, sondern lediglich die Hindernisse umgeben. Dabei ist natürlich der Weg von einem Knoten zum nächsten nicht jedesmal der gleiche.
Oder man kann die Bewegung auf verschiedenen Terrainarten teurer machen.
Damit kann man z.B. einer Stealth-Einheit beibringen, sich möglichst im Schatten zu bewegen.
Oder natürlich, Sümpfe zu vermeiden, wenn in der Nähe auch ein Weg um den Sumpf herum führt.

</vermutung>

TGGC

In einem Graphen G = (V,E), wir die reele Zahl c(e), die der Kante e element E zugeordnet ist, Kantengewicht oder Bewertung genannt.

Hinweis: Optimizer hat recht.

Bye, TGGC (Der Held lebt!)