Warum glitcht meine Kollisionsbehandlung

Design Patterns, Erklärungen zu Algorithmen, Optimierung, Softwarearchitektur
Forumsregeln
Wenn das Problem mit einer Programmiersprache direkt zusammenhängt, bitte HIER posten.
Antworten
Benutzeravatar
Hannes
Beiträge: 14
Registriert: 11.06.2008, 06:04

Warum glitcht meine Kollisionsbehandlung

Beitrag von Hannes »

Hallo Zfxler,

ich sitze momentan an der Kollisionsbehandlung für meinen First Person Shooter.
Das Spiel orientiert sich an Doom. Spieler und NPCs sind Sprites. Sie bewegen sich auf einer 2D Ebenen und können untereinander sowie mit Wänden Kollidieren. Alle beweglichen Objekte sind Kreise. Und unbewegliche Wände sind Linien. Zum testen bilde ich erstmal alles in 2D, aus der Vogelperspektive, ab.
testscene1.png
Weiß sind die Spielobjekte und blau sind die Wände. Das Ziel ist, dass die sich bewegenden Kreise, an anderen Kreisen und an Wänden, ausweichend daran sliden, wenn es zu einer Kollision kommen würde.

Wie ich mir die Kollision denke
Bis jetzt, führe ich die Kollisionserkennung und Schnittpunktberechnung auf Linie-Line und Linie-Kreis Tests zurück. Das heißt, Kreisobjekte betrachte ich als Punkt, der den Radiusabstand zu anderen Objekten einhalten soll. Ich erzeuge Hilfslinien und Hilfskreise die den Radiusabstand haben. Eine Kollision tritt auf, wenn die Bewegungslinie, bestehend aus alter Kreismittelpunkt, neue Zielposition, eine Hilfslinie/Hilfskreis schneidet.
testscene2.png
Die gelben Linien sind Parallelen zu den Wandlinien, die den Spielerradius als Abstand haben. Die gelben Kreise an den Wandlinien sollen von dem Spielermittelpunkten nicht überschritten werden. Der kleine Weiße Kreis ist der Spieler. Die gelben Kreise an den Kreisobjekten haben einen Abstand von eigenem Radius + Spielerradius. Jedes Kreisobjekt hat seine eigenen Hilfsabstandlinien, weil sie unterschiedliche Radien haben. Im Bild sind nur die Hilfslinien vom Spielerkreis zu sehen.

Wie die Objekte bewegt werden
In der Update Methode bewege ich alle Kreisobjekte nacheinander. Will sich ein Kreisobjekt vorwärts bewegen, Teste ich zuerst ob eine Kollision auftritt. Wenn keine Kollision auftritt wird das Kreisobjekt auf die neue Position gesetzt. Wenn eine Kollision auftritt wird ein Distanzpunkt berechnet, der kurz vor dem Schnittpunkt liegt und nochmal getestet ob eine Kollision zu diesen Distanzpunkt auftritt. Tritt eine Kollision auf, wird abgebrochen und nicht bewegt. Tritt keine auf, wird eine Ausfallrichtung, vom Distanzpunkt, berechnet (bei Linien parallel zu ihr, bei Kreisen in Richtung Schnittpunkt-Tangente) und getestet ob es dahin kann.

Das Problem
Manchmal, wenn die Kreise sich gegenseitig an der Wand entlang schieben glitchen die Kreise ineinander. Wie auf dem Bild in der oberen rechten Ecke.
glitch.png
Zum Schluss die Frage
Übersehe ich etwas? Kann man das so machen? Ich weiß nicht wie das glitchen zustande kommt. Die meiste Zeit funktioniert dieser Algorhitmus, aber ebend manchmal auch nicht. Vielleicht kennt jemand auch einen besseren Ansatz?

Ganz zum Schluss hänge ich noch die Testscene an. Das Programm ist in Lua mit Hilfe des LÖVE Frameworks geschrieben
Demo.zip
(3.6 MiB) 19-mal heruntergeladen
Man ist der Kleine Kreis und man dreht sich immer zur Mausposition. Mit der Linken Maustaste bewegt man sich in Richtung Mauscursor.

Ich hoffe man kann meiner Beschreibung folgen.

Hannes
Benutzeravatar
marcgfx
Establishment
Beiträge: 1569
Registriert: 18.10.2010, 23:26

Re: Warum glitcht meine Kollisionsbehandlung

Beitrag von marcgfx »

Bin schon etwas müde aber bei Devader hatte ich das Problem auch. Es lag bei mir am korrigieren. Meine Lösung war die Korrektur nicht direkt zu machen, sondern einen Abstossvektor in den nächsten Frame zu übernehmen. Weiss nicht mehr ob ich den einfach dazuaddiert habe, oder als Bewegungsvektor verwendet hab. Wichtig war aber das alle Objekte dadurch gleich/parallel behandelt wurden und nicht sequenziell.
Benutzeravatar
Jonathan
Establishment
Beiträge: 1444
Registriert: 04.08.2004, 20:06

Re: Warum glitcht meine Kollisionsbehandlung

Beitrag von Jonathan »

Hannes hat geschrieben:
15.09.2020, 01:40
Das Problem
Manchmal, wenn die Kreise sich gegenseitig an der Wand entlang schieben glitchen die Kreise ineinander. Wie auf dem Bild in der oberen rechten Ecke.
Es ist nützlich sich ins Gedächtnis zu rufen, welche Teile der Kollisionsbehandlung welche Garantien haben.
Zunächst einmal ist das Gesamtproblem (komplexe Szene in der sich Objekte bewegen) so nicht lösbar, weswegen man es in Teilprobleme zerlegt. Es gibt Kreis-Kreis und Kreis-Linie Tests die garantiert erkennen, ob eine Kollision auftritt oder nicht. Des Weiteren kannst du auch berechnen, wie weit du einen Kreis bewegen darfst damit gerade so keine Kollision mit einer einzelnen Linie oder einem einzelnen anderen Kreis auftritt. Du kannst also nur sehr spezielle Teilprobleme schnell und garantiert richtig lösen, das Gesamtproblem wird nur numerisch approximiert und das bringt halt Probleme mit sich.

Du kannst das Ineinanderstecken von Kreisen vermeiden, wenn du immer nur Operationen durchführst, bei denen garantiert ist, dass es danach keine Kollision gibt, wenn es vor der Operation keine Kollision gab. Sprich, jedesmal wenn du einen Kreis bewegst muss du auf Kollision prüfen. Wenn du einen Gleit-Vektor parallel zur Hand berechnest und entlang diesen den Kreis bewegst, muss du wieder auf Kollision prüfen. Wenn du das systematisch machst, ist die Kollisionsbehandlung ggf. langsamer, aber Probleme wie das Beschriebene können nicht mehr vorkommen.

Ein alternativer Ansatz ist es, zunächst alle Objekte so zu bewegen, wie sie es tun würden wenn es keine Kollision gäbe. Danach stecken Objekte vermutlich ineinander, aber du kannst versuchen sie entlang der Normalen des Berührpunktes wieder auseinander zu schieben, bis es keine Kollision mehr gibt. Das kann mehrere Iterationen benötigen, da Objekte dadurch wieder in anderen Stecken bleiben können.
Bei diesem Verfahren gibt es glaube ich keine Garantie, dass du irgendwann fertig bist, man könnte vermutlich ungünstige Szenarien konstruieren, in denen unendlich viele Iterationen benötigt werden. Praktisch sollte das aber kaum auftreten, insbesondere wenn du die Simulationsiterationen an die Geschwindigkeitsvektoren anpasst. Für sehr schnelle Objekte würdest du also kleinere Zeitschritte benutzen, so dass objekte nicht so sehr ineinander feststecken.

Vielleicht ist die zweite Variante insofern fairer, als das Objekte gleicher behandelt werden (wie es marcgfx angesprochen hat). Bei der ersten wird zunächst versucht, das erste Objekt so weit und gut wie möglich zu bewegen, danach ist es quasi steif. Aber auch das kann man umgehen, indem man z.B. die Gesamtbewegung in 5 Teile aufteilt und jedes Objekt 5 mal ein bisschen bewegt wird. Du musst dann halt testen, ob du das Problem der Ungleichbehandlung in der Praxis hast und wie teuer deine Kollisionsbehandlung insgesamt ist.
Lieber dumm fragen, als dumm bleiben!
Benutzeravatar
starcow
Establishment
Beiträge: 324
Registriert: 23.04.2003, 17:42

Re: Warum glitcht meine Kollisionsbehandlung

Beitrag von starcow »

Hi Hannes

Ich mache was sehr ähnliches und setzte mich nun schon seit einiger Zeit mit solchen Fragen auseinander. Ich hatte auch sehr viel Zeit darin investiert, Lösungen zu suchen und "Fehler-Quellen" ausfindig zu machen. Geklappt hat es erst, als ich das Problem ganzheitlich neu angegangen bin. Solche Probleme sind mir also bestens vertraut.
Da ich deinen Code nicht kenne, kann ich nur Vermutungen anstellen. Aber wenn du ähnlich vorgegangen bist wie ich damals, dann entstehen deine Glichtes durch Rundungsungenauigkeiten. Denn du wirst _nie_ ein Objekt vor der Kollision mit 100% Sicherheit verlässlich stoppen können - und damit verhindern, dass es sich mit einem anderen überschneidet. Auch wenn die Überschneidung nur ganz minim ist und selten auftritt - sie kann nicht ausgeschlossen werden.
Der vermeindlich naheliegende Lösungsansatz für dieses Problem scheint dann das Einführen von Toleranzen zu sein. Nur leider ist dies ein Trugschluss. Es hat mich einige Zeit gekostet diesen aufzudecken - doch der Grund dafür, dass sowas prinzipbedingt nicht funktionieren kann, liegt im 2D-Raum selbst.

Schau dir mal folgende Grafik an
Bild
Grün makiert die Stop-Position. Rot die hinzugefügte Toleranz.

Das Problem ist, dass wenn du dich in einem sehr flachen Winkel zur Wand (oder einem anderen Objekt) bewegst, du immer der Wand beliebig nahe kommen kannst - ganz egal wie gross deine Toleranzen auch sein mögen. Und irgendwann ist der Abstand so klein, dass eine Rundungsungenauigkeit dir dein Kreis ins andere Objekt hineinsetzt.
Und wenn ich raten müsste, würde ich jetzt sagen, dass deine Glitches dadurch zustande kommen, dass wenn ein Objekt mal in einem anderen drin Steck, dein Algorithmus jenes von den weiteren Berechnungen einfach ausschliesst.

Mein entwickelter Ansatz ist folgender: Du bewegst deine Objekte an die berechnete Stop-Position - ganz ohne Toleranz.
Du prüfst nun aber als erstes, ob dein Kreis genug nah an einem anderen Objekt dran ist. Ist z.B. dein Kreis nur 0.01 von einem anderen Objekt entfernt, glit das bereits als "berühren". Und sollte ein Objekt ein anderes berühren, dann konstruierst du eine Bande.
Der grosse Vorteil dabei ist, dass die Distanz auch negativ sein kann. Wenn also dein Objekt aufgrund einer Rundungsungenauigkeit die Distanz von -0.000001 zu einem anderen hat, dann wird ebenfalls, geometrisch korrekt eine Bande gespannt. Da die Rundungsungenauigkeiten sich statistisch wieder "aufheben", spielt es auch absolut keine Rolle, wenn du über einzelne (sehr seltene) Frames um den Betrag von 0.00001 eigentlich in der Wand gesteck hättest. Nur das korrekte Ablenken spielt dabei eine Rolle.

Dieser Ansatz kostet aber etwas mehr Performance, als einfach die Position zu korrigieren. Die meisten begnügen sich wohl mit letzterem.

Gruss starcow
Freelancer 3D- und 2D-Grafik
mischaschaub.com
Benutzeravatar
Jonathan
Establishment
Beiträge: 1444
Registriert: 04.08.2004, 20:06

Re: Warum glitcht meine Kollisionsbehandlung

Beitrag von Jonathan »

Was meinst du mit 'eine Bande konstruieren'? Und was ist die Konsequenz daraus, wie wird diese Bande dann anschließen benutzt? An der Stelle bin ich nicht mehr so ganz mitgekommen...

Ich finde aber die Bemerkung mit den Fließkommaungenauigkeiten sehr wichtig. Auch wenn ein analytischer Algorithmus vielleicht garantiert, dass keine Kollision möglich ist, gilt das vielleicht nur wenn man mit reellen Zahlen rechnet, nicht aber für diskretisierte Fließkommazahlen. Da muss man also sehr vorsichtig sein.
starcow hat geschrieben:
16.09.2020, 13:30

Schau dir mal folgende Grafik an
Bild
Grün makiert die Stop-Position. Rot die hinzugefügte Toleranz.
Ok, aber was wäre wenn man nicht die Bewegungslinie um ein festes Stück kürzer macht, sondern stattdessen die Wand um ein festes Epsilon virtuell in richtung der Kugel bewegt und dann genau so weit geht, dass keine Kollision stattfindet. Dann hättest du am Ende - abgesehen von numerischen Ungenauigkeiten - immer die selbe kleine Entfernung zur Wand, unabhängig vom Bewegungswinkel.
Lieber dumm fragen, als dumm bleiben!
Benutzeravatar
starcow
Establishment
Beiträge: 324
Registriert: 23.04.2003, 17:42

Re: Warum glitcht meine Kollisionsbehandlung

Beitrag von starcow »

Ja, das war wohl etwas zu lapidar ausgedrückt.
Ich habe jetzt deinen Ansatz nicht konsequent durchgedacht, aber gut möglich, dass das auf das selbe hinausläuft - einfach von der anderen Seite her gedacht.

Was ich mit Bande meinte war folgendes:
Bild

1) Man sucht als erstes den nächsten Punkt der einzelnen "Wandlinie".
Das geht sehr schön und einfach, wenn man zuerst den Skalierungsfaktor für den hypothetisch nächsten Punk (gelb) zur Gerade sucht und diesen Faktor anschliessend begrenzt clamp(vector_scale, 0.0, 1.0)
So hat man auch immer schön die Eckpunkte abgedeckt.
Es spielt bei dieser Methode auch überhaupt keine Rolle, ob man mit der Linie oder einem Eckpunkt kollidiert. Das Prinzip funktioniert ohne Ausnahme.

2) Hat man den nächsten Punkt zur Linie bestimmt, berechnet man die Distanz.
Das tolle daran ist, das man die Distanz ohnehin sehr gut brauchen kann: Als zweites Vorselektionskriterium (nach dem "spatial hashing" - oder was auch immer man für die erste Vorselektion verwenden möchte).
Denn wenn: Distanz >= Länge_des_Bewegungsvektors + Kreisradius, dann kann auch garantiert keine Kollision mit dieser Linie stattfinden.

3) Nun schaut man sich an, ob die Distanz zum nächsten Punkt (dabei spielt es keine Rolle, ob das eine Wand oder eine Figur ist) den Toleranzbereich unterschreitet. Sollte dies der Fall sein, konstruiert man die Bande, das ist die Normale vom grünen Vektor. Und an dieser Bande lenkt man dann quasi die Bewegung ab. Das geht sehr einfach mit dem Skalarprodukt.

Vielleicht sprengt das jetzt ein bisschen den Rahmen. Ich kann es auch gern genauer ausführen, falls Interesse daran besteht.
Ich empfehle, erst alle "Punkte" zu sammeln, die den Toleranzbereich unterschreiten. Auf diese Art kann man dann sehr schnell entscheiden, ob eine Bewegung resp. Ablenkung überhaupt möglich ist oder ob der Kreis in einer Ecke steckt.
Denn wenn der Bewegungsvektor zwischen zwei grünen Vektoren liegt, ist dies der Fall - und der Kreis muss erst gar nicht mehr bewegt werden.

Gruss starcow
Freelancer 3D- und 2D-Grafik
mischaschaub.com
joeydee
Establishment
Beiträge: 713
Registriert: 23.04.2003, 15:29
Kontaktdaten:

Re: Warum glitcht meine Kollisionsbehandlung

Beitrag von joeydee »

Hi werte Kollisionskollegen, ich habe gerade nochmal einen Minitest zusammengehackt mit der Konstellation dynamische Kreise und statische Linien-Levelwände. Nur mit einfacher Positionsverschiebung, ohne Euler-Integrator oder weitere Physik.
Man kann natürlich u.U. Stöße durch papierdünne Wände weitergeben und mit genügend Speed bei kleinem Radius durch Wände huschen, aber die Mehrfach-Überlappung müsste glitchfrei sein. Max. 5 Iterationen sind rein willkürlich; je nachdem dauert es bei viel Gedränge ein paar Frames bis sich alles auseinander bewegt hat.
Sprache ist AS3, die Typen sind nachgestellt, also var d:Number heißt soviel wie double d.

Code: Alles auswählen


			//Hauptschleife

			var dirty:Boolean=true;
			var numTries:int=0;
			
			while(dirty && numTries<5){
				numTries++;
				dirty=false;
				//test circles (dynamic) vs. lines (static)
				for(i=0;i<circles.length;i++){
					var circle:PhysCircle=circles[i];
					for(j=0;j<lines.length;j++){
						var line:PhysLine=lines[j];
						var dist:Number=line.distanceToPoint(circle.pos)-circle.rad;
						if(dist<0){
							//slide (dynamic circle vs static wall)
							var normal:Vector3D=line.getNormalAt(circle.pos);
							normal.scaleBy(dist);
							circle.pos.incrementBy(normal);
							dirty=true;
						}
					}
				}
				
				//test all circles vs. circles
				for(i=0;i<circles.length;i++){
					var candidate:PhysCircle=circles[i];
					for(j=i+1;j<circles.length;j++){
						var opponent:PhysCircle=circles[j];
						var normal:Vector3D=opponent.pos.subtract(candidate.pos);
						var len:Number=normal.length;
						if(len!=0)normal.scaleBy(1/len);//normalize
						var dist:Number=len-candidate.rad-opponent.rad;
						if(dist<0){
							//slide (both dynamic)
							normal.scaleBy(dist);
							candidate.pos.incrementBy(normal);
							opponent.pos.decrementBy(normal);
							dirty=true;
						}
					}
				}
			}

PhysCircle ist lediglich ne Struct mit pos und rad.
PhysLine hat v0 und v1 als Endpunkte, sowie diese beiden Methoden:

Code: Alles auswählen

		
		public function distanceToPoint(p:Vector3D):Number{
			var pa:Vector3D=p.subtract(v0);
			var ba:Vector3D=v1.subtract(v0);
			var h:Number=pa.dotProduct(ba)/ba.dotProduct(ba);
			if(h<0)h=0;
			if(h>1)h=1;
			ba.scaleBy(h);
			pa.decrementBy(ba);
			return pa.length-1;
		}

		public function getNormalAt(pos:Vector3D, e:Number=0.1):Vector3D{
			var normal:Vector3D=new Vector3D();
			var x0:Number=distanceToPoint(pos.add(new Vector3D(e,0,0)));
			var x1:Number=distanceToPoint(pos.add(new Vector3D(-e,0,0)));
			var y0:Number=distanceToPoint(pos.add(new Vector3D(0,e,0)));
			var y1:Number=distanceToPoint(pos.add(new Vector3D(0,-e,0)));
			//var z0:Number=distance(pos.add(new Vector3D(0,0,e)));
			//var z1:Number=distance(pos.add(new Vector3D(0,0,-e)));
			normal.x=x1-x0;
			normal.y=y1-y0;
			//grad.z=z1-z0;
			normal.normalize();
			return normal;
		}
Stammt eigentlich aus meinem SDF-Paket. Die Abstandsfunktion dürfte bekannt sein.
getNormal ist hier als Gradientennäherung implementiert, die somit für beliebige SDF-Funktionen funktioniert.
Kann man auch für jedes Objekt mathematisch exakt lösen, für Kreise wäre es z.B. die direkte Verbindung der Mittelpunkte, was ich im cicle-vs-circle-Test direkt in die Schleife gehackt habe statt eine Methode anzulegen.
Benutzeravatar
starcow
Establishment
Beiträge: 324
Registriert: 23.04.2003, 17:42

Re: Warum glitcht meine Kollisionsbehandlung

Beitrag von starcow »

Danke joeydee! Auch eine sehr schöne Methode!
Sehe ich das recht, dass du gar nicht erst versuchst zu verhindern, dass die Objekte ineinander geraten, sondern einfach entlang der Normalen korrigierst, falls überschneidungen auftreten?

Gruss starcow
Freelancer 3D- und 2D-Grafik
mischaschaub.com
joeydee
Establishment
Beiträge: 713
Registriert: 23.04.2003, 15:29
Kontaktdaten:

Re: Warum glitcht meine Kollisionsbehandlung

Beitrag von joeydee »

Ja, im Prinzip berechne ich den Teil nach der Kollision und setze nicht auf einen Zustand vor der Kollision zurück. Aber so macht man das üblicherweise auch, ich muss ja irgendeinen Zustand darstellen, der nach dem Frame plausibel wäre, nicht davor.

Reflect statt Slide wäre übrigens die physikalisch korrektere Response, dafür braucht man ebenfalls den Normalenvektor, kann man also leicht switchen falls man mal Billard oder Minigolf bauen möchte. Spätestens dann am besten auch einen Euler-Integrator verwenden und Kräfte (==Beschleunigung) addieren. Slide ist eigentlich nur eine starke Vereinfachung z.B. für Charaktere, die ihre Bewegung stetig ausgleichen, und läuft auch ohne weitere Physik. Ein Spiel kann man damit bereits bauen.

Den Gradienten hätte ich hier für die Linie gar nicht gebraucht, die Normale steckt auch irgendwo in der Distanzberechnung. Redundanz in den Schleifen für 2x Slide kann man auch eliminieren. Wie gesagt nur zusammengehackt, kann man schöner coden, dafür lauffähig getestet.
joeydee
Establishment
Beiträge: 713
Registriert: 23.04.2003, 15:29
Kontaktdaten:

Re: Warum glitcht meine Kollisionsbehandlung

Beitrag von joeydee »

Für eventuell zuschauende Code-Muffel hier noch zwei Aufnahmen. Bewegung für den einen Kreis ist einfach ++x, im zweiten Fall läuft er in eine "unlösbare" Situation (Position wird dabei immer noch versucht zu ändern).
Wenn mich nichts täuscht, dürfte es da auch in 3D als Ego-Kamera nichtmal Subpixl-Zittern geben.
simplecollider01.gif
simplecollider02.gif
Benutzeravatar
starcow
Establishment
Beiträge: 324
Registriert: 23.04.2003, 17:42

Re: Warum glitcht meine Kollisionsbehandlung

Beitrag von starcow »

Ich muss sagen, das ist schon ziemlich beeindruckend! Vielleicht sollte ich auch mal versuchen, deine Lösung nachzubauen.
Zwar ist es mittels meiner Methode auch mit kleinen Kreisen und beliebig hohen Tempi ausgeschlossen, sich durch Wände hindurch zu buggen - jedoch ist auch der Code um ein Vielfaches länger.
Ich hab jetzt noch nicht ganz verstanden, wie du denn auf die velocity Vektoren bei Kollision reagierst. Die Positionskorrektur ist ja nur die halbe Miete.

Gruss starocw
Zuletzt geändert von starcow am 01.10.2020, 08:56, insgesamt 1-mal geändert.
Freelancer 3D- und 2D-Grafik
mischaschaub.com
joeydee
Establishment
Beiträge: 713
Registriert: 23.04.2003, 15:29
Kontaktdaten:

Re: Warum glitcht meine Kollisionsbehandlung

Beitrag von joeydee »

Ich habe hier nur Position in der Demo, das wäre der allereinfachste Fall für ein Game. Alle Geschwindigkeiten werden händisch auf die Position addiert im Sinne von if(keyRight)player.pos.x+=5;
Das hat zur Folge, dass es keine Eigengeschwindigkeiten gibt, daher das stumpfe Geschiebe. Wer im nächsten Frame nicht irgendwoher ne Positionsveränderung bekommt, bleibt einfach stehen. Es gibt keinen aktuellen Geschwindigkeitsvektor, der ohne Zutun beibehalten wird, wie es die Physik verlangt. Das ist aber keine Bedingung für den Test, ich wollte es nur nicht komplizierter aufbauen als es sein muss.

Euler-Integrator wäre (fast) die volle Miete, also für jedes Objekt je Frame velocity+=acceleration; position+=velocity; und als input addiert man nur Kräfte zur acceleration. Das wäre dann der Ansatz für (Weltraum-)Physik.
In dem Fall kann man dort wo die Positionskorrektur erfolgt auch den Schubs mitgeben. Gleiche Richtung (Normale), Reflect entsteht praktisch von selbst. Geht auch mit dem halben Integrator, also ohne acceleration, dafür velocity den Schubs mitgeben.
Ab dann hat man sowas wie Billard oder Minigolf, man muss dann Reibung einbauen (velocity*=0.5 z.B.), damit alles irgendwann wieder zur Ruhe kommt. Evtl. mach ich dazu nochmal ne kleine Demo.
Massen (sprich Impulserhaltung) wären dann das nächste Fass, das man aufmachen könnte, dann Circle-Gruppen mit Schwerpunk und Aufteilung nicht-zentraler Stöße in Translation und Rotation, ... :)

Ich glaube was du machst mit kleinen Kreisen wäre dann ein Sphere-Sweep? Das ist auch sinnvoll. Für "einfache" Games, wo ich selbst in der Hand habe was passiert, reicht mir immer der einfache Sphere-Test. Ich achte nur auf das Verhältnis Radius/Geschwindigkeit, bzw. lasse die Physik-Schleife entsprechend öfter in kleineren Schritten laufen, und für Bullets nehme ich sowieso Ray-Tests. Das sind dann eigentlich Sphere-Sweeps mit Radius 0, da verpasst man auch nichts mehr.
Benutzeravatar
Hannes
Beiträge: 14
Registriert: 11.06.2008, 06:04

Re: Warum glitcht meine Kollisionsbehandlung

Beitrag von Hannes »

Danke an Euch für die vielen Einblicke und Hinweise. Ich habe mein Problem, hoffentlich nicht nur scheinbar, gelöst.

Aus einem Buch habe ich die folgende Linie-Kreis Schnittpunktberechnung (keine Ahnung wie man darauf kommt und im Buch wird auch nichts beschrieben).

Code: Alles auswählen

function Line:IntersectCircle(rhs)
	local M, r = rhs:GetPosition(), rhs:GetRadius()
	local linePointA, lineDir = self:CalculateParametricForm()
	
	local lineLength = lineDir:Length()
	lineDir = lineDir:Div(lineLength)

	local diff = linePointA:Sub(M)
	
	local a = 2 * lineDir:DotProduct(diff)
	local b = diff:LengthSquared() - r*r
	
	local discriminant = ((a*a) * 0.25) - b
	if discriminant < 0 then return false end
	
	local root = math.sqrt(discriminant)
	local s = a * (-0.5) - root

	if s >= 0 and s <= lineLength then
		return true, linePointA:Add(lineDir:Mul(s))
	end
	
	return false
end
Ich hab daraus folgendes gemacht, um die Wurzel, aus Zeile 5 oben (lineDir:Length()), rauszuoptimieren. Funktioniert wohl nicht wie gedacht.

Code: Alles auswählen

function Line:IntersectCircle(rhs)
	local linePointA, lineDir = self:CalculateParametricForm()
	local M, r = rhs:GetPosition(), rhs:GetRadius()
	local diff = linePointA:Sub(M)
	
	local a = 2 * lineDir:DotProduct(diff)
	local b = diff:LengthSquared() - r*r
	
	local discriminant = ((a*a) * 0.25) - b
	if discriminant < 0 then return false end
	
	local root = math.sqrt(discriminant)
	local s = a * (-0.5) - root

	if s >= 0 and s <= 1 then
		return true, linePointA:Add(lineDir:Mul(s))
	end
	
	return false
end
Der Code ist in Lua.
Ist dass ein Fehler von mir oder handelt es sich dabei um ein Präzisionsproblem?

Das Fertige Progrämmchen:
Kollision - Fertig.zip
(3.61 MiB) 12-mal heruntergeladen
Mit Rechtsklick kann man nun Kreise an der Mausposition Erstellen.
joeydee
Establishment
Beiträge: 713
Registriert: 23.04.2003, 15:29
Kontaktdaten:

Re: Warum glitcht meine Kollisionsbehandlung

Beitrag von joeydee »

LineDir muss normalisiert sein, das ist es in deiner Version dann wahrscheinlich nicht mehr.
Antworten