# Figur Rotation



## Pfaeff (28. Feb 2009)

Hallo,

Ich möchte ein paar Figuren entlang eines Pfades bewegen, das funktioniert auch schon soweit. Jetzt sollen sich diese erst immer auf dem kürzest möglichen Weg in Richtung Ziel drehen, bevor sie weitergehen. 
Das funktioniert eigentlich auch schon ganz gut, nur leider kommt es ab und zu zu Sprüngen, die ich mir nicht erklären kann. (Also keine Weiche Bewegung sondern eine instantane 180° Drehung z.B.)
Ich finde meine Lösung (das abfragen des Winkels zum Ziel) auch noch nicht besonders elegant, vielleicht liegt das Problem auch an der Umsetzung. 
dt ist die vergangene Zeit.
speed ist der betrag der geschwindigkeit
position ist die position der Figur
velocity ist der geschwindigkeitsvektor
target ist das Ziel zu dem die Figur laufen soll

[HIGHLIGHT="Java"]    public void update(float dt) {        
        // Ziel erreicht, nächstes auswählen
        if (Vector2D.distanceSquare(position, target) <= speed*dt) {
            nextTarget();    
        }
        // move ist der Vektor von der Position zum Ziel     
        Vector2D move = Vector2D.sub(target, position);
        // Winkel (rad) zwischen derzeitiger Bewegungsrichtung und Zielrichtung
        float alpha = Vector2D.angle(velocity, move);
        // Ermittelt ob Rechts- oder Linksdrehung erfordlich ist
        float cP = Vector2D.crossProduct(move, velocity);
        // Ist der Winkel größer als ein gewisser Grenzwert muss sich die Figur zunächst drehen (geht das nicht auch eleganter?)
        if (alpha > 0.8f*dt) {
            if (cP < 0) {
                velocity = velocity.rotate(1.8f*dt);
            } else {
                velocity = velocity.rotate(-1.8f*dt);
            }
        } else {
            // Ansonsten geht sie ganz normal Richtung Ziel
            velocity = move.normalize();
            velocity = Vector2D.scale(velocity, speed);
            position = Vector2D.add(position, Vector2D.scale(velocity, dt));
        }
    }[/HIGHLIGHT]

Vielen Dank schonmal,

mfg


----------



## 0x7F800000 (28. Feb 2009)

weiß jetzt nicht, was konkret hier das problem ist, aber winkelberechnungen sind immer stressig und performancefressend
Vielleicht gefällt dir die idee mit dem auf + - * beschränkten Kreuzprodukt mehr:
http://www.java-forum.org/mathematik/78410-kuerzeste-drehbewegung-berechnen.html#post482355

(sin und cos-berechnungen kann man eigentlich auch wegschmeißen, wenn man es nicht zu genau braucht, man kann dann die rotationsmatrix einfach auf festen wert setzen, bei den meisten Speielen ist rotationgeschwindigkeit nicht sooo extrem ausschlaggebend. Dann hätte man dasselbe erreicht, aber nur mit + - * also mit billigen rechenoperationen, ohne den ganzen lahmen trigonometrischen krempel)


----------



## Pfaeff (28. Feb 2009)

Das ist ja im Grunde genau das was ich mache, nur liegt noch irgendwo der Hund begraben


----------



## 0x7F800000 (28. Feb 2009)

Naja, wie gesagt: könnte dran liegen, dass du diese Winkelberechnungsmethode irgendwie krumm implementiert hast, und dass die jetzt irgendwas +-180° liefert...

Ansonsten sind ferndiagnosen etwas schwierig, kompilieren kann man deinen code ja nicht, und das im kopf durchzuspielen ist nicht allzu spaßig. Poste mal minimales kompilierbares Beispiel, vielleicht guggt sich das dann einer an...


----------



## Marco13 (28. Feb 2009)

Ansonsten kannst du versuchen, ein einfaches, anschauliches Beispiel zu finden, wo der Fehler auftritt, und dann mit Debug-Ausgaben nachvollziehen, was schiefgeht:

```
System.out.println("Want to move from "+position+" to "+target);
    System.out.println("Current direction "+direction);
        if (alpha > 0.8f*dt) {
            if (cP < 0) {
                velocity = velocity.rotate(1.8f*dt);
                System.out.println("Rotated left, direction now "+direction);
            } else {
                velocity = velocity.rotate(-1.8f*dt);
                System.out.println("Rotated right, direction now "+direction);
            }
```


----------



## Pfaeff (1. Mrz 2009)

Ich habe schon ein wenig gedebuggt und es scheint bei Winkeln aufzutreten die annähernd 180° sind. Ich bin mir da aber noch nicht so ganz sicher. Bevor ichs genau raus hab, poste ich hier mal noch relevanten Code für die Winkel Berechnung, vielleicht sticht da ja was offensichtliches ins Auge :

```
// Vielleicht kann ich das Gleiche auch ohne acos erreichen, acos benötige ich aber an anderer Stelle noch
    public static float angle(Vector2D v1, Vector2D v2) {
        return (float)Math.acos(cosAngle(v1, v2));
    }
    public static float cosAngle(Vector2D v1, Vector2D v2) {
        if ((v1.length() == 0) || (v2.length() == 0))
            return 1;
        return (dotProduct(v1, v2) / (v1.length() * v2.length())); 
    }
    // Berechnet das "Kreuzprodukt" zweier Vektoren
    public static float crossProduct(Vector2D v1, Vector2D v2) {
        return (v1.x*v2.y-v1.y*v2.x);
    }
```


----------



## 0x7F800000 (1. Mrz 2009)

ich kann schonmal sagen:
/(v1.length()*v2.length())
tut weh. Du ziehst du zweimal die Wurzel. Du musst zuerst die quadratischen Längen ausrechnen,multiplizieren, und erst danach die wurzel ziehen, dann läuft's schonmal zweimal schneller. Ansonsten: sieht eigentlich nicht sonderlich verdächtig aus...


----------



## Pfaeff (1. Mrz 2009)

ja Geschwindigkeit ist erstmal ein sekundärer Faktor, ich weiß dass sich da noch viel machen lässt, aber ich nutze die Funktionen auch nicht allzu häufig. Danke trotzdem für den Tipp 

mfg


----------



## EgonOlsen (2. Mrz 2009)

Andrey hat gesagt.:


> ich kann schonmal sagen:
> /(v1.length()*v2.length())
> tut weh. Du ziehst du zweimal die Wurzel. Du musst zuerst die quadratischen Längen ausrechnen,multiplizieren, und erst danach die wurzel ziehen, dann läuft's schonmal zweimal schneller. Ansonsten: sieht eigentlich nicht sonderlich verdächtig aus...


Sorry, aber das ist an dieser Stelle sowas von egal. Er bewegt EINE Figur und nicht tausende. Was meinst du, wieviele Wurzeln und ähnliches du pro Frame ziehst, wenn du z.B. Kollisionsberechnung in 3D machst!? Das auf heutigen Systemen kein Problem, sofern es nicht völlig ausufert.


----------



## 0x7F800000 (2. Mrz 2009)

EgonOlsen hat gesagt.:


> Was meinst du, wieviele Wurzeln und ähnliches du pro Frame ziehst, wenn du z.B. Kollisionsberechnung in 3D machst!?


Hehe, hab hier neulich zum spaß die wurzelziehung aus der Kollision von Kugeln herausoptimiert (die klasse ist irgendwie immer stets vorhanden, für billard oder gassimulationen, und weil's so lustig aussieht^^) und habe festgestellt, dass dank dieser Optimierung und einer etwas angemesseneren Raumunterteilung ich plötzlich zehn mal so viele Kugeln rumdotzen lassen konnte, das find ich schon recht witzig  Ich weiß zwar nicht wieviel das ziehen der wurzel dabei ausmacht, aber ich meine mich erinnern zu können, dass wurzelziehen um größenordnungen teuer ist, als die relativ teuere division... Muss aber nicht stimmen, hab grad keine Lust es zu testen...


----------



## Marco13 (2. Mrz 2009)

Ich stimme da mal ganz dezent zu. Auch wenn die eigentlich peinliche Sache ja eher die war, dass vorher schon zweimal "length" ausgerechnet wurde, und dieses Resultat dann nicht weiterverwendet wurde:

```
public static float cosAngle(Vector2D v1, Vector2D v2) 
{
    float lenSquared1 = v1.lengthSquared();
    float lenSquared2 = v2.lengthSquared();
        if ((lenSquared1 == 0) || (lenSquared1 == 0)) // ==-Vergleiche bei floats sind eigentlic auch nicht gut...
            return 1;
        return (dotProduct(v1, v2) / ... hier jetzt Math.sqrt(lenSquared1) oder besser(!) : gleich lenSquared1 verwenden
    }
```

Wurzelziehen IST ziemlich teuer. Und wenn man mit geringem Aufwand eine Methode x-mal schneller machen kann, dann sollte man das tun - schon _aus Prinzip_, und um den ganzen ***en, die immernoch behaupten, Java sei langsam, mal wieder ein Stück mehr den Wind aus den Segeln zu nehmen...

Und bevor der Hinweis kommt: Ich rede nicht vom "root of all evil", sondern davon, dass man keinen rautavistischen code produzieren sollte....


----------



## Pfaeff (2. Mrz 2009)

Vielleicht ist meine length() Methode aber auch intelligent und berechnet die Länge nur dann neu, wenn sich etwas verändert hat? Naja back2topic wär wohl spätestens jetzt angesagt


----------



## 0x7F800000 (2. Mrz 2009)

Pfaeff hat gesagt.:


> Vielleicht ist meine length() Methode aber auch intelligent und berechnet die Länge nur dann neu, wenn sich etwas verändert hat? Naja back2topic wär wohl spätestens jetzt angesagt


omfg  um Himmels Willen, mach deine Vektorklasse lieber immutable, aber mache auf keinem fall jedes mal irgendwelche "ist xy bereits berechnet?"-Abfragen, das will eh keiner haben, und es zieht einfach bei jeder primitivsten operation ein bisschen was von der geschwindigkeit ab, und bläht den code unnötig auf.


----------



## Marco13 (2. Mrz 2009)

Hm. Bei Vektoren und Längen macht das wohl nicht sooo viel Sinn, aber ganz allgemein kann sowas schon OK sein. (Hab' gerade das Beispiel von der BoundingBox eines Objektes im Kopf - bei jeder Änderung wird die BoundingBox auf "null" gesetzt, und bei jeder Abfrage nur neu Berechnet, wenn sie null ist - nur als Beispiel).

Back to... was? Ach, Topic. Ja, geht's jetzt oder wie?


----------



## Pfaeff (3. Mrz 2009)

Andrey hat gesagt.:


> omfg  um Himmels Willen, mach deine Vektorklasse lieber immutable, aber mache auf keinem fall jedes mal irgendwelche "ist xy bereits berechnet?"-Abfragen, das will eh keiner haben, und es zieht einfach bei jeder primitivsten operation ein bisschen was von der geschwindigkeit ab, und bläht den code unnötig auf.


das war ein Scherz.

B2T


----------

