2D Kollisionsabfrage: "Nachfolgekollision"

[achim2310]

Hallo,

Ich hab nochmal eine Frage zur 2D Kollision. Ich erläuter mal kurz den Stand der Dinge:
Jedes Objekt wird als Rechteck behandelt. In jedem Frame wird eine Objektliste durchgelaufen und überprüft, ob sich zwei Rechtecke überlappen (d.h. eine Kollision vorliegt). Ist dies der Fall, wird die Position eines der Rechtecke (oder evtl. auch beider Rechtecke) so korrigiert, dass keine Kollision mehr stattfindet.
Das "Durchlaufen" duch die Objektliste gestaltet sich recht simpel und wahrscheinlich nicht besonders optimal:

for(int i=0; i < lpLevel->iAnzObj; i++)
	{
		for(int j = i+1; j < lpLevel->iAnzObj; j++)
		{	
			bKollision = FALSE;

				bKollision = momObjekte_BoundingBoxObj(lpLevel,&(lpLevel->lpObjListe[i]),&(lpLevel->lpObjListe[j]));

			if(bKollision)
{
	// Positionskorrektur...
}

Jetzt hab ich ein Problem, das ich mal "Nachfolgekollision" getauft habe: Angenommen das i-te Objekt kollidiert mit irgendeinem j-ten Objekt. Dann wird die Position des i-ten Objekts korrigiert und angenommen sie wird so korrigiert, dass das i-te Objekt mit einem k-ten Objekt in der Liste wieder kollidiert, wobei k < i ist, dann wird diese Kollision nicht erkannt !
D.h. ich müsste nach jeder Positionskorrektur wieder die gesamte Liste durchlaufen und nach einer Kollision suchen ?????? Sagt mir bitte, dass das nicht wahr ist, denn das ist doch viel zu Performance-hungrig !
Hat jemand eine bessere Idee - muss ich die Kollisionsabfrage ganz anders aufbauen ??

Danke im Voraus,
achim2310

[TGGC]

Sinvoll wäre erstmal eine Unterscheidung in bewegliche und nichtbewegliche Objekte, tust du das schon? Dann solltest du dir genau überlegen, wie die Reaktion auf die Kollision sein soll, müssen die Objekte wirklich unbedingt zurückgesetzt werden? Wie genau wird überhaupt zurückgesetzt?

Und ja, dein Kollisionstest ist wirklich "nicht besonders optimal".

Bye, TGGC (Der Held ist zurück)

[achim2310]

Ja, ich unterscheide schon zwischen beweglichen und nicht beweglichen Objekten. Aber halt nur bei der Positionskorrektur - man könnte in der äußeren Schleife noch prüfen, ob es sich um ein Statisches Objekt handelt (wenn ja, innere Schleife nicht ausführen) -ok. Aber das ändert ja nichts daran, dass wenn irgendwo nach einer Kollision eine Position korrigiert wird (und bei jeder Kollision muss ja die Position korrigiert werden, denn sonst bleibt die Kollision ja weiterhin bestehen) die komplette Liste nochmal erneut durchsucht werden muss, um eine "Nachfolgekollision" auszuschließen....

[lustig]

Eine Frage, wieso prüfst du nicht zuerst, ob die Position frei ist und verschiebst nur dann das Objekt? Wenn ich das richtig verstanden habe prüfst verschiebst du zuerst das Objekt und wenn eine Kollision stattfindet, versuchst du es irgendwoandershin zu verschieben. Dann bleibt dir nichts anderes übrig als die neue Position wieder zu prüfen (rekursion). Andersherum wäre es wahrscheinlich einfacher, falls das möglich ist.

[Sgt. Nukem]

In 3D würde man sicher ein BoundingVolume plus einen BewegungsVektor benutzen.
Man könnte dann alle BVs so lange an den jeweiligen BVn (ähh... sind ja super Abkürzungen: BoundingVolume und BewegungsVektor ) verschieben, bis die erste Kollision stattfindet. Dann wird der kollidierte BewVek gespiegelt (oder was auch immer) und es wird wiederum so lang weitergegangen, bis eine erneute Kollision stattfindet. So könnte man beliebig viele Objekte gegeneinander überprüfen in einem beliebig langen zeitlichen Rahmen (gegeben durch den größten BewVek).

[0x00000001]

Ich würde die innere for-Schleife in eine Funktion packen. Die wird dann einfach für jedes Objekt aufgerufen, und falls mal eins aufgrund von Kollision zurückgesetzt werden muss wird die Funktion für dieses Objekt einfach nochmal aufgerufen. Das könnte aber zu einer Endlosschleife führen, wenn ein Objekt irgendwie zwischen zwei andere Gerät und dann da hin und herwackelt. Das musst Du halt irgendwie ausschließen.

[TGGC]

Klar ändert das etwas, du kannst dir ja so viel Arbeit sparen, z.b. ist es ja sinnlos statische rects überhaupt gegeneinander zu testen, bei Zurücksetzen kann nie ein statisches rect berührt werden usw. Soviele bewegliche Objekte hat man normal garnicht, oder man benutzt (wie z.b. in RTS) von vornherein andere Methoden.

Wieso darf die Kollision nicht weiterbestehen? Wenn nicht, kann man sie vorausschauend verhindern (siehe lustig)?

Bye, TGGC (Der Held ist zurück)

[achim2310]

Eine Frage, wieso prüfst du nicht zuerst, ob die Position frei ist und verschiebst nur dann das Objekt?

Naja, und wie mach ich das ? Ich muss schauen, ob ein anderes Rechteck das aktuelle Rechteck an der neuen Position schneidet - d.h. ich muss beide Objekte erstmal an die neue Position schieben. Falls es eine Kollision gibt, kann ich sie ja wieder zurückversetzen, was ich ja innerhalb der Positioinskorrektur auch mache und dann halt ensprechend wieder vor, dass sie genau aneinander liegen...

Das problem ist nur, dass es bei Rechtecken echt nicht so einfach ist, eine Kollision im Voraus anhand der Bewegungsvektoren festzustellen ... z.B. bei Kreisen geht das viel einfacher (ich will aber rechtecke verwenden)...
Hat da jemand eine Idee ?? Wenn das nämlich funktioniert ("schneidet Vektor a von ObjA Vektor B von ObjB an der Stelle S --> Kollision --> "Kollisionsstelle S"), dann ging auch die Positionskorrektur viel viel einfacher...

Klar ändert das etwas, du kannst dir ja so viel Arbeit sparen, z.b. ist es ja sinnlos statische rects überhaupt gegeneinander zu testen

Ja stimmt eigentlich - Performance-mäßig ist das schon ein krasser unterschied.
Sorry, aber was ist RTS ? Hab ich ne Bildungslücke ?

[TGGC]

achim2310 schrieb:

Sorry, aber was ist RTS ? Hab ich ne Bildungslücke ?

Offensichtlich: RTS = _r_eal _t_ime _s_trategy
Das einzige was mir spontan einfällt, wo man mehr als ~20 bewegte Objekte zu prüfen hätte.

Bye, TGGC (Der Held ist zurück)

[Sgt. Nukem]

TGGC schrieb:

Das einzige was mir spontan einfällt, wo man mehr als ~20 bewegte Objekte zu prüfen hätte.

...oder bei blödsinnigen 4K-Demos wo drölfzig Millionen Kugeln umher fallen - WENN man sie denn physikalisch korrekt hätte abprallen lassen...

[TGGC]

Warum wird wohl dort (genau wie bei Partikelsystemem) nicht auf Kollisionen getestet?

Bye, TGGC (Der Held ist zurück)

[Sgt. Nukem]

TGGC schrieb:

Warum wird wohl dort (genau wie bei Partikelsystemem) nicht auf Kollisionen getestet?

Weil ab da wahres Heldentum anfangen würde...

...und das ist 'ne Sache für Jay-Ci, und sonst keinen...!