nicht angemeldet
Verbesserung des *-Algorithmus
0 0 0 0 Allgemeine Fage zu A*
Verbesserung des *-Algorithmus
hallo zusammen,
ich abe es nun dank eurer hilfe geschafft in meim game den
A*-Algorithmus einzbauen ...
nun ergibt sich aber ein weitees 'problem':
meine spielwelt besteht aus 1Mio feldern und hat viele flüsse und meerarme,
das führt dazu da das script mit dealgorithmus für grosse wege lange suchen muss ...
hier maein sat-bild von der spielwelt.
[img]http://www.mounchain.com/satpic.jpg[/img]
ich will vn A nach B aber das cript probiert natürlich erst ale felder im dem transparent
violetten breich aus .... weil diese auf grund der heuistik bevorzugr werden..
und da werden ca. 200.000 felder üerprüft ... was natürlich nen bissel lang dauert ....
kann ich das irgendwie verbessern ??
danke schonmal
kai
-
Hello,
violetten breich aus .... weil diese auf grund der heuistik bevorzugr werden..
könntest du vielleicht etwas an der Heuristik drehen, frei nach dem Motto "Wasser kostet unendlich viel" oder überproportional viel oder sowas, irgendetwas was den Weg über das Wasserhindernis auf jeden Fall schlecht werden lässt? Wobei ich nicht sage, dass es dein Problem löst, im Gegenteil, es mag sogar andere Karten geben in denen das Problem dann anders ist, lass mich was kurz mit "W" für Wasser und "L" für Land aufmalen
LLWLLL
ALLWLWB
LLWLWL
LLLLWL
LLWWWL
LLLLLL
Wenn du jetzt den Zickzack-Weg durch das Wasser per Heuristik zu teuer machst, läuft der Algorithmus am Ende noch unten herum...MfG
Rouven--
-------------------
Death is nature's way of telling you to slow down.-
hallo,
ansch natürlich ein guter ansatzt ABER manachmal müsste ich eigentlich schon 100 felder bevor ich aufs wasser treffe um 90 Grad den kurs ändern ... daher bringt mir das ja nix .. wenn ich am wasser bin
ist es zu spät...cu
kai-
Hello,
ansch natürlich ein guter ansatzt ABER manachmal müsste ich eigentlich schon 100 felder bevor ich aufs wasser treffe um 90 Grad den kurs ändern ... daher bringt mir das ja nix .. wenn ich am wasser bin
ist es zu spät...na ja, im Prinzip ist das Problem was du hast ja genau einer der Knackpunkte. Der Algorithmus arbeitet eben NICHT auf vollständigen Informationen sondern auf einer lokalen heuristischen Entscheidung, die alles andere als optimal sein kann. Sein ganzes Können liegt in einer günstigen Heuristik.
MfG
Rouven--
-------------------
Eine Bilanz ist wie der Bikini einer Frau. Sie zeigt fast alles, aber verdeckt das Wesentliche -- Günter Stotz, Regierungsdirektor des baden-württembergischen Wirtschaftsministeriums
-
-
-
Hallo kai,
Das Problem scheint mir zu sein, dass Dein Graph, auf dem Du Suchst, unnötig groß ist.
Dein Startpunkt A ist z.B. eingeschlossen von Wasser und es gibt nur an einer Stelle, um weiter zu kommen. Die Frage ist nur, wie findet man diese.
Meine Überlegung ist nun folgende:
Es gibt erstmal zwei Möglichkeiten:
1. Das Ziel ist auf geradem Weg erreichbar, kann also vom Startpunkt aus "gesehen" werden. In dem Fall ist diese Sichtlinie bereits die Lösung.
2. Es liegt ein Hindernis dazwischen. In diesem Fall kannst Du rechts oder links vorbei, es ist also absolut sinnlos, alle Wege dazwischen überhaupt in Betracht zu ziehen, was Dein Algorithmus bislang aber tut.Ich würde nun versuchen, nicht auf dem Graph der Kartenfelder zu rechnen, sondern immer von einem Knoten ausgehend zu prüfen, ob das Ziel schon direkt erreichbar ist und wenn nicht, als nächste Knoten nur die Felder betrachten, die an sichtbaren Ecken von Hindernissen liegen.
Ersteres ist einfach. Man prüft einfach den direkten Weg zum Ziel.
Wenn man nun auf ein Hindernis stößt, kann man diesem entlang laufen bis zu einem rechten und linken Eckpunkt. (Eckpunkte erkennt man daran, dass man nicht weiter nach rechts (bzw. links) gehen kann)
Wenn man nun so einen Eckpunkt gefunden hat, muss man wieder den direkten Weg vom aktuellen Startpunkt aus überprüfen. Ist diesr Weg frei, hat man einen Eckpunkt gefunden und man kann an diesem in Sichtrichtung weiter das nächste Hindernis suchen. Liegt ein anderes Hindernis davor, ist der Eckpunkt nicht sichtbar und die Eckpunkte des Hindernisses davor müssen gesucht werden.Das zu programmieren dürfte etwas aufwendig sein. Außerdem muss man sich noch überlegen, wie groß Ecken sein sollen, damit man sie als solche erkennt. Man könnte hier mehrere Felder gemeinsam betrachten, um nicht schon kleine, unbedeutende Wellen der Ränder von Hindernissen als Eckpunkte zu erkennen.
Außerdem sollte man wohl nicht alle sichtbaren Ecken für einen Ausgangspunkt sofort bestimmen, sondern immer nur so weit nach Ecken suchen, dass man die Ecke findet, die anhand der Heuristik am besten ist.
Der Algorithmus wird dann nach wie vor zuerst in die lila Bereiche hineinlaufen, aber er wird sehr viel weniger Knoten betrachten müssen, um festzustellen, dass es keinen Weg gibt.Grüße
Daniel
-
Hallo,
les dir einmal http://www.policyalmanac.org/games/aStarTutorial_de.html durch. Unter Punkt 6 gibt es ein paar Tipps, die die Geschwindigkeit von A* deutlich erhöhen können. Vielleicht ist ja ein passender für dich dabei.
Gruss,
OhneName -
Hej,
ich hätte da mal eine allgemeine Frage zu A*: Ist es nicht so, dass A* nur bei gewichteten Graphen sinnvoll einsetzbar ist? Bei ungewichteten sollten doch eigentlich Tiefen- und Breitensuche ein exaktes Ergebnis bei geringerer algorithmischer Komplexität liefern. A* läuft mit [latex]O(\vert V \vert log \vert V \vert + \vert E \vert)[/latex], Tiefen- und Breitensuche hingegen mit [latex]O(\vert V \vert + \vert E \vert)[/latex].
Und soweit ich das sehe, handelt es sich doch in dem hier diskutierten Beispiel um einen ungewichteten Graphen.
Beste Grüße
Biesterfeld--
Art.1: Et es wie et es
Art.2: Et kütt wie et kütt
Art.3: Et hätt noch immer jot jejange
Das Kölsche Grundgesetz-
Hallo Biesterfeld,
Und soweit ich das sehe, handelt es sich doch in dem hier diskutierten Beispiel um einen ungewichteten Graphen.
Nun, wenn man wirklich auf den Feldern als Knoten rechnet, hast Du damit wohl recht. Wenn man den Graphen so vereinfacht, wie von mir vorgeschlagen, hat man aber nicht mehr gleiche Abstände zwischen den Knoten. Ich würde erwarten, dass das deutliche mehr bringt.
Das nächste Problem ist, dass man bei Tiefen oder Breitensuche erstmal keine Heuristik verwenden kann, d.h. man durchläuft den Graphen irgendwie, wärend man mit dem A*-Algorithmus immer an der "vielversprechendsten" Stelle weitersucht. Was man bei Tiefensuche/Breitensuche einspart, ist ja der Aufwand für die Prioritätswarteschlange. Um das Problem in der Praxis schnell zu lösen ist es aber wohl notwendig, eine solche zu verwenden. Sonst durchläuft man im Mittel den halben Graphen.
Zu beachten ist hier, dass das worst-case Verhalten auf allgemeinen Graphen relativ uninteressant sind. Es handelt sich ja um Landkarten, die eine sehr viel einfachere Struktur haben dürften.
Grüße
Daniel
-