Kollisionserkennung

[dba]

Hallo!

Ich schreibe zur zeit ein Programm, in welchem 2D Objekte Miteinander kollidieren können: Kugeln mit Wänden und Kugeln untereinander.
Das tun sie auch ganz gut miteinander. Aber so ganz sauber ist das alles jedoch nicht. Der Ablauf der Kollisionserkennung sieht zunächst wie folgt aus:
Kollisionserkennung zwischen Linien und Kugeln.: Liste durchschleifen und Auf Zusammenstöße reagieren. Es wird nicht darauf geachtet, welche Objekte ZUERST Kollidiert sind. Es werden lediglich die Kugeln so lange behandelt, bis sich nichts mehr überschnitten hat und die Strecke für diesen Zeitschritt aufgebraucht ist. Das will ich jetzt aber verbessern.

Die Implementierung der Erkennung der Kugeln untereinander hat zwar funktioniert, liefert jedoch kein, aufgrund einer fehlenden beachteten Größe keine fruchtenden Ergebnisse. Denn die Zeit selbst zwischen den Zeitschritten muss auch noch unterteilt werden.
Praktisch gesehen dachte ich mir das wie folgt: Es soll die Reihenfolge der Zusammenstöße beachtet werden.
Also gleiche ich alle Objekte miteinander ab, suche die Früheste Kollision während des Zeitschrittes und behandle diese entsprechend. die beiden Objekte ändern Ihre Position und ein nächster check wird durchgeführt. Ich hätte aber einen ziemlichen Overhead verursacht. Kennt jemand hierfür ein gutes Entwurfsmuster? Das Management während einer solchen Abfrage...


Vielen dank fürs Lesen!

schönes Wochenende,
dba

[SPech]

Wenn du die Kollisionen pro Frame betrachtest dann sind dort alle Kollisionen gleichzeitig. Ich würde dann ein Flag bei den Objekten setzen das diese getroffen wurden und im Anschluss für alle das Kollisionsverhalten durchgehen: Zurücksetzen, Entfernen, Schaden verursachen, ...

[BlueShark]

Moin moin,

Die Implementierung der Erkennung der Kugeln untereinander hat zwar funktioniert, liefert jedoch kein, aufgrund einer fehlenden beachteten Größe keine fruchtenden Ergebnisse. Denn die Zeit selbst zwischen den Zeitschritten muss auch noch unterteilt werden.

Vielleicht kannste ja mal den Code dafür posten, dann finden wir vielleciht diese unbekannte Größe.

Aber mich würde folgendes interessieren:

Also gleiche ich alle Objekte miteinander ab

Gehst du bei der Kollisionsüberprüfung einer Kugel durch die gesamte Liste der restlichen Kugeln oder ermittelst du ersteinmal, welche Kugeln überhaupt für eine Kollision in Frage kommen könnten, sprich nur die die in unmittelbarer Nähe der zu prüfenden Kugel liegen? Falls nicht würde ich empfehlen, dass du so etwas in der Art implementieren solltest. Dafür gibt es glaube ich sogar nen Algo. Wenn mir wieder einfällt wie der heißt reiche ich das noch nach.

Was vielleicht auch noch interessant wäre, wie schnell sich deine Kugeln bewegen können. Sind die eher langsam sollte eigentlich eine Kollision auf Basis der Radien der beiden Kugeln reichen. Sind es jedoch schnellere Objekte muss man mit anderen Mitteln ran. Dann musst du wirklich einen aufwändigeren Test benutzen.

Wenn du die Kollisionen pro Frame betrachtest dann sind dort alle Kollisionen gleichzeitig.

Stimmt, wenn es sich um langsame Objekte handelt reicht das vollkommen aus. Aber nehmen wir einmal an, dass sich ganz viele Kugeln mit relativ kurzen Abständen zueinander in einem abgeschlossenen System befinden. Nun schießt man eine Kugel da hinein, deren Geschwindigkeit sehr hoch ist. In einem Frame würde man nur eine Kollision detektieren, wenn man Glück hat, dass diese schnelle Kugel das System rechnerisch nicht schon verlassen hätte. In Wahrheit hätte man in diesem Frame jedoch sehr viele Kollisionen in sehr kurzen Zeitabständen haben müssen. In diesem Fall können wir nicht mehr eine Methode verwenden, die nur in speziellen Situationen funktioniert.

Kannst du noch ein wenig mehr Infos rausrücken? Der Code der Kollisionserkennunt zum Beispiel. Und ob du irgendeine Art von Vorauswahl der Kugeln für die Kollision machst. Vlt. kannst du dir ja auch mal folgende Seite anschauenhttp://www.geometrictools.com/index.html. Vielleicht findest du da ja einen Ansatz für dein Problem.

Mfg
BS

[dba]

Hallo!

Die Kugeln bewegen sich unterschiedlich schnell. das heißt, dass pro frame tatsächlich zig kollisionen stattfinden können.

Gehst du bei der Kollisionsüberprüfung einer Kugel durch die gesamte Liste der restlichen Kugeln oder ermittelst du ersteinmal, welche Kugeln überhaupt für eine Kollision in Frage kommen könnten, sprich nur die die in unmittelbarer Nähe der zu prüfenden Kugel liegen?

Ich habe bisher nur die Kugeln nacheinander miteinander abgeglichen und daraus die reaktionen abgeleitet. Aber eigentlich muss man ja, nach der ersten (auf zeitlicher basis) Kollision des frames, die gleiche Prüfung nochmal durchführen.

Da die Objekte unterschiedlich schnell fliegen, bekommen die Kugeln einen schweif hinten dran, der den aktuellen Punkt mit dem letzten Punkt verbindet. wenn diese Linie etwas schneidet, gibt es eine Kollision - funktioniert. Das wäre die Abfrage zwischen Kugeln und Linien.
Auch Kugeln mit Kugeln funktionieren. Aber im zusammenspiel kommt einiges durcheinander.

ich hab den Code auf das wesentliche reduziert. Damit wir uns nicht an den Details aufhalten. Die Algorhithmen für ausfallswinkel usw sind eh alle im netz zu finden und funktionieren ja.
also hier die beiden schleifen:

Code: Alles auswählen

public void _ManageMovements(ref List<IGameObject> bowls, ref List<IGameObject> obstacles)
        {

            //die objekte auf ihre neue position setzen
            foreach (IGameObject var in bowls)
            {
                var.SetNewPosition(); // Hier Wird die Neue Position gesetzt, wodurch überschneidungen usw stattfinden.
            }
            // die Kugeln liegen nun auf neuen Positionen, haben aber höchstwahrscheinlich andere Objekte geschnitten


            //1. schleife - Kugeln mit Linien
            #region bowl - Line

            for (int i = 0; i < bowls.Count; i++)
            {
//jede kugel mit  jeder Linie abgleichen
                if (bowls[i].Frozen == false)
                {
                    //erstelle den Vektor der akutellen Kugel

                    for (int c = 0; c < obstacles.Count; c++)
                    {

                        //erstelle den vektor der aktuell betrachteten Linie

                        //wenn die beiden Vektoren sich schneiden, ist Colliding vectors(...) == true 
                        if (CollidingVectors(u, v, p, q, ref tempHit, ((Bowl)bowls[i]).radius))
                        {
                            //kollisionsbehandlung  zwischen linie  und Kugel
                            //Ausfallsvektor wird berechnet und Kugel wird an den neuen Endpunkt gestzt
                        }
                    }

                }


            #endregion


                //2. schleife
                //Kugeln mit Kugeln
                //erst jetzt werden die Kugeln untereinander behandelt
                #region bowl - bowl

                //die äußersten beiden schleifen gleichen die kugeln jeweils miteinander ab
                for (int i = 0; i < bowls.Count; i++)
                {


                    for (int j = i + 1; j < bowls.Count; j++)
                    {



                        //für jedes aktuelle Kugelpaar wird der zeitschritt in kleinere Zeitschritte unterteilt 
                        //dadurch nähert  man sich dem an, was zwischen den Frames geschehen ist
                        for (int a = 1; a < accuracyBowlBowl + 1; a++)
                        {
                            //distanz während des teilzeitschritts wird berechnet
                            dist = Force.GetDistance(u, p, v, q, 1 / a);

                            //Kollision, wenn mindest Distanz unterschritten wird
                            if (Math.Abs(dist) < minDist)
                            {


                                //vektoren für die beiden Kugeln berechnen
                                //Kugeln um diese vektoren verschieben

                            }
                        }

                    }
                }

                #endregion


            }
        }

mein vorschlag wäre jetzt, diesen durchlauf so umzubauen, dass wir zusätzlich ermitteln, zu welchem Zeitpunkt der zeitschritt erfolgt ist. und dann den zeitlich ersten Fall behandeln.
ungefähr so:

Code: Alles auswählen

do
{
//Kollisionsliste erstellen
//zeitlich ersten Fall behandeln
}while(CollisionCount != 0)
//dann würden wir die reihenfolge sauber beachtet haben.

So wäre mein Muster gewesen, welches ich in den nächsten tagen einbauem möchte. Hat jemand hierzu ein paar erfahrungen`?

grüße,
dba