Du bist nicht angemeldet.

Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!

Kollisionsabfrage: Überschneiden von Objekten

Werbeanzeige

ph4nt0m

Frischling

  • »ph4nt0m« ist der Autor dieses Themas

Beiträge: 81

Beruf: Student

  • Private Nachricht senden

1

19.03.2007, 14:14

Kollisionsabfrage: Überschneiden von Objekten

Hallo,
ich habe ein kleines Problem bei der Kollision von (Billard-)Kugeln untereinander bzw. an Banden. Das ganze ist in 2D. Dabei ist das Problem aber nicht die Berechnung der Abprallwinkel, sondern die Tatsache, dass sich Objekte manchmal überschneiden.

Jede Kugel wird pro Durchlauf um eine bestimmte Anzahl Pixel verschoben und anschließend auf Kollision mit irgendeinem anderen Objekt überprüft. Dabei kann es aber sein, dass sich die Objekte nach dem verschieben schon überlappen und sich nicht einfach nur berühren. Wenn ich dann die Winkel ändere und die Kugeln sich anschließend in die neue Richtung bewegen, kommt es öfters vor (so erkläre ich mir das merkwürdige Verhalten jedenfalls), dass diese sich dann immer noch nicht vollständig voneinander gelöst haben und im nächsten Durchlauf erneut eine Kollision erkannt wird. Die dann wiederum erechneten Winkel stimmen dann natürlich überhaupt nicht mehr.

Ich hoffe das Problem einigermaßen verständlich ausgedrückt zu haben. Vielleicht möchte mir ja jemand weiterhelfen :)

ph4nt0m

Wümpftlbrümpftl

Alter Hase

Beiträge: 774

Beruf: Student

  • Private Nachricht senden

2

19.03.2007, 15:09

Du musst die Position des Objekts nach einer Kollision so korrigieren, dass sozusagen ganz knapp keine Kollision stattfindet. Kollision bedeutet ja an sich, dass 2 Objekte ich überlappen, was ja in der realität eigentlich nie passiert.

chriss

Alter Hase

Beiträge: 624

  • Private Nachricht senden

3

19.03.2007, 15:12

Wenn du die Berührung haben willst mach folgendes:

1. Berechne den Richtungsvektor
2. Prüfe ob du um die maximale entfernung (Richtung * geschwindigkeit * zeit) verschieben kannst
3. wenn nicht berechne den Berührpunkt (Abstand(Kugel1,Kugel2) == Radius (Kugel1) + Radius(Kugel2)
4. Berechne den Austritswinkel (hast ja Gesagt das es kein Problem ist)
5. Verschiebe um den Restweg in die neue Richtung (NeuerVektir * (Gesammtweg - ZurueckgelegterWeg))

Bei Kugeln hast du es da sehr leicht

Punkt 3 ist lineare Algebra und sollte im Schulstoff des Gymnasiums ca 12. Klasse vorhanden sein

ph4nt0m

Frischling

  • »ph4nt0m« ist der Autor dieses Themas

Beiträge: 81

Beruf: Student

  • Private Nachricht senden

4

19.03.2007, 15:35

Erstmal vielen Dank für die Antworten! :)

@chriss:
Die 5 einzelnen Schritte habe ich verstanden. Jetzt frage ich mich nur, wie ich das umsetzen soll. Im Programm überprüfe ich in jedem Hauptschleifendruchlauf jede Kugel zuerst auf Kollision mit Banden und anderen Bällen:

C-/C++-Quelltext

 
1
2

bool ball::collision(int left, int top, int right, int bottom)
bool ball::collision(ball& other)

Diese beiden Methoden überprüfen, ob Kollision vorliegt und ändern gegebenenfalls die Richtungsvektoren der Kugel(n).
Danach bewege ich die Kugel:

C-/C++-Quelltext

 
1

void ball::move(float time)

Diese Methode addiert einfach die (durch die collision-Funktion eventuell geänderten) aktuellen Richtungsvektoren auf die Position, teilt das ganze aber vorher durch die übergebene Zeit, die ich in einer Timerklasse berechne (Stichwort: QueryPerformanceCounter()). Durch diese Zeit wird die Größe der Bewegung pro Durchlauf natürlich der Framerate angepasst, ist damit allerdings nicht konstant.

Deine Berechnungen müsste ich ja nun am besten in der collision-Funktion durchführen, was aber ohne die Zeit (und damit auch ohne den wahren Weg, um den die Kugel bewegt werden soll) unmöglich ist.

Wie sollte ich meine Funktionen am besten organisieren? Sollte ich der collision-Funktion auch die Zeit übergeben? Ich würde mich über weitere hilfreiche Vorschläge sehr freuen ;)

ph4nt0m

chriss

Alter Hase

Beiträge: 624

  • Private Nachricht senden

5

19.03.2007, 20:00

Ich würde eine Klasse schreiben welche alle Kugeln und die Bandee verwaltet. Diese ist dann auch für Bewegung und Kollisionstest verantwortlich (muss aber nicht so gemacht werden).

Was du machst find ich gut. Ich würde für jede Kugel erst einmal die Bewegung durchführen, also in der Annahme das alles reibungslos funktioniert. Hierbei muss für jede Kugel die alte Position gespeichert werden und die Bewegungsrichtung.

C-/C++-Quelltext

 
1
2
3
4
5
6

unsigned long i = 0;
for(i=0; i < Kugel.length; i++)
{
 Kugel[i].PosAlt = Kugel[i].Pos;
 Kugel[i].move(globalTime);
}

Dann für jede Kugel die Kollision prüfen.
Hier kommt es darauf an wie du es machen willst. Physikalisch am besten wäre es jede Kugel mit jeder zu testen, dabei aber bereits ducrchgeführte Tests auszuschließen.
Ein simples verfahren wäre das von bubblesort, jedoch nicht umbedingt das schnellste. Also du beginnst beim ersten Element und prüfst mit allen anderen. Dann gehst du zum nächsten und prüfst von dort aus auf alle anderen. Das Erste wird hierbei schon ausgelassen usw.

C-/C++-Quelltext

 
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

unsigned long a = 0;
unsigned long b = 0;

for(a=0; a < Kugeln.lenght; a++)
{
  for(b=a; b < Kugeln.length; b++)
  {
     if(Kugel[a]->collision(Kugel[b]))
     {
         // Die Restzeit holen. Also die zeit die nach dem Berührpunkt

         // noch übrig bleibt

         Time1 = Kugel[a]->GetEllapsedTime(Kugel[b]);
         Time2 = Kugel[b]->GetEllapsedTime(Kugel[a]);

          // Die neue Richtung ermitteln

          Kugel[a]->ChangeMove(Kugel[b]);
          Kugel[b]->ChangeMove(Kugel[a]);

          // Die Kugeln mit der Restzeit und neuen Richtung bewegen

          Kugel[a]->move(Kugel[b]); 
          Kugel[b]->move(Kugel[a]);

          // Globales Flag setzen

         someflag = true;
      }
  }
}

Diese ganze Prozedur musst du so lange ausführen bis ein ganzer Durchlauf mit allen Kugeln keinen einzigen positiven Test durchführt (sehr langsam nehm ich an) Da die zeit dabei aber immer abnimmt wird das jedoch irgend wann passieren. Für viele genres sehr unpraktikabel aber für Billard perfekt denn sonst hast du beim Anstossen keine korrekten Ergebnisse wie sich die Kugeln bewegen.

Reicht das als Anregung? Optimieren kann man das bestimmt noch so in jeder zeile :D aber so funktioniert es schonmal.

ph4nt0m

Frischling

  • »ph4nt0m« ist der Autor dieses Themas

Beiträge: 81

Beruf: Student

  • Private Nachricht senden

6

23.03.2007, 18:19

Vielen Dank für die Hilfe! Ich komme leider erst heute wieder dazu, das auszuprobieren, deshalb meine "späte" Antwort. :oops:
Ich melde mich dann mit Ergebnissen wieder. ;)

ph4nt0m

Edit:
Ich konnte bisher leider nur die Kollision mit einer Bande korrigieren. Dabei bin ich etwas anders vorgegangen, um mir in der move-Funktion eine Abfrage zu sparen, ob die Kollisionsfunktion die Kugel schon bewegt hat oder nicht. Sonst würde es nachher doppelte Bewegungen pro Durchlauf geben... Dabei gehe ich wie folgt vor:

Zuerst wird berechnet, ob die Kugel kollidieren würde, wenn sie jetzt um die entprechende Anzahl Pixel bewegt werden würde. Falls ja, werden die Richtungsvektoren entsprechend geändert und die korrekte Position der Kugel nach der Kollision berechnet. Dann wird die Kugel allerdings nicht auf diese Position gesetzt (denn sonst würde der anschließende move() Aufruf ja nocheinmal bewegen), sondern auf genau die Position, damit sie sich erst nach dem dann folgenden Aufruf der move-Funktion auf der richtigen Position befindet.

Etwas kompliziert, aber damit kann ich wenigstens in jeder Schleife collision() und dann move() aufrufen, ohne, dass diese beiden irgendwie untereinander kommunizieren müssten.

Weil das ziemlich gut funktioniert und auch aussieht, wollte ich das jetzt also auf die Kollision zwischen zwei Kugeln übertragen. Dabei mangelt es zur Zeit aber noch an der Berechnung des exakten Berührpunktes: Auch hier habe ich ja wieder nur den Weg und die Richtung, in die sich beide Kugeln bewegen wollen. Die Abfrage, ob sie kollidieren WÜRDEN, ist natürlich kein Problem. Da sie sich nach der vollständigen Bewegung dann aber wie gesagt eventuell überschneiden, brauche ich die Position, an der sie sich berühen (oder den Weg, den beide bis dahin zurückgelegt haben).

Das ganz gestaltet sich jedenfalls doch komplizierter, als ich dachte. Vielleicht könnt ihr mir ja nochmal weiterhelfen 8)

ph4nt0m

Werbeanzeige