Du bist nicht angemeldet.

Werbeanzeige

1

19.04.2008, 15:16

Kollision bewegter Sphären im 2D

Ausgangslage: In einem Kartensektor beschränkter Größe soll jedes Objekt gegen jedes andere auf Kollision geprüft werden.
Dazu besitzt jedes Objekt eine Ausgangsposition, eine Ausrichtung, eine Geschwindigkeit sowie einen Radius.
Im Falle einer Kollision müssen beide betroffenen Objekte über den genauen Kollisionspunkt informiert werden.
Problematik: Einfach nur die Abstände der einzelnen Zielpositionen mit der Summe der Radien zu vergleich bringt nicht das gewünschte Ergebnis da:
  • Objekte sich somit gegenseitig überspringen könnten
  • Objekte mitten in anderen Objekten landen würden
  • Kollisionspunkt kann nicht bestimmt werden
Betrachtet man die Bewegung der Objekte als Strecken im R² löst sich zwar das Problem das sich Objekte überspringen würden, es kommt jedoch das Problem hinzu das z.B. 2 Projektile kollidieren würden nur weil die Flugbahnen sich schneiden.

Gesucht ist nun eine Möglichkeit anhand der Ausgangsposition, der Geschwindigkeit, der Ausrichtung und der Radien mit dem geringsten Aufwand den genauen Kollisionszeitpunkt zu berechnen.

Ein möglicher Lösungansatz wäre die Kollision zweier Sphären im R² als das Unterschreiten des Abstand zweier Strecken in der X-Y-Ebene in einem R3-Raum mit den Achsen X, Y und t zu betrachten.

Bereit die Umformulierung des letzten Satzes in eine Formel wäre ein große Hilfe ;)

Das Gurke

Community-Fossil

Beiträge: 1 999

Wohnort: Pinneberg

Beruf: Schüler

  • Private Nachricht senden

2

26.04.2008, 17:28

Wir scheinen das Problem nahezu gelöst zu haben. Momentan testen wir die verschiedensten Fälle mit einem kleinen Testprogramm durch. Die Formel wie das Programm sind gleichermaßen gruselig. Ich poste das nur mal als Referenz. Alternativ auch auf Nopaste, dann gibts keine Zeilenumbrüche: http://nopaste.org/p/aAm5X4kse

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <cstdlib>
#include <cmath>

struct Entity
{
    float x;
    float y;
    float u;
    float v;
    float r;
};

int main(int argc, char** argv)
{
    Entity e[2];
    // Taking arguments from the commandline

    if (argc == 11)
    {
        for (int i = 0; i < 2; ++i)
        {
            e[i].x = atof(argv[i * 5 + 1]);
            e[i].y = atof(argv[i * 5 + 2]);
            e[i].u = atof(argv[i * 5 + 3]);
            e[i].v = atof(argv[i * 5 + 4]);
            e[i].r = atof(argv[i * 5 + 5]);
        }
    }
    // Entering them by hand

    else
    {
        for (int i = 0; i < 2; ++i)
        {
            std::cout << "Entity " << i + 1 << ":";
            std::cout << std::endl <<"X:";
            std::cin >> e[i].x;
            std::cout << std::endl <<"Y:";
            std::cin >> e[i].y;
            std::cout << std::endl <<"U:";
            std::cin >> e[i].u;
            std::cout << std::endl <<"V:";
            std::cin >> e[i].v;
            std::cout << std::endl <<"R:";
            std::cin >> e[i].r;
        }
    }
    
    float p = 2*(e[0].x*e[0].u+e[1].x*e[1].u-e[0].x*e[1].x-e[1].x*e[0].u-e[0].x*e[1].u+e[0].y*e[0].v+e[1].y*e[1].v-e[0].y*e[1].y-e[1].y*e[0].v-e[0].y*e[1].v)/(e[0].u*e[0].u+e[1].u*e[1].u-2*e[0].u*e[1].u+e[0].v*e[0].v+e[1].v*e[1].v-2*e[0].v*e[1].v);
    float q = (e[0].x*e[0].x+e[1].x*e[1].x+e[0].y*e[0].y+e[1].y*e[1].y-(e[0].r+e[1].r)*(e[0].r+e[1].r))/(e[0].u*e[0].u+e[1].u*e[1].u-2*e[0].u*e[1].u+e[0].v*e[0].v+e[1].v*e[1].v-2*e[0].v*e[1].v);
    if(p*p>=4*q)
    {
        float t1 = -p/2+sqrt(p*p/4-q);
        float t2 = -p/2-sqrt(p*p/4-q);

        std::cout << "t1: " << t1 << " t2: "<< t2 << std::endl;
    }

    return (0);
}

3

26.04.2008, 19:21

Zitat

Thankfully, the solution to a very hard problem could not be simpler. What we are really interested in is not their movement vectors, but their movement relative to each other. If we translate circle A's movement such that B can be considered stationary, we can use the Dynamic-Static solution described above!


Quelle: http://www.gamasutra.com/features/20020118/vandenhuevel_01.htm

Fuer "early rejection" kann das Bewegungsvolumen betrachtet werden.


PS: Bei langen Zeilen im Quelltext kann man ruhig auch mal per Hand 'nen Zeilenumbruch erzeugen. Selbst im Quelltext bei dir zu Hause bringt es nichts, staending nach links und rechts zu scrollen, du kannst auch innerhalb der Formel semantisch gruppieren. Ich werde mir nicht die Muehe machen, zu verstehen, was du da in dem Einzeiler machst. Zeilenumbrueche sind nicht schlimm und tun niemanden weh.

4

27.04.2008, 10:56

Dieser Ein(Zwei-)zeiler ist die Umstellung der Gleichung

Quellcode

1
r1+r2 = sqrt((x1+u1*t-x2-u2t)²+(y1+u1*t-y2-v2*t)²)
nach t unter Anwendung der pq-Formel zum lösen dieser quadratischen Gleichung wobei u und v jeweils den Versatz innerhalb eines Frames angeben.

Die Lösung in dem Link den du gepostet ist allerdings nicht wirklich effizienter bedingt durch den wiederhohlten Einsatz von Kreisfunktionen und dem normalisieren der Vektoren.

5

27.04.2008, 12:14

Im ersten und zweiten Post wurde nicht von Effizienz. Ausserdem ging es mir nicht darum, dass du die Kurzformel hinschreibst, sondern erlaeuterst (in Worten) was dein Ansatz ist, welche Idee hinter deiner Herangehensweise ist. Dann brauchst du auch nicht einzelne Faelle testen, sondern hast eine mathematisch "bewiesene" Loesung und brauchst nur schauen, ob die Implementation stimmt.

In dem Artikel wird auch gesagt: "An Algorithm That Works", Moeglichkeiten zur Optimierung sind meist auch abhaengig von deinem Design. Z.B. kannst du die Geschwindigkeit auch in deren Betrag und Richtung aufsplitten. Ausserdem finde ich die Herangehensweise elegant, da das Problem auf ein einfacheres zurueckgefuehrt wurde. Das vereinfacht auch das Testen und Erstellen von Testfaellen. Also genau das Gegenteil von "gruselig".

Es werden keine Winkelfunktionen genutzt, nur "normalize" und "magnitude". Also 3*Wurzelfunktion ( die restlichen koennte man auf Anhieb sparen ). Wenn man viele Objekte hat, so kann man durch andere Konzepte wie Quadtrees viele Kollisionstest einsparen.

PS: Ich wuerde Zeilenumbrueche oben in dem Code begruessen. :-)

Werbeanzeige