Sortieren, Sweep und Pruning: Collision-Detection-Algorithmen (2023)

 (leanrada.com)
3 Punkte von GN⁺ 2024-08-15 | 1 Kommentare | Auf WhatsApp teilen

Algorithmen zur Kollisionserkennung

Kollisionserkennung

  • In der Videospielprogrammierung ist Kollisionserkennung ein sehr häufiges Problem
  • Sie ist unverzichtbar, damit Charaktere nicht durcheinander hindurchgehen und um eine Physik-Engine zu implementieren

Einfacher Ansatz 🐥

  • Eine Methode, bei der jedes Objektpaar geprüft wird, um festzustellen, ob eine Kollision vorliegt
  • Codebeispiel: 
    for (let i = 0; i < balls.length; i++) {
  const ball1 = balls[i];
  for (let j = i + 1; j < balls.length; j++) {
    const ball2 = balls[j];
    if (intersects(ball1, ball2)) {
      bounce(ball1, ball2);
    }
  }
}
  • Diese Methode hat eine Zeitkomplexität von O(n^2)

Performance-Probleme

  • Je mehr Objekte es gibt, desto eher treten Performance-Probleme auf
  • Zum Beispiel müssen bei n = 20 insgesamt 190 Paare geprüft werden

Verbesserte Lösung

  • Es ist wichtig, unnötige Arbeit zu reduzieren
  • Optimierung der Funktion intersects(): 
    function intersects(object1, object2) {
  return object1.left < object2.right &&
         object1.right > object2.left &&
         object1.top < object2.bottom &&
         object1.bottom > object2.top;
}

Optimierung durch Sortieren

  • Wenn die Objekte nach ihren x-Koordinaten sortiert werden, lassen sich unnötige Prüfungen reduzieren
  • Codebeispiel: 
    sortByLeft(balls);
for (let i = 0; i < balls.length; i++) {
  const ball1 = balls[i];
  for (let j = i + 1; j < balls.length; j++) {
    const ball2 = balls[j];
    if (ball2.left > ball1.right) break;
    if (intersects(ball1, ball2)) {
      bounce(ball1, ball2);
    }
  }
}

Performance-Analyse

  • Sortieren: O(n log n)
  • Innere Schleife: im Durchschnitt O(n + m) (m ist die Gesamtzahl der Überlappungen auf der x-Achse)
  • Endgültige Zeitkomplexität: O(n log n + m)

Visueller Vergleich

  • Vergleich zwischen globaler Paarprüfung und sortierter Paarprüfung
  • Die sortierte Paarprüfung führt deutlich weniger Prüfungen aus

Zusammenfassung von GN⁺

  • Dieser Artikel behandelt, wie sich Algorithmen zur Kollisionserkennung in der Spieleentwicklung optimieren lassen
  • Er beginnt mit einem einfachen O(n^2)-Algorithmus und verbessert die Performance durch Sortierung deutlich
  • Sehr nützliche Informationen für Spieleentwickler oder Softwareingenieure
  • Andere Projekte mit ähnlicher Funktionalität sind unter anderem Box2D und Bullet Physics

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2024-08-15
Hacker-News-Kommentare

  • Der Autor schlägt vor, für optimale Leistung „schnelle“ Sortieralgorithmen wie Mergesort oder Quicksort zu verwenden.

    • In der Praxis können jedoch „weniger gute“ Sortieralgorithmen wie Insertion Sort eine bessere Leistung zeigen.
    • Die Objekte eines Collision-Detection-Systems bewegen sich zwischen Frames relativ nur in kleinen Schritten, sodass eine aus dem vorherigen Frame stammende, nahezu sortierte Liste beibehalten werden kann.
    • Beim Sortieren einer solchen nahezu sortierten Liste liegt Insertion Sort nahe bei O(n), während Quicksort eher in die Nähe von O(n^2) kommt.

  • Ich habe in der Vergangenheit etwas Ähnliches gemacht, aber statt zu sortieren eine Indexliste für jede Richtung gepflegt.

    • Zum Beispiel vier Listen wie objectIndicesSortedByLeftEdge/RightEdge/TopEdge/BottomEdge.
    • Wenn sich ein Objekt horizontal bewegt, aktualisiert es seinen Index in den Arrays leftEdge und rightEdge.
    • Während der Bewegung müssen höchstens 1–2 Indizes vertauscht werden.

  • Dieser Artikel ist wirklich gut aufbereitet.

    • Ich entwickle seit Ende der 90er Jahre Spiele, aber der Großteil dieser Arbeit wird normalerweise von der Engine abstrahiert.
    • Für das Verständnis komplexer Systemsimulationen ist das essenziell.
    • Danke an den Autor, dass er einen so zugänglichen Artikel geschrieben hat.

  • Ich lese Dokumentationen zur kontinuierlichen Kollisionserkennung immer gern.

  • Der Einsatz von Illustrationen war gut.

    • Manchmal wirken solche Artikel wie ein Vorwand, um coole Demos zusammenzustellen, aber in diesem Fall stehen die Illustrationen nicht im Vordergrund.

  • Teil 2: https://leanrada.com/notes/sweep-and-prune-2/

  • Ich stelle die Aussage infrage: „Dieser einfache Algorithmus läuft in O(n^2) Zeit in Big-O-Begriffen“.

    • Die äußere Schleife (i) zählt bis n - 1, und die innere Schleife (j) beginnt bei i + 1 und durchläuft jedes Mal weniger Elemente.
    • Ich habe keinen CS-Abschluss, frage mich aber, ob das für große n ungefähr dasselbe wie O(n^2) ist oder ob es weniger ist.

  • Ich habe mich gefragt, ob diese Methode dem Einsatz eines Quadtrees ähnelt, um potenzielle Kollisionen zu reduzieren.

  • Ich habe mich gefragt, ob jemals ein Linear-Programming-Ansatz vorgeschlagen wurde.

  • Ich habe mich auf dieser Website im positiven Sinne verzettelt.

    • Sie ist unterhaltsam und inspirierend.