A* Algorithmus Ergänzung |
21.03.2016, 13:59 | Auf diesen Beitrag antworten » | ||||||||||||||
Tommy1234 | A* Algorithmus Ergänzung Hallo nochmal, das Beispiel im Thema vorher hab ich nachvollziehen können und habe sogleich eine grafische Umsetzung erzielen können. Bisher kann ich auf einer großen Map mit Kollisionspunkten, den kürzesten Weg immer erfolgreich finden,ABER sobald ich die Map (ich meine nur ein rechteckiges Gitter mit kollisionspunken) mit 1x1 großen Knoten erstelle, dann läuft die Wegfindungberechnung sehr sehr langsam. Daraufhin hab ich mir überlegt die Map nur einmal im Konstruktor zu laden, aber der Weg muss ja immer zur Laufzeit neuberechnet werden, also das funktioniert irgendwie nicht. Wie kann ich bei 1x1 großen Knoten und Mapbreite von z.B. 200 und Höhe von 320, eine bessere Performance erzielen, oder ist das normal, das es so langsam geht? Meine andere Frage betrifft letztendlich doch die Umsetzung der Bewegung einer Spielfigur ( hier nur ein Rechteck) entlang des Pfades. Ich dachte das wäre einfach, aber da hab ich mich wohl sehr getäuscht, denn es gelingt mir einfach nicht die Spielfigur nach den Pfadkoordinaten zu Bewegen. Ich war 2 Nächte dran gesessen und hab mir den Kopf zerbrochen, komme aber nicht drauf wie das geht. Bitte um nochmalige Hilfe, wenns keine Umstände macht, Gruß Tommy |
||||||||||||||
|
|||||||||||||||
21.03.2016, 16:30 | Auf diesen Beitrag antworten » | ||||||||||||||
eulerscheZahl | Mal ein paar Vorschläge: In meinem Code ist openList schlecht implementiert (Suche mit linearer Laufzeit, sollte erst mal nur funktionieren und verständlich für dich sein). Halte die Liste die ganze Zeit über sortiert, dann sollte es merklich schneller werden. Wenn du den Weg nur einmal berechnen musst, könntest du es mit Floyd probieren. Damit kannst du die Berechnung in den Konstruktor verschieben. Aber Laufzeit O(n^3) könnte schon kritisch werden. Du könntest auch Wege zwischen bestimmten Punkten vorberechnen und dann nur noch schauen, wie du vom Startknoten zu einem dieser Punkte kommst und wie du dann wieder wegkommst (wie beim Navi, das einen auf die Autobahn lotsen will). Ein Rechteck zu bewegen, kann doch nicht so schwer sein. Wo hängt es genau? |
||||||||||||||
21.03.2016, 19:38 | Auf diesen Beitrag antworten » | ||||||||||||||
Tommy1234 | OpenList hab ich mittlerweile als ProrityQueue, also mit Warteschlnge implementiert. Geht jetzt auch schneller. Also ein Rechteck bewegen mach ich indem ich die x bzw y Koordinate erhöhe oder vermindere. x += speed; y += speed; Das ist ja klar. Ich hab nun vor, wenn das überhaupt möglich ist den x bzw. y Wert genau an den Pfad anzupassen so das sich das Rechteck schließlich entsprechend bewegt. In meiner ersten sehr primitiven A* Implementation ist mir das gelungen, indem ich einfach den x bzw y- Wert des Wegpunktes den Rechteckkoordinaten angepasst habe, also so x = Knotenx; y = Knoteny; So müsste es eigentlich sein und das hatte auch funktioniert, allerdings musste ich das für jeden x bzw y Wert einzeln zuweisen und das ist sehr viel Schreibarbeit, wenn der Weg länger wird. Bei dem von Dir angefertigten Code findet A* zwar den kürzesten Weg, aber wenn ich dann wie oben die Koordinaten zuweise springt das Rechteck nach kurzer Verzögerung sofort zum Zielpunkt. Ich möchte aber eine flüssige Bewegung erreichen. Die Koordinaten werden ja von A* stets richtig berechnet. Und genau das bereitet mir Kopfzerberechen. Grad beim schreiben ist mir die Idee gekommen die einzelnen x bzw y Werte des Pfades dynamisch in einem Array zu speichern und dann die Werte anzupassen per Schleife. Aber grad nur so ne Idee.... Ich hoffe du weisst jetzt was ich erreichen möchte?!!! |
||||||||||||||
21.03.2016, 19:41 | Auf diesen Beitrag antworten » | ||||||||||||||
eulerscheZahl | Hast du in der Bewegung ein Warten (sleep oder ähnliches)? Nicht dass du erst langsam den Weg ausrechnest und dann ganz schnell einen Punkt nach dem anderen zuweist. |
||||||||||||||
Anzeige | |||||||||||||||
|
|||||||||||||||
22.03.2016, 10:22 | Auf diesen Beitrag antworten » | ||||||||||||||
Tommy1234 | Ich habe nur eine Spielschleife mit einem Thread, den ich alle 48ms schlafen lege. Also: run(){ while(true){ update(); repaint(); Thread.sleep(48); } } Mehr nicht. Ist das falsch? Habe das nämlich immer so gemacht. |
||||||||||||||
25.03.2016, 17:50 | Auf diesen Beitrag antworten » | ||||||||||||||
Tommy1234 | Hallo nochmal, es hatte nicht mit irgendnem Warten oder sleep zu tun, sondern der Grund warum der Spieler immer sofort zum Ziel gesprungen ist liegt daran, dass der Pfad vom Ziel ausgehend zum Startpunkt berechnet wird. Das heisst, dass man die Werte in der Pfadliste einfach nur umzudrehen braucht, also anstatt von hinten nach vorne, von vorne nach hinten. Erst dann kann man eine Bewegung erzielen. Ich denke das bekomme ich hin also die Liste "umzudrehen". Danke trotzdem. PS: Habe mich nun intensiver mit Spielschleifen beschäftigt und nun endlich mal eine einigermaßen vernünftige Spielschleife hinbekommen mit UPS und FPS Werten bei 60. |
||||||||||||||
25.03.2016, 21:45 | Auf diesen Beitrag antworten » | ||||||||||||||
Tommy1234 | Ok, du hattest Recht, der Weg wird erst langsam ausgerechnet und anschließend wird ganz schnell der Weg ausgerechnet. Aber ich habe weder sleep noch irgendein warten implementiert. Leider hab ich keinen blassen Schimmer woran das liegen könnte. Ich nutze repaint(), aber daran allein kann das nicht liegen vermute ich. Bei Bedarf poste ich hier die Klasse, die das Fenster mit dem Label erzeugt und die Map auf dem Bildschirm ausgibt. Wäre toll nochmal was zu hören. Gruß Tommy |
||||||||||||||
26.03.2016, 08:06 | Auf diesen Beitrag antworten » | ||||||||||||||
eulerscheZahl | Ich wollte dich schon für die letzte Frage um den Code bitten - muss es dann irgendwie vergessen haben. Lade bitte mal so viel hoch, dass ich es kompilieren kann (werde es zeitlich aber wohl erst morgen schaffen). |
||||||||||||||
26.03.2016, 12:10 | Auf diesen Beitrag antworten » | ||||||||||||||
Tommy1234 | Hallo hier mal der gesamte Code. Die Mapdaten musst du in eine txt.Datei kopieren und in eclipse importieren in eine folder.
Ich hoffe das hilft. Bei mir ist der Code kompilierbar. Sorry für die Formatierung.(5min Arbeit ) |
||||||||||||||
26.03.2016, 18:54 | Auf diesen Beitrag antworten » | ||||||||||||||
eulerscheZahl | Na ein Glück, dass eclipse automatische Codeformatierung hat... Du hättest es aber auch einfach in eclipse archivieren und das .zip hochladen können. Naja, schaue ich mir morgen an. |
||||||||||||||
27.03.2016, 14:09 | Auf diesen Beitrag antworten » | ||||||||||||||
eulerscheZahl | Wenn es dir um die Verzögerung zwischen Klicken und Einzeichnen des Wegs geht: das Event wird wohl einfach nicht schneller ausgeführt. Mache eine Kontrollausgabe - du wirst sehen, es vergehen ein paar Millisekunden. Ansonsten: wenn du die Wegsuche in einem größeren Programm einbauen willst, berechne den Weg nur einmal und speichere den Pfad ab. Das geht schneller, als ihn für jedes Frame neu zu berechnen. |
||||||||||||||
27.03.2016, 16:06 | Auf diesen Beitrag antworten » | ||||||||||||||
Tommy1234 | Ok Danke, aber das löst mein Bewegungsproblem noch nicht. Hm. Ich denke ich mach es so, dass ich wie du sagst den Weg in einem int Array speichere und anschließend die Positionen pro frame einzeln zuweise. Allerdings vermute ich, dass es dann wieder zu schnell oder viel zu langsam geht. Also so z.B.: for(int x = 0;x<intx.length;x++){ intx[x] = playerx; } Noch eine Frage: Mit einem Timer den Spieler bewegen (wegen der einzelnen Positionen) ist Schwachsin oder? |
||||||||||||||
27.03.2016, 16:11 | Auf diesen Beitrag antworten » | ||||||||||||||
eulerscheZahl | Bei jedem "Tick", also Neuzeichnen würde ich auch den Spieler bewegen. Dazu solltest du die benötigte Zeit für das Zeichnen mit einfließen lassen, damit man sich auf jedem Rechner gleich schnell bewegen kann.
ist keine gute Idee: das ist abgekoppelt vom Zeichnen und warten. Außerdem würde ich Punkte speichern, keine x Koordinaten. |
||||||||||||||
28.03.2016, 09:51 | Auf diesen Beitrag antworten » | ||||||||||||||
Tommy1234 | Also, ich hab die Bewegung jetzt endlich. Allerdings hab ich noch ein Problem. Der Algorithmus den Du geschrieben hast berechnet zwar den Pfad sehr gut, doch zur Laufzeit ändert sich der Pfad, d.h. er wird pro Frame neu berechnet. Ich hab schon die Wurzel 2 raus, aber das ändert nix. Wie kann ich denn den Pfad konstant halten? Dann hab ich noch eine Frage: Dein Algorithmus berechnet auch die diagonalen Nachbarn, doch mein Spieler kann ja nicht um Ecken gehen, wenn du weisst was ich meine? Ich möchte erreichen, dass der Spieler bei Kollision nur horizontal und vertikal laufen kann, um ein Hindernis zu umgehen und ansonsten auch diagonal. Wie erreiche ich das? Hab schon einiges probiert doch nichts fruchtet. Gruß Tommy |
||||||||||||||
28.03.2016, 10:07 | Auf diesen Beitrag antworten » | ||||||||||||||
eulerscheZahl | OpenList hast du als Set implementiert. Das Problem ist, dass ein HashSet keine feste Reihenfolge sicherstellt. Du könntest die Ordnung sicherstellen, indem du z.B. TreeSet statt HashSet nimmst - das sichert die richtige Reihenfolge. Du musst dann natürlich compareTo überschreiben. Netter Nebeneffekt: ich hatte schon geschrieben, dass das schlecht ist
Beim TreeSet musst du nicht nach dem kleinsten Wert suchen, da bereits sortiert ist. Das verbessert die Laufzeit. Die einfachste Möglichkeit, das Diagonallaufen zu verhindern, wäre die Nachbarschaftsbeziehung zu modifizieren:
|
||||||||||||||
28.03.2016, 20:02 | Auf diesen Beitrag antworten » | ||||||||||||||
Tommy1234 | Habe jetzt das TreeSet implementiert und versucht die erweiterte for-Schleife durch einen Iterator und eine while-Schleife zu ersetzen. Hat zwar funktioniert, aber je größer die Distanz zwischen startPunkt und endPunkt, desto langsamer wurde die Pfadsuche und man konnte dann auch eine Verzögerung während der Zuweisung erkennen. Frage: HashSet -----> HashMap TreeSet ------> TreeMap Bei TreeMap<Field,Double> in der Methode addNeighbours hat mir der Compiler gemeldet, dass er Field nicht casten kann zu Comparable. Gruß Tommy |
||||||||||||||
29.03.2016, 09:37 | Auf diesen Beitrag antworten » | ||||||||||||||
eulerscheZahl |
Du musst ja auch auf mich hören
Das schließt ein implements Comparable ein. Wie auch immer, bei mir wackelt der Weg nicht mehr. Eigentlich sollte ich jetzt sämtliche Zeilenumbrüche rauslöschen
|
||||||||||||||
29.03.2016, 16:21 | Auf diesen Beitrag antworten » | ||||||||||||||
Tommy1234 |
HaHa Ok, habs soweit verstanden. Ich werde mich die nächste Woche nicht mehr melden, denn ich werde mich intensiv mit Deinem Code und Sets, Maps und Queues auseinandersetzen. Ich hatte dieses Kapitel in der Insel blos überflogen und für unnötig befunden... . Jetzt sehe ich, dass mir diese Grundlagen erstens fehlen und zweitens das Leben durchaus vereinfachen können. Die Anwendung des Algorithmus auf großen Maps ist denke ich für mich machbar. Für den weiteren Verlauf meines Projekts, werde ich nun weiterkommen. Vielen, vielen Dank nochmal für Deine Geduld und Deine Mühe, Du hast mir sehr geholfen und ich hab wieder was gelernt. Gruß Tommy |
||||||||||||||
29.09.2016, 19:27 | Auf diesen Beitrag antworten » | ||||||||||||||
Tommy1234 | Weitere Ergänzungen zu A-Stern Hallo mal wieder, hatte viel um die Ohren und komme erst jetzt wieder zum programmieren. Ich habe mich in Sets, Listen und Maps eingelesen und ein wenig herumexperimentiert mit dem Ergebnis, dass eulerscheZahl die beste Lösung mit dem TreeSet bereits verwendet hat. Außerdem experimentiere ich mit dem A* viel und komme doch an einigen Stellen nicht weiter. Gleich zu meinen Fragen: Also, wenn ich zwar die Größe eines booleanGrids definiert habe aber keine Blockade eingebaut habe,dann müsste doch, wenn startx bzw. starty 0,0 ist und zielx bzw ziely einfach die geklickte aktuelle Mausposition darstellt, der gemalte Pfad einfach eine Linie vom Start zum Ziel darstellen. Tuts aber nicht, WIESO? Die zweite Frage betrifft folgendes: Ich habe ein isometrisches Feld erstellt mit isometrischen Texturen die auch korrekt angezeigt werden. Was ist jetzt, wenn ich den A* auf ein isometrisches Spielfeld anwenden möchte bezüglich des boolean grids und des tatsächlichen isometrischen Spielfeldes? Ich stelle mir das in etwa so vor, dass der Spieler (ein isometrisch dargestelltes Rechteck) über das isometrische Spielfeld laufen und der A* dabei Hindernisse erkennt und der Spieler darum herumlaufen kann. Also im Prinzip nichts anderes als ein orthogonales Spielfeld mit rechteckigen Kacheln nur eben isometrisch. Schließlich noch etwas, was ich bereits gefragt habe: Die Laufzeit leidet stark bei dieser Implementierung ( nicht falsch verstehen bin ja dankbar für die investierte Zeit von eulersche Zahl ), d.h., dass beim Starten der Applikation ca. 3 Sekunden vergehen bis der Spieler angezeigt wird und pro Klick vergehen ca. 1,5 Sekunden. Das ganze läuft natürlich besser wenn man statt 1x1, 32x32 hernimmt und so schnell wie bei letzterem sollte der A* auch bei 1x1 gehen. Ist das überhaupt möglich und was kann man noch verbessern??? (Ich hab das noch nicht ganz verstanden, deshalb frage ich) Mir ist klar, dass sehr viele Punkte berechnet werden müssen, aber wenn man an professionelle Spiele denkt, funktioniert es ja auch. Ok, ziemlich viel. Wäre aber dennoch für einen geduldigen Menschen dankbar, der mir etwas dazu sagen kann. Gruß Tommy |
||||||||||||||
30.09.2016, 08:09 | Auf diesen Beitrag antworten » | ||||||||||||||
Tommy1234 | Mir gibt noch etwas zu bedenken, nämlich die Nachbarknoten. (also bei addNeighbours) In Deinem Code berechnest Du alle Nachbarknoten von allen möglichen Knoten auf einmal und das pro Frame. Ich denke, dass genau das die Laufzeitprobleme verursacht. Ich dachte aber, dass man nur die Nachbarknoten des gerade zu untersuchenden Knotens berechnen muss zur Laufzeit. Kann mich aber auch irren. Gruß Tommy |
|