A* verbesserte Laufbewegung

Eichelhäer

Bekanntes Mitglied
Hallo,

in meinem Isometrischen Spielfeld (kachelbasiert) versuche ich das Bewegungsverhalten meiner Sprites zu verbessern.
Will heißen bisher laufen meine Sprites exakt nach dem mit der Maus vorgegebenen Pfad, was auch funzt, allerdings denke ich mir ich brauche ja nicht für Bewegungen von A nach B ohne Hindernisse dazwischen kachelbasiert gehen, sondern einfach Luftlinie (Pythagoras).
Muss man da ständig alle 8 umliegenden Kachel beim normalen gehen ( Pythagoras ) prüfen und wenn eine nicht begehbar ist den Astern laufen lassen bis keines der acht felder mehr ein hindernis ist?
 

Eichelhäer

Bekanntes Mitglied
Ok, ich habe ein isometrisches grid auf dem sich Einheiten kachelbasiert bewegen also mittels pathfinding um blockierte Felder und Einheiten herum. Die Einheiten bewegen sich nacheinander. Also Einheit gibt ihr Feld frei nächste Einheit bewegt sich. Allerdings kachelbasiert.
Nun versuche ich die Bewegung aufzuwerten, indem ich die Einheiten abwechseln via luftlinie und a* bewege.
Wie geht man da vor?
 

mrBrown

Super-Moderator
Mitarbeiter

Eichelhäer

Bekanntes Mitglied
Naja den Pfad berechne ich kachelbasiert und ein Knoten des Pfades ist eine 64x32 (dimetrische) Kachel und anhand dieser Kacheln bewege ich die Einheiten letztenendes pixelbasiert innerhalb des Spielfeldes, während die Bewegung via Luftlinie ohne Pfad Erfolg (siehe atan-Funktion usw) was auch beides funktioniert.
Nun versuche ich beide Bewegungsformen zu kombinieren, indem ich den a* nur dann verwende, wenn die Einheit wirklich um ein Hindernis herum muss. Ansonsten ist ja, also ohne Hindernis zwischen Start und Ziel, die luftlinie der kürzeste weg. Wie erreicht man das? Denn bei 50 Einheiten und mehr jeweils bei Bewegung aller 8 umliegenden Kacheln auf Hindernisse zu prüfen kostet Laufzeit oder irre ich mich da?
 

mrBrown

Super-Moderator
Mitarbeiter
Kannst du eine kurze Übersichtszeichnung machen, wie der A* und wie der Luftlinienpfad aussehen?

Wenn ich dich richtig verstehe, können sich Einheiten auch innerhalb eine Kachel beliebig bewegen?
 

Eichelhäer

Bekanntes Mitglied
Keine übersichtszeichnung nötig. Ich denke du hast mich jetzt verstanden.
Luftlinie ist der direkte Weg von a nach b ohne Hindernisse quer über alle begehbaren Kacheln.
A* ist Kachel abhängig und verläuft gerastert über die Kacheln.
 

mrBrown

Super-Moderator
Mitarbeiter
Einheiten können sich aber selbst im Weg stehen, und müssen einander ausweichen?



Generell kannst du A* und Luftlinie dabei gleich verwenden:
* Alle Kacheln, die per Luftlinie betreten werden, berechnen
* Testen, ob alle/die nächste im Pfad frei ist
* Wenn Nein, A*

Kannst A* und Luftlinie auch kombinieren:
* Pfad per A*
* Einzelne Pfadstücke soweit möglich per Luftlinie ablaufen lassen


Bsp: erst A*, dürfte etwa (4,1),(2,2),(1,3),(2,4),(3,4),(4,4) rauskommen, und dann per Luftlinie wenn möglich: (1,3),(2,4),(4,4)


Code:
_________
4|_|_|_|x|
3|_|/|/|/|
2|_|_|_|/|
1|_|_|_|o|
  1 2 3 4
 

Eichelhäer

Bekanntes Mitglied
Ok habs verstanden.

Die Einheiten auf dem Feld sind selber nicht begehbar also werden vom A* berücksichtigt und das Ausweichen klappt auch tendenziell ganz gut,allerdings nicht immer. Der Pfad wird stets zur Laufzeit berechnet und es entstehen laufzeitabhängige Varianten zwar nicht immer, aber manchmal.

Und noch etwas: Bringt es etwas mehrere markierte Einheiten nacheinander zu bewegen oder ist das egal?
 

mrBrown

Super-Moderator
Mitarbeiter
Die Einheiten auf dem Feld sind selber nicht begehbar also werden vom A* berücksichtigt und das Ausweichen klappt auch tendenziell ganz gut,allerdings nicht immer. Der Pfad wird stets zur Laufzeit berechnet und es entstehen laufzeitabhängige Varianten zwar nicht immer, aber manchmal.
Sind Einheiten denn kleiner als eine Kachel?

Dauerhaft neu berechnen kann man durchaus noch ändern zu neu berechnen bei Kollision, da gäbe viele Möglichkeiten

Und noch etwas: Bringt es etwas mehrere markierte Einheiten nacheinander zu bewegen oder ist das egal?
Ohne zu wissen was "markiert" und "nacheinander" in deinem Spiel(?) bedeuten, kann man da wenig sagen ;)
 

Eichelhäer

Bekanntes Mitglied
Markiert ist eine Einheit dann, wenn man eine Kachel auf der eine Einheit steht, anklickt. Es erscheint dann der bekannte Lebensbalken und eine kreisförmig BoundingBox, zwecks Kollisionserkennung.

Mit nacheinander bewegen meine ich, dass wenn mehrere Einheiten markiert sind die mit der geringsten Entfernung zum Ziel zuerst geht, bei gleichartigen Einheiten und gleichem Weg, die mit der kleinsten ID, also Bauer Nummer 2 geht vor Bauer Nummer 3.
Der Vorgang soll so verlaufen, dass wenn die Einheit mit dem kürzesten Weg ihr aktuelles Feld verlassen hat, die nächste Einheit in Richtung Ziel läuft.

Das mit den Boundingboxes mach ich deshalb, um zu vermeiden, dass die Einheiten ineinaderlaufen.

Ich bräuchte bei beiden, also sowohl bei dem Nacheinander gehen Algorithmus, als auch bei der Kollision noch Hilfe.

Bin schon sehr lange am grübeln wie man das für alle Einheiten einer Liste realisiert?
 

Eichelhäer

Bekanntes Mitglied
Hallo nochmal,

ich versuche immernoch das Einheitenmanagement gut hinzukriegen. Das mit den BoundingBoxes will nicht so recht also bewege ich nun zuerst die Einheit zur Laufzeit mit dem kürzesten Pfad und lass die anderen folgen, indem ich die zielposition des a* immer auf das zuletzt betretene Tile des Vorgängers setzte. Das klappt auch tadellos bei bis zu drei Einheiten. Bei zwölf ist das aber extrem laggy.

Wie kann man denn zur Laufzeit erreichen, dass der Pfad beim Klicken einmal aufgerufen wird und die übrigen einheiten folgen können?

Ich schaff das eben nur bei Berechnung der Pfade zur Laufzeit und das ganze auch noch innerhalb dreier Schleifen ( inkl Gameloop).
 

Eichelhäer

Bekanntes Mitglied
Hallo nochmal,
habe mich in Sachen Ai movement etwas eingelesen. Formationen und Gruppen Bewegungen zu implementieren ist denke ich nicht einfach. Deshalb hier die Frage hat jemand hier schon Erfahrung mit derartigen Algorithmen?
 

Eichelhäer

Bekanntes Mitglied
Naja eine Gruppe von Einheiten bewegen ohne dass diese möglichst nicht ineinanderlaufen. Mittlerweile hab ich den Flockig Algorithmus und er funktioniert.
 

Ähnliche Java Themen

Neue Themen


Oben