Was mir so einfällt

Bewegung mit Kollisionserkennung Teil 3 – Demonstrationsprogramm

Posted: 6th Februar 2011 by xaedes in Kaufhausschlacht

Kommentare deaktiviert

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:

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;
}

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;
		}
	}
}

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 ;
}

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

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:

Problem
Lösungsansatz
Die Lösung
Geradenschnittpunkt
Parametergleichung umgekehrt
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:

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:

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:

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

Bewegung mit Kollisionserkennung Teil 2 – Demonstrationsprogramm

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

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:

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:

Rechenweg
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.
.