# A* verbesserte Laufbewegung



## Eichelhäer (13. Mrz 2019)

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?


----------



## VfL_Freak (14. Mrz 2019)

**bahnhof** ????


----------



## Eichelhäer (17. Mrz 2019)

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 (17. Mrz 2019)

Eichelhäer hat gesagt.:


> Einheiten kachelbasiert bewegen also mittels pathfinding um blockierte Felder und Einheiten herum.





Eichelhäer hat gesagt.:


> Nun versuche ich die Bewegung aufzuwerten, indem ich die Einheiten abwechseln via luftlinie und a* bewege.


was ist denn der Unterschied zwischen den beiden?

Ich les bei beiden raus, du berechnest irgendwie den Pfad (wie ist ja egal) und bewegst die Einheiten entsprechend.


----------



## Eichelhäer (26. Mrz 2019)

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?


----------



## Eichelhäer (26. Mrz 2019)

Noch kurzer Nachtrag. Es soll im Code in Etwa so aussehen:

if(checkSurroundingTiles) {
moveWithPathfing() ;
else{
moveDirectly() ;
}


----------



## mrBrown (26. Mrz 2019)

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 (26. Mrz 2019)

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 (26. Mrz 2019)

Innerhalb der Kacheln gibt es also keinerlei Hindernisse?


----------



## Eichelhäer (26. Mrz 2019)

Nein gibt es nicht. Mir reicht erstmal ein weniger aufwendiges Projekt.


----------



## mrBrown (26. Mrz 2019)

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)



```
_________
4|_|_|_|x|
3|_|/|/|/|
2|_|_|_|/|
1|_|_|_|o|
  1 2 3 4
```


----------



## Eichelhäer (26. Mrz 2019)

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 (26. Mrz 2019)

Eichelhäer hat gesagt.:


> 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



Eichelhäer hat gesagt.:


> 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 (30. Mrz 2019)

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 (3. Mai 2019)

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 (15. Mai 2019)

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?


----------



## Xyz1 (17. Mai 2019)

Was willst machen? Lass mal das Fachchinesisch weg.


----------



## Eichelhäer (18. Mai 2019)

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


----------

