Kollisionserkennung mit Zeitdifferenzmessung

Hallo zusammen,

ich habe mal ein wenig mit spieleprogrammierung angefangen und habe ein problem mit der Kollisionserkennung.

Im moment mache ich das so wie ich das in einem tutorial gelesen hatte:

Ich habe eine main-loop in der am anfang die zeit seit dem letzen betreten der loop berechnet wird, daraufhin werden alle Aktoren basierend auf der zeitdifferenz bewegt und dann wird geprüft, ob bei den neuen positionen irgendwo kollisionen auftauchen.

Ein problem ist allerdings, wenn es mal kurz einen ruckler gibt und dadurch die zeitdifferenz zu groß wird, dadurch kann es dazu kommen, dass spielfiguren "durcheinander durchfliegen" ohne zu kollidieren.
Wie kann man das gut lösen?
Mir fallen 2 sachen ein:
- eine Obergrenze für die zeitdifferenz einführen (wenn die differenz zu groß ist kann man entweder einfach so tun, als ob die differenz kleiner wäre oder man macht dann mehrere berechnungsschritte für eine loop)
- eine berechnung von kollisionen unabhängig von der vergangenen zeit, z.B. mit sachen wie geradengleichungen oder soetwas

bin mal gespannt auf eure antworten/meinungen dazu.
Vielen Dank schonmal für eure Hilfe!

Gast1337 schrieb:

Hallo zusammen,

ich habe mal ein wenig mit spieleprogrammierung angefangen und habe ein problem mit der Kollisionserkennung.

Im moment mache ich das so wie ich das in einem tutorial gelesen hatte:

Ich habe eine main-loop in der am anfang die zeit seit dem letzen betreten der loop berechnet wird, daraufhin werden alle Aktoren basierend auf der zeitdifferenz bewegt und dann wird geprüft, ob bei den neuen positionen irgendwo kollisionen auftauchen.

Ein problem ist allerdings, wenn es mal kurz einen ruckler gibt und dadurch die zeitdifferenz zu groß wird, dadurch kann es dazu kommen, dass spielfiguren "durcheinander durchfliegen" ohne zu kollidieren.
Wie kann man das gut lösen?
Mir fallen 2 sachen ein:
- eine Obergrenze für die zeitdifferenz einführen (wenn die differenz zu groß ist kann man entweder einfach so tun, als ob die differenz kleiner wäre oder man macht dann mehrere berechnungsschritte für eine loop)
- eine berechnung von kollisionen unabhängig von der vergangenen zeit, z.B. mit sachen wie geradengleichungen oder soetwas

bin mal gespannt auf eure antworten/meinungen dazu.
Vielen Dank schonmal für eure Hilfe!

In der Praxis entkoppelt man Rendering, Logik & Physik. d.h. man macht immer 100 Physiksimulationen pro Sekunde, egal wie hoch die Framerate gerade ist. So kann es natürlich vorkommen, dass zwischen zwei Frames mehrere Physikberechnungen durchgeführt werden.

Cpp_Junky

An dem Zeug versuch ich mich auch gerade. Das Problem entsteht bereits, wenn die Schrittweite die Größe des Objekts übersteigt, z.B. bei kleinen sich schnell bewegenden Objekten. Mein Plan war, es mit einer Bounding Box zu versuchen, die in Bewegungsrichtung orientiert und dann gestreckt wird (u.U. länger als das Objekt tatsächlich ist). Ist evtl etwas ungenauer als in der Realität, aber es würde wenig zusätzlichen Rechenaufwand erfordern.

rapso

es ist durchaus ueblich die AABB vom object zur start und endzeit zu nutzen um erste ueberlappungstests zu machen, um so festzustellen ob kollisionsberechnungen noetig sind. wenn man z.b. eine patronenkugel hat die fliegt, sind kollisionnen in den wenigsten frames wahrscheinlich, aber man moechte dennoch dass man keine uebersieht. Da ist eine grosse bounding box besser als die zeitschritte winzig werden zu lassen.
und ja, 100 feste zeitschritte ist durchaus ueblich. manchme physics engines tesselieren die zeit dann noch weiter falls kollisionen vorhanden sind, um die simulation genauer zu machen. das kann z.b. bei box stacking wichtig sein, weil dabei die kleine instabilitaet ueber die zeit und die anzahl der boxen sichtbar wird.

Eisflamme

Bei ner Patronenkugel würde ich doch eher die Linie des Schusses mit den Objekten kollidieren lassen, oder?

Mir fallen 2 sachen ein:
- eine Obergrenze für die zeitdifferenz einführen (wenn die differenz zu groß ist kann man entweder einfach so tun, als ob die differenz kleiner wäre oder man macht dann mehrere berechnungsschritte für eine loop)
- eine berechnung von kollisionen unabhängig von der vergangenen zeit, z.B. mit sachen wie geradengleichungen oder soetwas

Erstere Lösung ist gut, wenn die Performance nicht so wichtig ist, da die Implementierung sehr einfach ist.

Wenn das zu lange dauert, könnte man zweitere Methode versuchen, indem man die Boundingbox des bewegenden Objektes einfach von Start- bis Endposition verlängert. Da hätte man also 8 Linien (evtl. weniger), welche man auf Kollision mit der anderen Box testen müsste. Für jede Linie müsste man bis zu 6 Flächen testen, also 8x6 = 48 Linien-zu-Flächen-Kollisionen. Aber das reicht ja nicht, weil man die Fläche zwischen den Linien auch testen muss, z.B. wenn BB1 viel größer als BB2 ist. Vielleicht reichen da Diagonalen oder so aus, hmm... eher nicht.

Also ich breche Mal ab. Ich glaube, Variante 1 ist deutlich besser, wenn Du nicht gerade reine Achsenbewegungen hast.

Ok, danke schonmal für eure hilfreichen antworten.
Ich werde jetzt mal mein derzeitiges konzept in java-code vorstellen (ich habe vor auf c++ umzusteigen, aber bisher hab ich in richtugn spiele nur mit java gearbeitet), vll habt ihr ja noch was dazu zu sagen (verbesserungsvorschläge o.ä.):

private static final long LOGIC_FRAME_TIME = 1e9/100; //100 logic frames per second, time in nanoseconds
private long rest;  //zeit die vom letzten logikframe übrig geblieben ist
private final List<Actor> actors;
public static void gameLoop()
{
   while(gameIsRunning)
   {
      checkKeys(); //nicht so wichtig erstmal
      long delta = calculateDelta() + rest; //vergangene zeit in nanosekunden
      while(delta > LOGIC_FRAME_TIME)
      {
        doLogicFrame(LOGIC_FRAME_TIME);
        delta -= LOGIC_FRAME_TIME;
      }
      rest = delta;
      //logik hat priorität (wird öfter ausgeführt als grafik)
      renderObjects();
   }
}

private static void doLogicFrame(long delta)
{
    moveObjects(delta);
    checkCollisions();
    doLogics(delta);
}

private static void moveObjects(long delta)
{
    for(Actor a : actors)
    {
       a.move(delta);
    }
}

private static void checkCollisions()
{
    for(Actor a1 : actors)
    {
        for(Actor a2: actors)
        {
            if(a1 == a2)
                continue;
            if(collides(a1,a2))
            {
               a1.collideWith(a2);
               a2.collideWith(a1);
            }
        }
    }
}

private static void doLogics(long delta)
{
    for(Actor a : actors)
    {
       a.doLogic(delta);
    }
}

in moveobjects werden einfach nur ein paar koordinaten umgestzt,
bei check collisions wird geguckt ob mit den neuen koordinaten kollisionen entstehen und wenn ja wird gegenseitig collideWith aufgerufen...
Dazu noch ne frage (mit dem collide with):
Alle "actors" erben von der abstrakten Basisklasse actor und werden darüber angesprochen.
Beim kollidieren muss man aber sehr stark unterscheiden, mit was man da kollidiert.
Eine möglichkeit (bei java) wäre sowas in der art:

if(a instanceof BoeserGegnerXY)
{
   //spezialbehandlung für BoeserGegnerXY
}

if(a instanceof Z)
{
   //spezialbehandlung für Z
}

Gibt es da evtl. bessere ansätze?
Habe gehört, dass sowas mit instanceof kein guter stil ist, aber ich weiß nicht wirklich, wie man es besser machen kann...

Hoffentlich habt ihr noch ein paar hilfreiche Beiträge für mich

rapso

for(Actor a1 : actors)
        for(Actor a2: actors)
        {
            if(a1 == a2)
                continue;
            if(collides(a1,a2))
            {
               a1.collideWith(a2);
               a2.collideWith(a1);
            }
        }

die zeitkritischste stelle
versuch sowas wie

for(a0=start to end-1)
for(a1=a0+1 to end)
if(collides(a0,a1))
...

mit steigender anzahl der objekte steigt es mit Anzahl*log(Anzahl) statt Anzahl*Anzahl, bei 100 objekten also 10x schneller.

danke, schonmal guter verbesserungsvorschlag!

Weiß vll noch wer ne alternative zu dem instanceof zeugs, oder einfach paar allgemeine tipps?

volkard

rapso schrieb:

versuch sowas wie
for(a0=start to end-1)
for(a1=a0+1 to end)
if(collides(a0,a1))
...
mit steigender anzahl der objekte steigt es mit Anzahl*log(Anzahl) statt Anzahl*Anzahl, bei 100 objekten also 10x schneller.

Nö. Nur 2-mal so schnell wie zuvor. Mit steigender Anzahl noch genauer 2-mal.

Die formel müsste doch (n*(n-1))/2 sein, oder?
Aber ist ja auch nicht so wichtig^^
Mir gehts eher um konzeptionelle sachen und das war schon nen guter tipp...

Cpp_Junky

Dazu unterteilst du die Welt in kleinere Einheiten und checkst nur noch Objekte die sich in der selben "Gegend" befinden

Jo, das ist sicherlich ne gute idee, die welt in so kacheln einzuteilen und dann immer nur per kachel nach kollisionen zu prüfen und auch den hintergrund kann man ja so gut einteilen.
Ich stelle mir das dann so vor, dass ich zu jeder kachel eine liste von elementen habe, die sich in der kachel befinden und dann innerhalb der kachel auf kollisionen prüfe.
Ich sehe da allerdings noch ein problem, was mache ich, wenn ein element genau auf der grenze zwischen zwei (oder sogar mehr) kacheln ist, also z.B. zur hälfte links und zur hälfte rechts drin... ?
Muss das element dann in beiden listen drin sein, oder wie würde man das umsetzen?

Gut wäre auch noch, wenn ihr noch was zu der sache mit instanceof (siehe seite 1) sagen könnt

Vielen Dank schonmal für weitere Antworten!

Cpp_Junky

Jo, du musst das Objekt abhängig von seiner Größe ggf. bei mehreren Bereichen "anmelden" und wenn es sich bewegt evtl wieder "abmelden". Je grösser die Bereiche sind desto weniger An/Abmelde-Aufwand hast du, aber desto zeitintesiver wird die Prüfung (da die Anzahl der Objekte im selben Bereich steigt). Am besten alles schön dynamisch aufbauen, so das du die Bereichsgrösse variieren kannst um das perfekte Verhältnis zu finden. Wenn man einen Quadtree/Octree oder sowas verwendet, bieten sich diese Strukturen natürlich als Speicherort an.

hustbaer

Gast1337 schrieb:

Ich sehe da allerdings noch ein problem, was mache ich, wenn ein element genau auf der grenze zwischen zwei (oder sogar mehr) kacheln ist, also z.B. zur hälfte links und zur hälfte rechts drin... ?
Muss das element dann in beiden listen drin sein, oder wie würde man das umsetzen?

Das wird unterschiedlich gemacht.
Entweder so wie du schreibst, also jedes Objekt in jede Kachel eintragen mit der es sich überschneidet.

Die zweite Variante ist, das Objekt nur in die Kachel einzutragen die unter dem Mittelpunkt des Objekts liegt. Beim Prüfen auf Kollisionen nimmt man dann alle Objekte die einer Kachel liegen, und prüft sie dann gegen sich selbst sowie die Objekte die in den umliegenden 8 Kacheln liegen. Die Grösse der Objekte darf dabei allerdings 2x2 Kacheln nicht übersteigen.

Das mit den Kacheln (Grid) hört sich gut an, nur leider legt es eine obere Grenze für die Größe von Objekten fest, kann man das irgendwie in guter Weise modifizieren, so das das nicht der Fall ist?
Was mir einfällt ist man testtet, ob es in 9 kacheln reinpasst (die wos reinkommt und die umliegenden) und wenn nicht, dann kommt es in eine seperate liste, in der alles gespeichert wird, was nicht in die kacheln reinpasst.

Ansonsten hab ich nochmal nen bischen was übern quadtree gelesen, klingt interessant und vermutlich auch effizient, aber ich vermute, dass es sehr aufwändig wird und bei wiki stand was von das die fläche auf die das angewendet wird rechteckig sein sollte/muss (warum auch immer)?

Falls wer nen gutes Tutorial in die Richtung kennt - für einen Link wäre ich dankbar.

Cpp_Junky

Gast1337 schrieb:

Das mit den Kacheln (Grid) hört sich gut an, nur leider legt es eine obere Grenze für die Größe von Objekten fest, kann man das irgendwie in guter Weise modifizieren, so das das nicht der Fall ist?

Mach dir eine quadratische Bounding Box für jedes Objekt. Das Ding muss sich darin noch drehen können, falls du das willst - Falls nicht, brauch die Box nicht unbedingt quadratisch sein. Dann nimmst du dir den Punkt oben Links und den Punkt unten Rechts und berechnest, welche Tiles dazwischenliegen. Dort machst du das Objekt dann bekannt, oder eben auch nicht.

Ansonsten hab ich nochmal nen bischen was übern quadtree gelesen, klingt interessant und vermutlich auch effizient, aber ich vermute, dass es sehr aufwändig wird und bei wiki stand was von das die fläche auf die das angewendet wird rechteckig sein sollte/muss (warum auch immer)?

Für was willst du den Quadtree denn verwenden? Grundsätzlich ist es egal, welche Abmessungen das Ding hat. Man nimmt aber gerne z.B. eine 2er Potenz, weil dann jeder Teilbereich eine glatte Zahl ist (64,32,16,8 usw) und sich vielleicht irgenwelche Rechentricks anwenden lassen.

hustbaer

Gast1337 schrieb:

Das mit den Kacheln (Grid) hört sich gut an, nur leider legt es eine obere Grenze für die Größe von Objekten fest, kann man das irgendwie in guter Weise modifizieren, so das das nicht der Fall ist?

Nein, tut es nicht. Wenn du die Objekte in alle Kacheln einträgst mit denen sie sich überschneiden dann gibt es keine Obergrenze für die Grösse.

Was mir einfällt ist man testtet, ob es in 9 kacheln reinpasst (die wos reinkommt und die umliegenden) und wenn nicht, dann kommt es in eine seperate liste, in der alles gespeichert wird, was nicht in die kacheln reinpasst.

Ja, auch eine Möglichkeit - vermutlich sogar eine gute.