C++ Bewegungsrichtung programmieren

[Furtano]

Hallo,

ich schreibe eine Ameisensimulation, und jede einzelne Ameise, soll sich in eine bestimmte Bewegungsrichtung bewegen (z.B. 30°).
Sie marschieren auf einer Matrix z.B. int matrix [100][100].

Wie kann man die Bewegungsrichtung auf der "rechteckigen" Matrix übertragen?

Hab sowas noch nie gemacht.

Danke.

 

[Saio]

Durch Vektoren!

 

[Limeray]

Dafür gibt es in der Mathematik die Winkelfunktionen (link)

Du kannst hier mit angegebenen Winkel und Länge die du dich bewegen willst, die die X und Y Verschiebung berechnen.

Vektoren sind zwar erst ein mal keine falsche Antwort aber auch hier musst du erst mal die X und Y Komponente berechnen.

 

[asdfman]

Zusätzlich ist vermutlich soetwas wie der Bresenham-Algorithmus hilfreich, damit man auch bei allen Winkeln diskrete Koordinaten bekommt.

http://en.wikipedia.org/wiki/Bresenham's_line_algorithm

 

[Nai]

Ich würde die Position der Ameise nicht als Gitterkoordinaten speichern; denn das ist einfach zu ungenau. Sondern ich würde ihr 2 Floats zuweisen. Dann hast du auch kein Problem sie kontinuierlich (per Eulerintegration) zu bewegen und musst nicht auf umständliche Workarounds wie Bresenham zurückgreifen.
Willst du ihre Position im Gitter haben musst du die Floatkoordinaten in Gitterindexe umrechnen. Dafür kannst du soetwas verwenden wie:
GitterIndexX = (int)(FloatX / DX)
GitterIndexY = (int)(FloatY / DY)

 

[Furtano]

@Saiso
Hab ich noch nie gemacht, gibt es da ein Beispiel wie ich das mit Vektoren mache?
Danke

@Nai,

deine Idee klingt interessant.
Hast du da vielleicht einen guten Link wo die Euler-Integration erklärt ist?
Hab davon noch nie gehört / angewendet.
Das kann ich dann auch im Zusammenspiel mit Richtungsvektoren benutzen?

Danke

 

[Nai]

(Explizite) Eulerintegration ist in diesem Fall die einfachste numerische Lösung der standard Bewegungsgleichung, wie man sie aus der Schule her kennt:
XPositionNeu = XPosition + XGeschwindigkeit * DT
YPositionNeu = YPosition + YGeschwindigkeit * DT

 

[Furtano]

Wie mache ich dass, wenn die Ameise noch in eine bestimmte Richtung laufen soll?

 

[maxwell-cs]

könntest du die frage etwas spezifischer formulieren?

 

[Tumbleweed]

Die Richtung steckt in der Geschwindigkeit, die nicht etwa ein Skalar, sondern ein normalisierter(!) Vektor (ggf. multipliziert mit einem Geschwindigkeitsfaktor, je nach Ameise ) ist und dieser hat eben eine Richtung, sowie einen Richtungssinn.

 

[asdfman]

Mein Mathe-LK ist jetzt 10 Jahre her, aber ist ein normalisierter Vektor nicht einer mit dem Betrag 1? Dann wäre die Positionsänderung ja konstant und man hätte damit ja gar keine Geschwindigkeitsinformation in dem Vektor, sondern eben nur die Richtung. Den dann mit dem skalaren Faktor zu multiplizieren, wie du sagst, wäre dann doch nur die Normalisierung wieder rückgängig zu machen.

Vielleicht ist das aber auch einfach nur ein Verständnisproblem von mir. Bin ja auch nicht wirklich vom Fach und die Mathematik in meiner Berufsausbildung war dann doch eher mau.

 

[Tumbleweed]

Ich hatte nur Mathe GK und es sind immerhin ~8 Jahre.

Die Idee dabei ist, dass die Berechnungslogik der Richtung einer "Spielfigur" (hier eben die Ameise) unabhängig davon ist, wie schnell sie sich bewegt. Meistens hat man ja die aktuelle Position und einen Zielpunkt, an den sich die Figur bewegen soll. Dann berechnet man die Differenz und hat somit die Richtung, aber natürlich mit einem unnützen Betrag. Würde man den Vektor so verwenden, würde die Figur sich auf längeren Strecken schneller bewegen. Daher normalisiert (genau, Betrag 1) man diesen Vektor und multipliziert ihn mit der Geschwindigkeit, die sich ja zwischen verschiedenen Figuren auch unterscheiden kann. Und dann eben noch deltaTime drauf, um es fps-unabhängig zu haben.

 

[asdfman]

Ah, alles klar. Habe nur daran gedacht, dass man sich von der Stelle an der man ist, mit einer bestimmten Geschwindigkeit weg bewegen will. Aber an eine andere Stelle HIN zu kommen, ist natürlich im allgemeinen eher, was man möchte. :3

 

[Nai]

Obwohl beide Darstellungen in etwa gleichwertig sind, würde ich die Geschwindigkeit tendentiell eher als Vektor abspeichern und nicht als Betrag und (Einheits)-Richtungsvektor, da man erstere Darstellung als solches öfter braucht, wie zB bei der der Integration insbesondere wenn man eine beschleunigte Bewegung hat. Dadurch spart man sich dann das mit Ungenauigkeiten verbundene umrechnen. Des Weiteren hat man bei der zweiten Darstellung eine Koordinatensingularität für den Fall, dass das Skalar 0 ist; solche Koordinatensingularitäten können immer Probleme (NaN, NaN, NaN . . . . . ) verursachen.

Und dann eben noch deltaTime drauf, um es fps-unabhängig zu haben.

Davon würde ich dringend abraten. Ein variables DT macht nur aber nur und nur numerische Probleme. Am besten ist ein fixes DT mit Sleep-Befehl falls der Rechner zu schnell oder mit Slow-Down falls der Rechner zu langsam ist.

 

[Hancock]

Ich stimm dir da nicht zu. Die Singularität bekommst du auch bei deinem Vektor.
Ein weiteres Problem ist, wenn du Bewegungsrichtung z.B. mit "Blickrichtung" gleichsetzt, dann hast du eine Singularität bei keiner Bewegung vs. einer eindeutigen Definition.

 

[Teiby]

Ich mach mir da immer eine Geradengleichung. Der Winkel ist m und rechne ich über eine Winkelfunktion.

y = m * x + b

Bei x addiert man einfach 1 dazu und b rechnet man aus, indem man x und y von der aktuellen Postion in die Gleichung einsetzt.

Ein Beispiel:

float winkel = 45; // in Grad°
float m = tan(winkel * PI / 180.0) / 1.0f;

float x = 5;
float y = 5;

float b = y - m * x;

float x_neu = x + 1;
float y_neu = m * x_neu + b;

 

[maxwell-cs]

bei diesem weg brauchst du kein b, da ist y_neu einfach y + m (oder genauer y + delta_x * m, aber delta_x ist bei dir ja 1).

 

[Teiby]

Ja b braucht man nicht wirklich. War nur zum Verständnis.

float b = y - m * x;
und 
float y_neu = m * x_neu + b;

wird zu
float y_neu = m * x_neu + (y - m * x);

und das kann man ausklammern zu
y_neu = m * (x_neu - x) + y

...und da sag mal einer, ich wäre in Algebra schlecht


Edit: Achja um das dann in deiner Matrix anzuzeigen, musste aus den float ein int machen.
Also so ungefähr:

int matrix[100][100];
matrix[(int)x_neu][(int)y_neu] = 1;

oder etwas moderner, aber genau das Gleiche:

int matrix[100][100];
matrix[static_cast<int>(x_neu)][static_cast<int>(y_neu)] = 1;

Ergänzung (5. Januar 2014)

Hatte gerade etwas langeweile und hab einfach mal aus Spaß dein Ameisenprogramm gemacht. Meins ist ein klein wenig Aufwendiger als deins (denk ich mal), aber vielleicht kannste ja was abschauen

http://pastebin.com/YDxVperr

Zum Austesten kannste ja mal den kompletten Quellcode in deine main.cpp Datei stecken und einfach ausführen. Hab 30 Ameisen die sich zufällig quer durch dem Raum bewegen.

 

[Hancock]

Hat die Geradengleichung kein singulären Punkt, wenn man sich senkrecht bewegt?

 

[Teiby]

Bei tan(90°) wird m unendlich. Wobei bei float irgendwann ne Grenze kommt.