Kommentare deaktiviert für Bewegung mit Kollisionserkennung Teil 3 – Demonstrationsprogramm

Teil 1 – Einführung
Teil 2 – Kollision mit Gerade
Teil 2 – Kollision mit Gerade – Demoprogramm
Teil 3 – Kollision mit Strecke
Teil 3 – Kollision mit Strecke – Demoprogramm

Zur Demonstration der bisherigen Lösung habe ich ein kleines Programm geschrieben, in welchem man sich die berechnete Lösung für beliebe Ausgangssituationen anzeigen lassen kann. Man sieht, dass nicht wirklich vorhandene Kollisionen nun nicht mehr fälschlicherweise „korrigiert“ werden.
Screenshot:

Bedienung :
Linke Maustaste, Drag&Drop : roter und schwarzer Kreis, Enden der schwarzen Linie
Rechte Maustaste, Drag&Drop : Bildschirmausschnitt
Mausrad : Zoomen

Ausprobieren: win-06.02.2011-21.09

Relevante Quellcodeausschnitte:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool TestBoundedMovement::DoLineSegmentsIntersect( sf::Vector2f s1, sf::Vector2f e1, 
	sf::Vector2f s2, sf::Vector2f e2 )
{
	sf::Vector2f v1 = e1 - s1;
	sf::Vector2f v2 = e2 - s2;
	sf::Vector2f intersection;
	if ( LinesIntersection( s1, v1, s2, v2, intersection ) ) {
		float k = LineParam( s1, v1, intersection );
		float m = LineParam( s2, v2, intersection );
		if( ( m >= 0 ) && ( m <= 1 ) &&
			( k >= 0 ) && ( k <= 1 ) ) {
			return true;
		} else {
			return false;
		}
	}  else 
		return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
bool TestBoundedMovement::LinesIntersection( sf::Vector2f s1, sf::Vector2f v1, 
	sf::Vector2f s2, sf::Vector2f v2, sf::Vector2f &intersection )
{
	if( v1.x != 0 ) {
		float a = v2.x * v1.y / v1.x - v2.y;
		if( a != 0 ) {
			float m = ( s2.y - s1.y - ( s2.x - s1.x ) * v1.y / v1.x ) / a;
			intersection.x = s2.x + m * v2.x;
			intersection.y = s2.y + m * v2.y;
			return true;
		} else {
			return false;
		}
	} else {
		if ( v2.x != 0 ) {
			float m = ( s1.x - s2.x ) / v2.x;
			intersection.x = s2.x + m * v2.x;
			intersection.y = s2.y + m * v2.y;
			return true;
		} else {
			return false;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
float TestBoundedMovement::LineParam( sf::Vector2f s, sf::Vector2f v, sf::Vector2f p )
{
	float k = 0;
	if( v.y != 0 ) {
		k = (p.y - s.y) / v.y;
	} else if ( v.x != 0 ) {
		k = (p.x - s.x) / v.x;
	}
	return k ;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
void TestBoundedMovement::UpdateCorrectDest()
{
	sf::Vector2f s = myCircleStart.GetPosition();
	sf::Vector2f v = myVector;
	sf::Vector2f pl1 = myLineBound.GetP1();
	sf::Vector2f pl2 = myLineBound.GetP2();
 
	sf::Vector2f z = s + v;
 
	sf::Vector2f ng0;
	sf::Vector2f nh0;
	if ( MathUtils::VectorLen(v) == 0 ) {
		myCircleCorrectDest.SetPosition( z );
		return;
	}
	sf::Vector2f v0 = v / MathUtils::VectorLen(v);
 
	if ( MathUtils::ComputeNormal( pl1, pl2, ng0 ) &&
		 MathUtils::ComputeNormal( s, z, nh0 ) ) {
 
		float r = radius;
 
		if( ! DoLineSegmentsIntersect( s + nh0 * r, 
		                               z + v0 * r + nh0 * r, 
		                               pl1, pl2 ) &&
		    ! DoLineSegmentsIntersect( s - nh0 * r, 
		                               z + v0 * r - nh0 * r, 
		                               pl1, pl2 ) &&
		    ! DoLineSegmentsIntersect( z + v0 * r + nh0 * r, 
		                               z + v0 * r - nh0 * r, 
		                               pl1, pl2 )) {
			//Bewegungslinie und BoundLine überschneiden sich nicht,
			//also wird keine Kollisionserkennung vorgenommen,
			//also ist myCircleCorrectDest = myCircleDest
			myCircleCorrectDest.SetPosition( z );
			return;
		}
 
		if( MathUtils::DotProduct( v, ng0 ) > 0 ) {
			//Bewegungsvektor zeigt von BoundingLine weg,
			//also wird keine Kollisionserkennung vorgenommen,
			//also ist myCircleCorrectDest = myCircleDest
			myCircleCorrectDest.SetPosition( z );
			return;
		}
 
		if( MathUtils::DotProduct( s - pl2, ng0 ) < 0 ) {
			//Der Startpunkt liegt hinter der Line
			//also wird keine Kollisionserkennung vorgenommen,
			//also ist myCircleCorrectDest = myCircleDest
			myCircleCorrectDest.SetPosition( z );
			return;
		}
 
		float d = ( MathUtils::DotProduct( z - pl2, ng0 ) );
 
		if( d >= r ) {
			//Es findet gar keine Kollision statt
			//also ist myCircleCorrectDest = myCircleDest
			myCircleCorrectDest.SetPosition( z );
			return;
		}
 
		float cosAlpha = MathUtils::DotProduct( v, pl2 - pl1 ) / 
				( MathUtils::VectorLen( v ) *  
				  MathUtils::VectorLen( pl2 - pl1 ) );
 
 
		float sinAlpha = sqrt( 1 - cosAlpha * cosAlpha );
 
		if( sinAlpha != 0 ) {
			float x = ( r - d ) / sinAlpha;
 
			sf::Vector2f z2 = z - x * v0;
			myCircleCorrectDest.SetPosition( z2 );
		}
	} else {
		//Normale konnte nicht berechnet werden, 
		//also liegen pl1 und pl2 auf einem Punkt,
		//also ist BoundingLine nicht vorhanden,
		//also ist myCircleCorrectDest = myCircleDest
		myCircleCorrectDest.SetPosition( z );
	}
}

Bewegung mit Kollisionserkennung Teil 3

Posted: 6th Februar 2011 by xaedes in Kaufhausschlacht
Kommentare deaktiviert für Bewegung mit Kollisionserkennung Teil 3

Teil 1 – Einführung
Teil 2 – Kollision mit Gerade
Teil 2 – Kollision mit Gerade – Demoprogramm
Teil 3 – Kollision mit Strecke
Teil 3 – Kollision mit Strecke – Demoprogramm

Übersicht:

  1. Problem
  2. Lösungsansatz
  3. Die Lösung
  4. Geradenschnittpunkt
  5. Parametergleichung umgekehrt
  6. Ende und Demo


Das Problem

Beim Herumspielen mit dem Demoprogramm fällt schnell auf, was wir noch beachten müssen. Die Kollision wird selbst dann berechnet, wenn die Bewegung gänzlich außerhalb der Begrenzungskante verläuft, wie hier veranschaulicht:

Dabei wäre die unkorrigierte Zielposition die korrekte. Wir müssen also entscheiden, ob eine Bewegung eine Begrenzungskante berührt oder nicht.
Dazu könnten wir einfach den Schnittpunkt S_{g,h} der Geraden g und h bestimmen und überprüfen, ob dieser innerhalb der Strecke zwischen p_{L1} und p_{L2} liegt. Wenn nicht, wird keine Kollisionserkennung durchgeführt. Allerdings würde dann folgendes passieren:

Der Schnittpunkt S_{g,h} liegt außerhalb der Strecke zwischen p_{L1} und p_{L2} und eine Kollisionserkennung würde nicht durchgeführt werden.
Allerdings findet eine Kollision statt, wie der rote Kreis verdeutlicht.

Lösungsansatz

Dadurch dass wir nicht nur eine Kollision für einen Punkt sondern für Kreise berechnen wollen, müssen wir auch die äußeren Begrenzungslinien der Bewegung daraufhin überprüfen, ob die Bewegung mit der Begrenzungskante kollidiert:

Die Punkte A_1, B_1, A_2 und B_2 spannen ein Rechteck auf, welches die Bewegung vollständig erfasst. Jetzt muss überprüft werden ob einer der Schnittpunkte S_{g,h,1} und S_{g,h,2} zwischen p_{L1} und p_{L2} liegen. Zusätzlich kann es noch einen Schnittpunkt geben, der durch die Strecke B_1 , B_2 entsteht. Für diesen muss die Überprüfung auch durchgeführt werden.
Sollte das einer der Schnittpunkte zwischen p_{L1} und p_{L2} liegen, ist eine Kollision mit der Begrenzungskante eingetreten, die erkannt und korrigiert werden muss.

Die Lösung

Zuerst müssen allerdings die Punkte A_1, B_1, A_2 und B_2 berechnet werden. Das ist relativ einfach:
  \overrightarrow{v_0} = \frac{\overrightarrow{v}}{|\overrightarrow{v}|} \\  \overrightarrow{A_1} = \overrightarrow{s} + \overrightarrow{n_{h,0}} \cdot r - \overrightarrow{v_0} \cdot r  \\  \overrightarrow{A_2} = \overrightarrow{s} - \overrightarrow{n_{h,0}} \cdot r - \overrightarrow{v_0} \cdot r  \\  \overrightarrow{B_1} = \overrightarrow{z} + \overrightarrow{n_{h,0}} \cdot r + \overrightarrow{v_0} \cdot r  \\  \overrightarrow{B_2} = \overrightarrow{z} - \overrightarrow{n_{h,0}} \cdot r + \overrightarrow{v_0} \cdot r  \\

Wie prüft man nun, ob zwei Strecken sich kreuzen? Erstmal sollte man überprüfen, ob sich die beiden Geraden die durch die beiden Strecken aufgespannt werden überschneiden. Sollte das der Fall sein kann man an Hand des Schnittpunktes, testen ob dieser innerhalb der beiden Strecken liegt.
Alle Punkte x auf einer Strecke zwischen s und e sind durch die Parametergleichung
  \overrightarrow{x} = \overrightarrow{s} + k \cdot ( \overrightarrow{e} - \overrightarrow{s} ) \\  0 \le k \le 1
bestimmt.
Haben wir den Schnittpunkt der beiden Geraden also erst einmal gefunden, müssen wir für diesen Punkt x nur noch den Parameter k für beide Strecken bestimmen. Liegen beide Parameter innerhalb des Intervals [0..1], so kreuzen sich die Strecken:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool TestBoundedMovement::DoLineSegmentsIntersect( sf::Vector2f s1, sf::Vector2f e1, 
	sf::Vector2f s2, sf::Vector2f e2 )
{
	sf::Vector2f v1 = e1 - s1;
	sf::Vector2f v2 = e2 - s2;
	sf::Vector2f intersection;
	if ( LinesIntersection( s1, v1, s2, v2, intersection ) ) {
		float k = LineParam( s1, v1, intersection );
		float m = LineParam( s2, v2, intersection );
		if( ( m >= 0 ) && ( m <= 1 ) &&
			( k >= 0 ) && ( k <= 1 ) ) {
			return true;
		} else {
			return false;
		}
	}  else 
		return false;
}


Geradenschnittpunkt

Die mathematischen Hintergründe für die Berechnung eines Geradenschnittpunktes sind hier zu finden : Schnittpunkt zweier Geraden

Daraus ergibt sich folgender Programmcode:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
bool TestBoundedMovement::LinesIntersection( sf::Vector2f s1, sf::Vector2f v1, 
	sf::Vector2f s2, sf::Vector2f v2, sf::Vector2f &intersection )
{
	if( v1.x != 0 ) {
		float a = v2.x * v1.y / v1.x - v2.y;
		if( a != 0 ) {
			float m = ( s2.y - s1.y - ( s2.x - s1.x ) * v1.y / v1.x ) / a;
			intersection.x = s2.x + m * v2.x;
			intersection.y = s2.y + m * v2.y;
			return true;
		} else {
			return false;
		}
	} else {
		if ( v2.x != 0 ) {
			float m = ( s1.x - s2.x ) / v2.x;
			intersection.x = s2.x + m * v2.x;
			intersection.y = s2.y + m * v2.y;
			return true;
		} else {
			return false;
		}
	}
}


Parametergleichung umgekehrt

Möchte man den Parameter aus der Parametergleichung eines Punktes auf einer Geraden berechnen, muss man diese nur umstellen. Auf Grund der Trivialität dieses Vorgangs lasse ich die mathematischen Hintergründe hier ganz außen vor. Folgender Quellcode ergibt sich:

1
2
3
4
5
6
7
8
9
10
float TestBoundedMovement::LineParam( sf::Vector2f s, sf::Vector2f v, sf::Vector2f p )
{
	float k = 0;
	if( v.y != 0 ) {
		k = (p.y - s.y) / v.y;
	} else if ( v.x != 0 ) {
		k = (p.x - s.x) / v.x;
	}
	return k ;
}


Ende und Demo

Nun muss nur noch die Überprüfung für die beiden Strecken eingebaut werden:

//...
if( ! DoLineSegmentsIntersect( s + nh0 * r, z + v0 * r + nh0 * r, pl1, pl2 ) &&
    ! DoLineSegmentsIntersect( s - nh0 * r, z + v0 * r - nh0 * r, pl1, pl2 ) &&
    ! DoLineSegmentsIntersect( z + v0 * r + nh0 * r, z + v0 * r - nh0 * r, pl1, pl2 )) {
	//Bewegungslinie und BoundLine überschneiden sich nicht,
	//also wird keine Kollisionserkennung vorgenommen,
	//also ist myCircleCorrectDest = myCircleDest
	myCircleCorrectDest.SetPosition( z );
	return;
}
//...

Dazu gibt es wieder ein Demonstrationsprogramm:
Demonstrationsprogramm zu diesem Teil

Teil 1 – Einführung
Teil 2 – Kollision mit Gerade
Teil 2 – Kollision mit Gerade – Demoprogramm
Teil 3 – Kollision mit Strecke
Teil 3 – Kollision mit Strecke – Demoprogramm

Zur Demonstration der bisherigen Lösung habe ich ein kleines Programm geschrieben, in welchem man sich die berechnete Lösung für beliebe Ausgangssituationen anzeigen lassen kann. Es zeigt intuitiv die Probleme, die bisher noch nicht gelöst wurden.
Screenshot:

Bedienung :
Linke Maustaste, Drag&Drop : roter und schwarzer Kreis, Enden der schwarzen Linie
Rechte Maustaste, Drag&Drop : Bildschirmausschnitt
Mausrad : Zoomen

Ausprobieren : win-04.02.2011-21.26

Relevanter Quellcodeausschnitt:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
void TestBoundedMovement::UpdateCorrectDest()
{
	sf::Vector2f s = myCircleStart.GetPosition();
	sf::Vector2f v = myVector;
	sf::Vector2f pl1 = myLineBound.GetP1();
	sf::Vector2f pl2 = myLineBound.GetP2();
 
	sf::Vector2f z = s + v;
 
	sf::Vector2f ng0;
 
	if ( MathUtils::ComputeNormal( pl1, pl2, ng0 ) ) {
 
		if( MathUtils::DotProduct( v, ng0 ) > 0 ) {
			//Bewegungsvektor zeigt von BoundingLine weg,
			//also wird keine Kollisionserkennung vorgenommen,
			//also ist myCircleCorrectDest = myCircleDest
			myCircleCorrectDest.SetPosition( z );
			return;
		}
 
		if( MathUtils::DotProduct( s - pl2, ng0 ) < 0 ) {
			//Der Startpunkt liegt hinter der Line
			//also wird keine Kollisionserkennung vorgenommen,
			//also ist myCircleCorrectDest = myCircleDest
			myCircleCorrectDest.SetPosition( z );
			return;
		}
 
 
		float r = radius;
		float d = ( MathUtils::DotProduct( z - pl2, ng0 ) );
 
		if( d >= r ) {
			//Es findet gar keine Kollision statt
			//also ist myCircleCorrectDest = myCircleDest
			myCircleCorrectDest.SetPosition( z );
			return;
		}
 
		float cosAlpha = MathUtils::DotProduct( v, pl2 - pl1 ) / 
				( MathUtils::VectorLen( v ) *  
				  MathUtils::VectorLen( pl2 - pl1 ) );
 
 
		float sinAlpha = sqrt( 1 - cosAlpha * cosAlpha );
 
		if( sinAlpha != 0 ) {
			float x = ( r - d ) / sinAlpha;
 
			sf::Vector2f z2 = z - x * v / MathUtils::VectorLen( v );
			myCircleCorrectDest.SetPosition( z2 );
		}
	} else {
		//Normale konnte nicht berechnet werden, 
		//also liegen pl1 und pl2 auf einem Punkt,
		//also ist BoundingLine nicht vorhanden,
		//also ist myCircleCorrectDest = myCircleDest
		myCircleCorrectDest.SetPosition( z );
	}
}

Bewegung mit Kollisionserkennung Teil 2

Posted: 4th Februar 2011 by xaedes in Kaufhausschlacht

Teil 1 – Einführung
Teil 2 – Kollision mit Gerade
Teil 2 – Kollision mit Gerade – Demoprogramm
Teil 3 – Kollision mit Strecke
Teil 3 – Kollision mit Strecke – Demoprogramm

Übersicht:

  1. Rechenweg
  2. Quellcode und Demo

So jetzt wissen wir was wir brauchen. Damit fangen die Berechnungen auch schon an. Zusätzlich brauchen wir aber noch den Lot von der Begrenzungslinie zu den beiden Zielpunkten z und z‘. Der Lot zu z‘ sollte eine Länge von r, also dem Radius des Figurenkreises haben, damit die Figur die Begrenzungslinie gerade so nicht überschreitet. Die Länge des Lotes zu z bezeichnen wir mit d.

Das führt uns zu folgender Skizze des zu Grunde liegenden mathematischen Problemes:

Die gepunktete Seite unter der Geraden g ist der abzugrenzende Bereich.

Nochmal eine Zusammenfassung aller Variablen:

s Startpunkt
v Bewegungsvektor
z unkorrigierter Zielpunkt
z‘ korrigierter Zielpunkt
r Radius der Figur
d Abstand des unkorrigierten Zielpunktes zur Begrenzungskante
x Abstand des unkorrigierten Zielpunktes zum korrigierten Zielpunkt
g Gerade, die von p_{L1} und p_{L2} aufgespannt wird
h Gerade, die von s und v aufgespannt wird
\alpha Winkel zwischen den Geraden g und h
n_{g} Normale zur Geraden g
n_{h} Normale zur Geraden h
p_1 Schnittpunkt des Lotes mit dem korrigierten Zielpunkt
p_2 Schnittpunkt des Lotes mit dem unkorrigierten Zielpunkt
p_{L1} Erster Endpunkt der Begrenzungskante
p_{L2} Zweiter Endpunkt der Begrenzungskante

Read the rest of this entry »

Bewegung mit Kollisionserkennung Teil 1

Posted: 4th Februar 2011 by xaedes in Kaufhausschlacht

Teil 1 – Einführung
Teil 2 – Kollision mit Gerade
Teil 2 – Kollision mit Gerade – Demoprogramm
Teil 3 – Kollision mit Strecke
Teil 3 – Kollision mit Strecke – Demoprogramm

Momentan arbeite ich daran eine sinnvolle Kollisionserkennung bei den Bewegungen zu implementieren.
Zum Berechnen einer korrekten Bewegung habe ich die Welt folgendermaßen modelliert:
Die Regale, oder später auch andere behindernde Objekte, bekommen eine BoundingBox, in die die Figuren sinnvollerweise nicht eindringen können sollten.
In folgenden Screenshots habe ich mal eine solche BoundingBox verdeutlicht und im zweiten Bild gezeigt was nicht passieren sollte.

Die BoundingBox besteht nun aus einzelnen Begrenzungskanten (Linien) und die Figur habe ich als Kreis abstrahiert:

s ist dabei die Position der Figur.
v ist der Vektor, der der gewünschten Bewegung der Figur entspricht. Er ist bestimmt durch Richtung und Länge.
p_{L1} und p_{L2} sind Endpunkte einer Begrenzungskante, welche nicht überschritten werden sollte.

Würde die Bewegung wie angefordert ausgeführt, hätten wir folgendes Ergebnis:

z ist dabei die Position der Figur nach der Bewegung (das Ziel).

Wie man unschwer erkennt hat die Figur in diesem Fall die Begrenzungskante nicht beachtet und ist an einer ungültigen Position.

Jetzt müssen wir wissen was bei einer solchen Kollision getan werden soll und wie sich die Figur verhalten soll. Es wäre zum einen möglich eine elastische Kollision mit Bewegungsreflektion, wie bei Billiardkugeln die von der Bande abprallen, zu simulieren, oder wie in diesem Kontext besser, eine unelastische Kollision. Dabei wird einfach nur soweit „gegangen“ wie möglich. Die Bewegung wird abgeschnitten und Bewegungsenergie geht dabei verloren. Steht man im Spiel z.B. neben einem Regal und versucht in die Richtung des Regals zu gehen, sollte einfach nichts passieren. Das ist das gewünschte Verhalten.
Möchte man eine solche perfekt unelastische Kollision erreichen, ist eine Platzierung wie hier veranschaulicht gesucht.
.

Gesucht ist also die korrigierte Zielposition z‘.

Wie man diese ausrechnet zeige ich im nächsten Teil.

Die Gesichter dahinter

Posted: 3rd Februar 2011 by xaedes in nebenbei
Kommentare deaktiviert für Die Gesichter dahinter

Beim Anzeichnen von simplen mathematischen Symbolen ist uns aufgefallen was dahinter steckt. Wer sich darin versteckt. Hier sind sie.

GTI Übungsblatt 13

Posted: 3rd Februar 2011 by xaedes in GTI
Kommentare deaktiviert für GTI Übungsblatt 13

Kaufhausschlacht – Update

Posted: 2nd Februar 2011 by xaedes in Kaufhausschlacht

So, mal wieder ein kleines Update.

Hähnchenkeule

Zuletzt habe ich an eine Regal gebaut. Dieses sieht man hier: win-02.02.2011-21.51

Bewegung mit den Pfeiltasten ist erstmals auch möglich.

Kaufhausschlacht – Update

Posted: 26th Januar 2011 by xaedes in Kaufhausschlacht
Kommentare deaktiviert für Kaufhausschlacht – Update

Ich habe zur Zeit viel mit Uni zu tun und daher leider nicht so viel Zeit für Kaufhausschlacht. Trotzdem gibt es jetzt mal ein kleines Update.

Aber noch viel interessanter ist eine neue Version zum Ausprobieren.

Die zweite Figur ist da schon drin und nen Cursor.

EInfach mal ausprobieren : win-26.01.2011-15.57

GAD Übungsblatt 11

Posted: 26th Januar 2011 by xaedes in GAD
Kommentare deaktiviert für GAD Übungsblatt 11