RTS: Bewegung der Einheiten



  • Hallo!

    Ich arbeite gerade an einem Echtzeitstrategiespiel. Mein bisheriger Plan war es, dass Einheiten sich unterschiedlich schnell bewegen. Sie haben also ein Attribut "Geschwindigkeit", dass die Einheit [pixel/berechnungsschritt] hat, um es kurz zu halten.

    Ich habe kein Grid, alle Einheiten können sich frei an jede Stelle bewegen. Mein A*-Algorithmus lässt dabei die Himmelsrichtungen NordWest, Norden, NordOst usw. zu. D.h. heißt: Bewegt sich eine Einheit mit 10 Pixel/Schritt, dann ist das für die Bewegungen auf x-Achse oder y-Achse schön einfach zu berechnen. Beispielsweise für Osten:

    currPos.x += 10;
    

    Jetzt das Problem:
    Die diagonalen Bewegungen machen mich ein wenig fertig. Da komme ich ja quasi immer auf ungerade dx und dy-Anteile, und bin somit auf Fliesskommaberechnungen angewiesen. Beispiel SüdOst bei 10 Pixel/Schritt:

    dx = dy = sin( 45° )*10 ~= 7.07

    Fliesskommaberechnungen will ich eigentlich soweit es geht vermeiden...

    1.) Ist mein Ansatz mit Pixel/Berechungsschritt grundsätzlich Mist?
    2.) Falls der Ansatz so erstmal gut ist: Kann ich irgendwie die Fliesskommaberechnungen umgehen?

    Danke für das Lesen zu später Stunde. Gute Literatur für diese Thematik ist auch gerne gesehen, ich hab das Gefühl für RTS-Programmierung gibt's kaum Material aus guter Quelle.



  • Wenn du keine exakten Bewegungen benötigst, kannst du sicher auch mit gerundeten Werten umgehen: currPos.x+=0.7*speed;currPos.y+=0.7*speed; (der exakte Wert wäre sqrt(1/2))



  • CStoll schrieb:

    Wenn du keine exakten Bewegungen benötigst, kannst du sicher auch mit gerundeten Werten umgehen: currPos.x+=0.7*speed;currPos.y+=0.7*speed; (der exakte Wert wäre sqrt(1/2))

    Hmm, also gänzlich umgehen geht eher nicht, nehme ich an?
    Dann wäre das Vorgehen ja: Intern mit gerundeten Fliesskommazahlen arbeiten, beim Zeichnen die Position auf Ganzzahl runden.



  • Du kannst auch "speed*7/10" verwenden, wenn du wirklich nur mit Ganzzahl-Arithmetik arbeiten willst.


  • Mod

    SmartTan schrieb:

    1.) Ist mein Ansatz mit Pixel/Berechungsschritt grundsätzlich Mist?

    Nein, dein Ansatz ist gut, gerade wenn man mal netzwerkunterstuetzung einbauen will, muss man float meiden, da sonst alles immer weiter auseinander driften kann bei der simulation, je nachdem welche cpu etc. die einzelnen leute verwenden.

    2.) Falls der Ansatz so erstmal gut ist: Kann ich irgendwie die Fliesskommaberechnungen umgehen?

    du simulierst schon fixpoint, indem du sagst, dass du "pixel" als einheit hast, aber in wirklichkeit dein A* mit 10er einheiten arbeitet, das ist ja quasi so als ob du ein grid haettest und deine einheit in 0.1 schritten arbeiten wuerde.
    du solltest einfach deine pixel pixel sein lassen, dein grid waehlen wie du moechtest, und dann mit fixpoint arbeiten von z.b. 10bit.



  • SmartTan schrieb:

    Ich habe kein Grid, alle Einheiten können sich frei an jede Stelle bewegen. Mein A*-Algorithmus lässt dabei die Himmelsrichtungen NordWest, Norden, NordOst usw. zu...

    Was sind denn deine Knotenpunkte für den A* Algo, wenn du kein Grid hast? 😕



  • Cpp_Junky schrieb:

    SmartTan schrieb:

    Ich habe kein Grid, alle Einheiten können sich frei an jede Stelle bewegen. Mein A*-Algorithmus lässt dabei die Himmelsrichtungen NordWest, Norden, NordOst usw. zu...

    Was sind denn deine Knotenpunkte für den A* Algo, wenn du kein Grid hast? 😕

    Da ich keine Informationen gefunden hab, hab ich mir selber eine Lösung überlegt:
    Jede meiner Einheiten hat einen eigenen Radius, d.h. es kann z.B. einen dicken Oger oder einen kleinen Arbeiter geben. Dieser Radius wird von A* zur Berechnung der Nachbarfelder verwendet. Das hat den Vorteil, dass z.B. der kleine Arbeiter zwischen zwei Bäumen ggfs. noch durchpasst, der Oger nicht. Ich hab einfach mal einen Screenshot gemacht:

    http://www.abload.de/img/erstereindruck1p4j.png

    Man sieht einen Arbeiter (den ich aus Warcraft 2 geklaut habe, da ich nicht zeichnen kann 😉 ), der läuft. Die Kreise haben genau den Umfang des Arbeiters, für den der Pfad gesucht wurde. Die lilanen Knoten gehören zur offenen Liste, die gelben zur geschlossenen Liste. Die Zahlen sind die Kosten. Falls jemand eine bessere Idee hat, war ich den A* einsetzen kann: Nur her damit.

    ⚠ Ich habe allgemein wirklich das Problem, dass ich keine guten Informationen zum RTS-Programmierung finde. Auch den Quadtree, mit dem ich meine Karte verwalte (siehe das graue Gitter) ist eine vollständige Eigenentwicklung mit meinen eigenen Ideen. Wenn jemand wirklich gutes Material hat und sei es nur ein Buchtitel, dann leih mir das Buch aus. Als bitte nennen 🙂 ⚠



  • SmartTan schrieb:

    1.) Ist mein Ansatz mit Pixel/Berechungsschritt grundsätzlich Mist?
    2.) Falls der Ansatz so erstmal gut ist: Kann ich irgendwie die Fliesskommaberechnungen umgehen?

    1. Ja, wegen Aufloesungsabhaengigkeit, ansonsten gehts du in die richtige Richtuing. Pixel sind aber vermutlich auch noch zu gross fuer "schoene Bewegungen". Besser ist es den Tile in z.b. 1024^2 Untertiles zu unterteilen. Geschwindigkeit ist dann wieder Untertiles pro Berechnungsschritt.
    2. Ja, ergibt sich direkt aus meinem Vorschlag 1. Rechne deine Geschwindigkeit einfach *1000/707 fuer z.b. 45 Grad. Du kannst dir eine Liste von Faktoren fuer alle benoetigten Gradschritte erstellen, mit dem du die Geschwindigkeit umrechnest. Sollte dir das zu ungenau werden, erhoehe die Aufloesung der Untertiles.

    @Cpp_Junky: A* hat noch nie ein Grid benoetigt.



  • Aus welchem Grund willst du denn eigentlich keine Fliesskommawerte verwenden?

    @TGGC: Na aber irgendwelche Knotenpunkte an denen du dich vorbeibewegst und der Klassiker ist halt das Tilegrid zu verwenden.



  • Cpp_Junky schrieb:

    Aus welchem Grund willst du denn eigentlich keine Fliesskommawerte verwenden?

    Ich hätte gesagt, weil eine Fliesskommaaddition immer noch langsamer ist als eine Ganzzahladdition.

    TGGC schrieb:

    SmartTan schrieb:

    1.) Ist mein Ansatz mit Pixel/Berechungsschritt grundsätzlich Mist?
    2.) Falls der Ansatz so erstmal gut ist: Kann ich irgendwie die Fliesskommaberechnungen umgehen?

    1. Ja, wegen Aufloesungsabhaengigkeit, ansonsten gehts du in die richtige Richtuing. Pixel sind aber vermutlich auch noch zu gross fuer "schoene Bewegungen". Besser ist es den Tile in z.b. 1024^2 Untertiles zu unterteilen. Geschwindigkeit ist dann wieder Untertiles pro Berechnungsschritt.
    2. Ja, ergibt sich direkt aus meinem Vorschlag 1. Rechne deine Geschwindigkeit einfach *1000/707 fuer z.b. 45 Grad. Du kannst dir eine Liste von Faktoren fuer alle benoetigten Gradschritte erstellen, mit dem du die Geschwindigkeit umrechnest. Sollte dir das zu ungenau werden, erhoehe die Aufloesung der Untertiles.

    @Cpp_Junky: A* hat noch nie ein Grid benoetigt.

    Ich hab deinen Vorschlag jetzt nicht genau verstanden. Im Prinzip habe ich erstmal keine Tiles, also auch keine TileGrid. Du meinst, ich soll ein TileGrid über meine Karte legen und darüber die Bewegungsgeschwindigkeit steuern?
    Ich verstehe den Ansatz nicht ganz.

    // Ich hab mich jetzt einfach mal angemeldet, weil ich es ganz nett hier finde 😉


  • Mod

    SmartTan schrieb:

    Cpp_Junky schrieb:

    Aus welchem Grund willst du denn eigentlich keine Fliesskommawerte verwenden?

    Ich hätte gesagt, weil eine Fliesskommaaddition immer noch langsamer ist als eine Ganzzahladdition.

    float sollte auch 1cycle fuer addition und subtraktion brauchen, zudem ist mul und div schneller und schlussendlich koenntest du auch SSE benutzen fuer deine mathematischen sachen, damit bist du schneller als mit int.



  • SmartTan schrieb:

    Ich hätte gesagt, weil eine Fliesskommaaddition immer noch langsamer ist als eine Ganzzahladdition.

    Und selbst wenn es so wäre, riecht das stark nach Mikrooptimierung. Dann läuft das Spiel statt mit 11.345ms 11.342ms 😉



  • SmartTan schrieb:

    Ich hab deinen Vorschlag jetzt nicht genau verstanden. Im Prinzip habe ich erstmal keine Tiles, also auch keine TileGrid. Du meinst, ich soll ein TileGrid über meine Karte legen und darüber die Bewegungsgeschwindigkeit steuern?

    Dann benutze doch einfach eine arbitraere Tilegroesse, z.b. 1 Tile == Groesse der Standardeinheit. Irgendeine Einheit wirst du sowieso benoetigen, um alle moeglichen Werte im Spiel zu balancen. z.b. wie weit sieht eine Einheit, wie weit schiesst sie oder eben wie schnell bewegt sie sich.

    Cpp_Junky schrieb:

    der Klassiker ist halt das Tilegrid zu verwenden.

    Noe. Das Tilegrid ist ein sehr spezieller Anwendungsfall von A*, der aber in der Spieleprogrammierung durch RTS sehr bekannt geworden ist.


Log in to reply