[Projekt] Kollision

[starcow]

Hallo werte ZFX'ler :)

Da ich ja nun schon ein ganzes Weilchen an meinem "Kollisions-Projekt" arbeite und erste Etappenziele erreicht habe, dachte ich mir, es sei vielleicht kein schlechter Zeitpunkt, einen ersten eigenen Projekt-Thread dazu zu erstellen und euch mal die Zwischenergebnisse zu präsentieren.
Ein grosses Fernziel und Wunsch ist natürlich, dass daraus einmal ein kleines Spiel entstehen kann. Es scheint mir jedoch sinnvoll, dieses Grossprojekt erstmal auf viele kleine "Teilprojekte" runter zubrechen, um nicht im Meer der unzähligen Aufgaben zu ertrinken :). Deshalb auch der etwas unkreative Projekttitel.

Vielleicht hat ja von euch jemand auch schon Ähnliches gemacht und sieht daher Ansätze, die einfacher und eleganter sind als meine eigenen. Deshalb (und auch als (Wieder)-Herleitung für mich selbst) will ich mir jetzt besondere Mühe geben, die einzelnen Überlegungen und Rechenschritte zu dokumentieren. :-)

Ziel:
- Bewegung eines Kreises mit stark vereinfachter Physik
- Kollision an beliebigen Linien
- "Entlangsliden" bei Kollision
- Tempo soll beliebig hoch werden können (beliebig viele Bildschirmpixel)

Die ganze Bewegung des Kreises findet in zwei zentralen Schritten statt.
1) Als erstes findet die Ermittlung der Zielposition statt - noch ohne Kollisionserkennung. Bei hohem Tempo "überspringt" der Kreis also mehrere Bildschirmpixel.
2) Ist die Zielposition bekannt, wird ermittelt, ob und wo eine Kollision stattfindet.

Ich werde hier gleich auf Teil 2 eingehen, da dies auch die deutlich grössere Herausforderung für mich darstellte.
Die Kollisionserkennung muss natürlich für jede einzelne Linie berechnet werden. Meine weiteren Schritte werden demnach auch sein, eine Art "sweep and prune" (danke @ joeydee) Algorithmus einzusetzen, um Linien, die für eine mögliche Kollision sowieso klar zu weit weg liegen, schon vorab effizient auszusortieren.

Grundidee ist eine Art "Iterationsverfahren" um den Kreis an der Linie entlang "sliden" zu lassen. Auf was anderes, respektiv etwas "direktes" bin ich auch nach längerem Nachdenken nicht gekommen. Es scheint mir prinzipiell unmöglich zu sein, das ganze quasi algebraisch auf einen Schlag zu entscheiden - lasse mich aber natürlich gerne eines besseren belehren. :-)

Ich habe ein paar gifs dazu erstellt, weil man so den Überlegungen wohl am einfachsten folgen kann.

Ansatz ist folgender:


Das eigentliche Ziel in diesen Berechnungen war, ein Skalar-Wert für den Vektor circle.target zu bekommen. Dieser Skalar-Wert als Faktor drückt aus, nach welchem Streckenteil der grüne Kollisionspunkt exakt berührt wird. Zudem soll die Kollisionsmethode noch einen "Refraktions-Vektor" zurückgeben, der angibt, in welche Richtung sich der Kreis nach Erreichen des Kollisionspunktes weiter bewegen muss.

Der tatsächliche Kollisionspunkt kann natürlich auch ein "Eckpunkt" der Linie sein. Es scheint mir, als gäbe es daher auch keinen direkteren Weg (also über den Berechnungsschritt des grünen Kollisionspunktes) um auf den roten "Breaking-Point" zu kommen.

Die Linie selbst besteht aus einem Ortsvektor und einem Zielvektor (also quasi einem Offset zum ersten Eckpunkt).
Die Idee ist nun, zuerst den "Schein-Kollisionspunkt" zu berechnen. Also der Kollisionspunkt bei einer unendlich langen Geraden. Dabei geht es erstmal gar nicht um die tatsächlichen Koordinaten des Kollisionspunktes, sondern um den Vorfaktor für den Linien-Target-Vektor (Skalar), an deren Stelle quasi der Kollisionspunkt auf der Strecke liegt. Weil hat man diesen Faktor, lässt sich sehr einfach sagen, ob die (mögliche) Kollision auf der Linie oder einem Eckpunkt stattfinden würde.

Um also den grünen Schein-Kollisionspunkt zu berechnen, respektive den skalaren Vorfaktor, muss man erst den Schnittpunkt der beiden Geraden bestimmen (ebenfalls als skalarer Vorfaktor für den Linien-Ziel-Vektor). Auf einen anderen Weg, ohne den Linienschnittpunkt, bin ich auch nach längerem Nachdenken nicht gekommen. Dies geht aber ja Dank des Hinweises von joeydee super einfach! :-)

Habe ich nun diesen Skalar, ist die Ermittlung des tatsächlichen Kollisionspunktes (mit Berücksichtung der endlichen Ausdehnung der Linie) denkbar einfach.
=> liegt der Wert zwischen 0 und 1, liegt der Kollisionspunkt auf der Linie
=> ist der Wert kleiner als 0, ist der Kollisionspunkt der Ortsvektor der Linie (Anfangspunkt)
=> ist der Wert grösser als 1, ist der Kollisionspunkt der Endpunkt der Linie

Code: Alles auswählen

scale = std::min(std::max(scale, 0.0), 1.0);

Berechnung des grünen Kollisionspunktes oder Vorfaktor als Skalar



Hat man nun den tatsächlichen Kollisionspunkt ermittelt, lässt sich auch der "Breaking-Point" (rot) berechnen.



Hierbei prüfe ich vorher noch, ob der Vektor hin zum Kollisionspunkt und der Bewegungsvektor circle.target nicht weiter als 90 grad auseinander liegen (Skalarprodukt > 0.0). Wäre dies der Fall, kann sowieso eine Kollision unmöglich stattfinden und Streckenlängen könnten dann aufgrund des Skalarproduktes negativ werden. Eleganter wäre natürlich ein Weg ohne diese IF-Bedingung. Ich konnte jedoch bis jetzt keine finden.

Damit man das ganze auch mal in Bewegung sehen kann, hab ich noch ein kurzes Video erstellt. Youtube vermiest allerdings die Qualität leider so stark, dass sich die Linien kaum noch erkennen lassen. Deshalb habe ich das Video auf meinen eigenen Webspace hochgeladen.

Was noch gesagt werden muss: Wenn die Linie genau parallel oder rechtwinklig zum Bewegungsvektor des Kreises liegt, tritt ein Spezialfall ein, den ich noch implementieren muss. Das scheint mir aber relativ gut machbar zu sein - ohne grosses "Ausnahme-Gewürge"

Wie gesagt, bin ich sehr an eurer Meinung und Einschätzung interessiert. Ich kann jetzt nicht wirklich einschätzen, ob das für eine "an-der-Wand-sliding-Methode" schon ziemlich aufwändig ist. Es war mir halt wichtig, dass es mit beliebigen Tempo und mit jeder Art von Linie funktioniert.

Eine andere offene Frage ist, ob es durch Rundungsfehler möglich werden kann, sich quasi durch die Wand hindurch zu buggen, wenn man über sehr lange Zeiträume dagegen steuert. Ich arbeite zwar grundsätzlich mit double, aber es übersteigt meine Kenntnisse in Informatik, ob sich in diesen Berechnungen kleinste Ungenauigkeiten hochsummieren oder ob sich die gegenseitig wieder "ausebnen".

Gruss starcow

[Jonathan]

Wie gesagt, bin ich sehr an eurer Meinung und Einschätzung interessiert. Ich kann jetzt nicht wirklich einschätzen, ob das für eine "an-der-Wand-sliding-Methode" schon ziemlich aufwändig ist. Es war mir halt wichtig, dass es mit beliebigen Tempo und mit jeder Art von Linie funktioniert.

Eine andere offene Frage ist, ob es durch Rundungsfehler möglich werden kann, sich quasi durch die Wand hindurch zu buggen, wenn man über sehr lange Zeiträume dagegen steuert. Ich arbeite zwar grundsätzlich mit double, aber es übersteigt meine Kenntnisse in Informatik, ob sich in diesen Berechnungen kleinste Ungenauigkeiten hochsummieren oder ob sich die gegenseitig wieder "ausebnen".

Ich finde, das hört sich alles ziemlich solide an. Die Berechnungen sind insgesamt ja nicht sonderlich zeitaufwändig, ich würde mir deshalb erstmal keine weitere Gedanken machen, ob das jetzt schon zu komplex ist. Spannender wird es, wenn du später mal 10.000 Linien hast, aber da macht man dann eben Vortests auf einer höheren Ebene, wie du ja auch schon geschrieben hast. Das sollte also so passen.

Zu dem zweiten Problem: Ich habe ja jetzt nicht den ganzen Algorithmus gesehen, aber deine Beschreibung klingt eigentlich ganz robust. Die Frage ist vielleicht, was passiert, wenn der Kreis sich an der Wand entlang bewegt und dabei vielleicht am Ende ein bisschen in der Wand steckt. Aber ich vermute, dass in diesem Fall dein Algorithmus einen Kollisionspunkt finden würde, der den Kreis dann wieder etwas weiter von der Wand wegschiebt. Solange das Ziel vom Algorithmus ist, nach jedem Durchlaufen eine gültige Kreisposition zu liefern sehe ich so spontan nicht, wie sich da Fehler aufaddieren könnten.

[starcow]

Hey Jonathan
Vielen Dank für deine Antwort! :-)

Tatsächlich ist es so, dass der Kreis aufgrund von Rundungsfehler absolut minimal in der Wand "steckt", sobald man an dieser "entlangslidet".
Ich habe jetzt eine kleine Berechnung eingefügt, die die genaue Zahl ausgibt, um wie viel sich der Kreis in der Wand befindet.
Das sind während des Slidens Werte zwischen 1.0e-13 und 1.0e-12. Die Zahl scheint aber nicht grösser zu werden.
Meine Hypothese ist, dass sich die Rundungsfehler bei mehreren Iterationen in der Summe wieder ausgleichen - weil der "Slide-Vektor" auch mal minimalst von der Wand wegzeigt.
Was man tun könnte, um die Ungenauigkeiten quasi aktiv zu korrigieren - dazu hab ich lediglich erste Ansätze. Denn tatsächlich ist es so, dass der Algorithmus nicht zwingend eine valide Position ausspuckt. Der Algorithmus lenkt lediglich den Kreis um. Befindet sich der Kreis bereits in der Linie drin, unternimmt der Algorithmus dagegen nichts.
Ich meine, ich kann feststellen, ob sich der Kreis in einer Linie befindet - klar... Aber was dann? Schiebe ich den Kreis einfach entlang der Wand-Normalen heraus, kann es theoretisch passieren, dass ich ihn mit dieser Korrektur-Bewegung wieder in eine andere Linie hineinschiebe.
Das Problem scheint mir nicht ganz trivial zu sein.

Die Frage ist halt, wie weit es sinnvoll ist, dass ich mich jetzt diesem theoretischen Problem annehme. Es ist grundsätzlich nicht meine Art, solche Dinge einfach unbeantwortet zu lassen. Aber als Perfektionist habe ich auch immer wieder mal die Situation, dass ich mich mit eher Unwesentlichem zu lange aufhalte. :-)

Gruss starcow

[Jonathan]

Hm, mal sehen (frei improvisiert): Ich glaube man kann das schon relativ einfach ziemlich robust lösen. Angenommen, deine Startposition ist gültig und du bewegst deinen Kreis. Dann kannst du potentiell mit mehreren Linien kollidieren. Wenn du nicht direkt die Kollision behandelst sondern erst prüfst, mit welcher Linie du als erstes kollidieren würdest (sollte ja leicht gehen), dann weißt du, dass von der aktuellen Position bis zum Kollisionspunkt mit eben dieser Linie jede Position gültig sein muss. Anstatt den Kreis direkt an die Linie zu setzen, addierst du einen kleinen Offset - wenn deine Szene im Meter-Maßstab ist, merkt keiner, wenn ein Objekt einen halben Millimeter vor der Wand stehen bleibt. Du würdest also z.b. nur bis 1e-4 gehen, so dass du immer im Bereich bist, wo deine Fließkommazahlen noch ausreichend genau sind. Du willst jedenfalls sicherstellen, dass die übliben Matheregeln noch gelten.
Wenn du jetzt vor der Wand stoppst und das "an der Wand gleiten" als eigene Bewegung implementierst (du also wieder ganz vorne bei der Kollisionsbehandlung anfängst), dann dürfte es quasi garantiert sein, dass du dich immer an gültigen Positionen befindest.

Ansonsten könnte es interessant sein sich anzusehen, wie gängige Physiksimulationen dieses Problem lösen. In komplexeren Situationen können anderen Algorithmen vorteilhafter sein, ich glaube in einigen Fällen werden derlei Constraint-Verletzungen (z.B. zwei Objekte stecken ineinander) durch hinzufügen von Kräften gelöst. Das würde zumindest erklären, weshalb manchmal verkantete Objekte anfangen zu zittern, bis der ganze Stapel dann explodiert und alles durcheinander fliegt. Wirklich beschäftigt habe ich mich damit aber auch noch nicht.

[starcow]

Wirklich sehr interessante Idee! :-)
Ich hab das jetzt mal so umgesetzt und es funktioniert wirklich sehr gut (Freunde herrscht! :-D)! Vielen Dank!
Der Abstand zur Linie bleibt immer positiv und selbst mit einem extrem flachen Winkel über Minuten des Slidens, ist es mir nicht gelungen, dass sich eine immer kleiner werdende Abstands-Tendez eingestellt hätte.
Ich werde jetzt noch die zwei Sonderfälle "Parallel" und "Rechtwinklig" implementieren und mich dann mal an den Vorselektions-Algorithmus wagen :-)

Gruss starcow

[Jonathan]

Aus Interesse: Könntest du den relevanten Code mal posten, wenn er fertig ist?

[starcow]

Klar! Ich werde heute noch daran arbeiten und dann den Code hier posten!

Gruss starcow

[starcow]

Nachdem ich gestern nochmals eine ganze Weile dran gesessen - und das ganz noch etwas optimiert und vereinfacht habe, funktioniert es jetzt wirklich sehr sauber und zuverlässig. Ich konnte jeden Falls kein unerwünschtes Verhalten feststellen - und alle speziellen Situationen sollten nun ebenfalls abgedeckt sein.

Wenn du dir schon die Mühe machst und einen Blick auf den Code wirfst, können ein paar Erläuterungen von meiner Seite sicher nicht schaden.

Das ganze funktioniert grundsätzlich über das Zusammenspiel zwischen zwei Funktionen.
Die Methode "Collision" der Klasse "Character" steuert quasi die einzelnen Iterations-Schritte, indem es die eigentliche(n) Kollisions-Funktionen mit den neuen Refraktions-Vektoren erneut aufruft.
Bis jetzt ist da erst eine Methode drin: Kreis gegen Linie.

Die eigentliche Kollisionsmethode (Kollisions-"Modul") nimmt dann ein Kreis-Objekt entgegen und gibt daraufhin ein sogenanntes Refrakt-Objekt zurück. Dieses enthält einerseits einen Scalaren-Wert, wie weit sich der Kreis in seiner angegebenen Zielrichtung bewegen darf - und andererseits, wie er danach gegebenenfalls abgelenkt wird.
Die Iterationsschritte (for-Schlaufe) sind auf drei beschränkt. Damit funktioniert das "Sliding" in jeder Situation und es wird nicht unnötig lange gerechnet, falls sich der Kreis z. B. in einen Spitzen Winkel manövriert hat.
Sinnvoll ist noch zu erwähnen, dass die Länge des Refraktions-Vektors mit dem ursprünglichen Zielvektor des Kreises verrechnet wird. Das macht mehr Sinn, als den ehemaligen Iterations-Vektor zu nehmen. Damit wird ein hin- und her "Zittern" in bestimmten Winkeln verhindert und es entspricht auch mehr den "Bewegungs-Erwartungen".
"scalar" ist einfach ein double, denn ich für die verschiedenen Berechnungen verwende - und "vector" wäre auf der Grafik weiter oben der hellblaue Offset-Vektor.

Der Kern des Codes umfasst jetzt ca. 90 Zeilen. Finde das doch sehr erfreulich - hätte eigentlich deutlich mehr erwartet.

Code: Alles auswählen

		for (int i = 0; !circle.iteration.Null() && i < 3; ++i) {
			/* Wände */
			compare = Engine->Collision->Line(circle);
			if (compare.scale < collision.scale) {
				collision = compare;
			}
			
			/* circle aktualisieren */
			circle.position += circle.iteration * collision.scale;
			circle.iteration = collision.refract;
			
			/* "circle.target" auf selbe Länge wie "collision.refract" bringen */
			circle.target = circle.target.UnitV() * collision.refract.Norm();
			
			/* "collision" resetten */
			collision.scale = 1.0;
			collision.refract.x = 0.0;
			collision.refract.y = 0.0;
		}

Code: Alles auswählen

	STR_COLLISION_Refract CLS_Collision::Line(STR_COLLISION_Circle circle) {
		STR_COLLISION_Refract collision;
		collision.scale = 1.0;

		STR_COLLISION_Refract compare;
		compare.scale = 1.0;

		STR_Line line;

		CLS_Vector2d blau;
		CLS_Vector2d gruen;
		CLS_Vector2d rot;
		CLS_Vector2d vector;

		double scalar = 0.0;
		
		/* Sollte "circle.iteration" ein Nullvektor sein, wird die Schlaufe nicht ausgeführt */
		for (unsigned int i = 0; !circle.iteration.Null() && i < Engine->Area.index_VEC.size(); ++i) {
			/* 1. "compare", "blau", "gruen" und "rot" zurücksetzen */
			compare.refract *= 0;
			compare.scale = 1.0;
			
			blau = circle.position;
			gruen = circle.position;
			rot = circle.position;

			/* 2. Linie aus "Area" holen */
			line.position = Engine->Area.vertex_VEC.at(Engine->Area.index_VEC.at(i).begin);
			line.target = Engine->Area.vertex_VEC.at(Engine->Area.index_VEC.at(i).end);

			/* 3. "line.target" wird zu einem Offset zu "line.position" */
			line.target -= line.position;

			/* 4. gruener - und gebenenfalls blauer Punkt bestimmen */
			if (line.target.Null()) {
				/* Wand-Linie ist nur ein Punkt */
				gruen = line.position;
			}
			else if (circle.iteration.DotP(line.target.Normal())) {
				/* 4.1. blauer Punkt berechnen - Schnittpunkt Circle-Linie und Wand-Linie */
				calculateBlue();
				/* 4.2. grüner Punkt berechnen - Kollisionspunkt an Linie */
				calculateGreen();
			}
			else {
				/* grüner Punkt bei Parallelität bestimmen */
				calculateParallel();
			}

			/* 5. "vector" berechnen - Offset von "circle.position" zu Kollisionspunkt "gruen" */
			vector = gruen - circle.position;

			/* 6. Falls möglich, roter Punkt und "compare" bestimmen */
			if (vector.DotP(circle.iteration) > 0.0) {
				scalar = abs(vector.DotP(circle.iteration.Normal().UnitV()));

				if (circle.size > scalar) {
					scalar = abs(vector.DotP(circle.iteration.UnitV())) - sqrt(pow(circle.size, 2.0) - pow(scalar, 2.0));
					scalar /= circle.iteration.Norm();
					rot = circle.position + (circle.iteration * scalar);
					scalar = std::trunc(scalar * 10000) * 0.0001;

					if (scalar <= 1.0 && scalar >= 0.0) {
						compare.scale = scalar - 0.0001;
						compare.scale = std::max(compare.scale, 0.0);
						compare.refract = (gruen - rot).Normal().UnitV();
						compare.refract *= circle.target.DotP(compare.refract) * (1.0 - compare.scale);
					}
				}
			}

			/* 7. Scale-Werte von compare und collision vergleichen und gegebenfalls zuweisen */
			if (compare.scale < collision.scale) {
				collision = compare;
			}

			/* 8. Linienabstand Kontrolle (temporär) */
			scalar = line.target.Intersect((circle.position - line.position), line.target.Normal());
			if (isnan(scalar)) {scalar = 0.0;}
			scalar = std::min(std::max(scalar, 0.0), 1.0);
			scalar = ((line.position + (line.target * scalar)) - circle.position).Norm() - circle.size;
			//std::cout << "Abstand: " << scalar << std::endl;
		}

		/* 9. Visualisierung der Punkte (temporär) */
		Engine->rCircle3.position = rot;
		Engine->rCircle1.position = blau;
		Engine->rCircle2.position = gruen;

		return(collision);
	}

Als nächstes werde ich die Kreis-Kreis Kollision implementieren und mich dann daran wagen, dass ganze über eine Art "sweep & prune" Funktion effizient Vorzuentscheiden. :-)

Gruss starcow

[Jonathan]

Ok, ich habe mal kurz drüber geschaut. Ich muss gestehen, der Code verwirrt mich ein wenig, auch wegen diesen komischen farbigen Vektoren. Aber insgesamt war ich vor allen Dingen neugierig, wie du die verschiedenen Fälle implementiert hast. Großartige Kommentare habe ich jetzt nicht, aber es ist ja schon ein ganz gutes Zeichen wenn der Code kompakt ist (ohne komprimiert zu wirken). (Gerade bei Fallunterscheidungen kann es halt leicht passieren, dass man gemeinsame Dinge mehrfach implementiert, und sowas ist immer eine beliebte Quelle für Fehler.)

Nunja, viel Spaß noch mit deinen robusten Kollisionsabfragen :) Schöne Arbeit.

[starcow]

Nochmals Danke fürs Feedback Jonathan :-)
Ich kann mir gut Vorstellen, dass es nicht ganz einfach sein dürfte, die Mathematik dahinter so aus dem Stegreif nachzuvollziehen.
Die farbigen Vektoren (blau, grün, rot) sind einfach die Punkte, wie sie in der ersten Darstellung zu sehen sind.
Blau der Schnittpunkt der Linien, grün der Kollisionspunkt und rot der Stopp-Punkt.

Ich habe jetzt noch die Kreis-Kreis Kollision implementiert. Ein sehr ähnlicher Aufbau, nur ein gutes Stück einfacher und kürzer. :)
Als nächstes werde ich nun versuchen, eine Art "sweep & prune" Vorselektions-Algorithmus mit einzubauen.

Gruss starcow

[starcow]

Kleines Update:
Ich hab jetzt erstmal ein simples Testlevel erstellt, um das ganze mal in Aktion zu sehen - und um einen Vergleichswert Punkto Performance zu erhalten, wenn ich dann den "sweep & prune"-Algorithmus implementiert habe. In der Debug-Version liegt die durchschnittliche Schlaufenzeit (ohne das SDL Rendering) bei knapp 3 ms. In der Release Variante sinds blos 0.2 ms, also rund 5000fps :-). Dabei werden 14 Kreise (sofern sie sich denn bewegen) auf 28 Linien - und auf die jeweils verbleibenden anderen 13 Kreise getestet.

Ideal wäre es natürlich, wenn das ganze später mit rund 10'000 Linien und 1000 Kreise noch mit einer annehmbaren Geschwindigkeit laufen würde.
Ich kann allerdings nicht wirklich einschätzen, was der "sweep & prune"-Algorithmus so rausreisen kann.



Ein kleines Video gibts wieder hier:



Gruss starcow

Edit:
Weil ja thematisch zusammen gehört, trage ich noch die Bilder hier rein, die sich noch in anderen Threads befinden...


(Beispielgrafik)


(Grafikstudie)


(Grafikstudie)


(Grafikstudie)


(gerenderte Grafikstudie)