Sortieren, Sweepen, Pruning: Algorithmen zur Kollisionserkennung (2023)

• Der Artikel erklärt anhand einer Ballsimulation die in der Spielephysik immer wieder benötigte Kollisionserkennung und den Optimierungsweg von der Prüfung aller Paare hin zu Sweep-and-Prune
• Der einfache Ansatz ruft für jedes Kandidatenpaar aus n Objekten intersects() auf und führt damit etwa (n*(n-1))/2 Prüfungen aus, wächst also schnell mit O(n²)
• Ein AABB-Schnitttest besteht aus mehreren Ungleichungen und &&; mithilfe von Kurzschlussauswertung und der Transitivität von Ungleichungen lassen sich Kandidaten ohne Kollisionsmöglichkeit früh verwerfen
• Nachdem die Objekte nach ihrer linken Begrenzung, also minimum x, sortiert wurden, kann die innere Schleife in dem Moment mit break beendet werden, in dem ball2.left > ball1.right gilt; alle folgenden Kandidaten werden damit auf einmal ausgeschlossen
• Zu den Sortierkosten von O(n log n) kommen Schleifenkosten in Höhe der Anzahl m der Überlappungen auf der x-Achse hinzu; im Mittel ergibt sich etwa O(n log n + m), wodurch unnötige intersects()-Aufrufe stark reduziert werden

---

Ausgangspunkt der Kollisionserkennung in Spielen

• Kollisionserkennung ist in der Videospielprogrammierung Voraussetzung für viele Verhaltensweisen
  • Sie verhindert, dass Figuren einander durchdringen
  • Ein Goomba ändert die Richtung, wenn er gegen ein anderes Objekt stößt
  • In agar.io frisst eine große Zelle eine kleine Zelle bei Berührung
  • Allgemeine Spielephysik wird verarbeitet
• Das Beispiel nutzt eine Rigid-Body-Ballsimulation, um verschiedene Ansätze zur Kollisionserkennung zu vergleichen
• Der Umfang reicht vom einfachsten Verfahren bis hin zu Sweep-and-Prune; räumliche Partitionierung oder die Verfeinerung über Spatial Trees sind ausgenommen

Einfacher Ansatz: alle Paare prüfen

• Die direkteste Methode betrachtet alle Objektpaare als Kandidaten
  • Die äußere Schleife iteriert über jeden Ball
  • Die innere Schleife beginnt bei i + 1, um doppelte Paare wie A-B und B-A zu vermeiden
  • Für jedes Kandidatenpaar wird intersects(ball1, ball2) aufgerufen; bei wahr wird bounce(ball1, ball2) ausgeführt
• Diese Prüfung wird bei jedem Zeitschritt wiederholt, sodass der Ball im Moment der Kollision abprallt
• Bei wenigen Objekten reicht das aus, doch mit wachsender Anzahl wird die Prüfmenge schnell zum Performance-Engpass

Die Grenzen von O(n²)

• Der einfache Algorithmus läuft in Big-O-Notation in O(n²) Zeit
• Für n Bälle müssen ungefähr (n*(n-1))/2, also 0.5n² - 0.5n, Paare geprüft werden
  • Bei n = 5 sind es 10 Paare
  • Bei n = 10 sind es 45 Paare
  • Bei n = 15 sind es 105 Paare
  • Bei n = 20 sind es 190 Paare
• Im Worst Case, wenn alle Objekte gleichzeitig überlappen, kann kaum ein Algorithmus zur Kollisionserkennung eine Kollisionsverarbeitung von O(n²) vermeiden
• In der Praxis sind Durchschnitts- und Best-Case-Fälle relevanter als der Worst Case
• Der einfache Ansatz arbeitet unabhängig von der tatsächlichen Zahl der Kollisionen immer mit Θ(n²) und bietet daher viel Verbesserungspotenzial

Wiederholte Arbeit in intersects()

• Ausgangspunkt der Optimierung ist die Funktion intersects(), die für jedes Kandidatenpaar aufgerufen wird
• Ein typischer AABB-Schnitttest besteht aus mehreren Ungleichheitsprüfungen, die die Grenzen in jeder Richtung vergleichen

function intersects(object1, object2) {
  // compare objects' bounds to see if they overlap
  return object1.left < object2.right
      && object1.right > object2.left
      && object1.top < object2.bottom
      && object1.bottom > object2.top;
}

• Diese Prüfung zerfällt in vier Bedingungen
  • object1.left < object2.right
  • object1.right > object2.left
  • object1.top < object2.bottom
  • object1.bottom > object2.top
• Wegen der Kurzschlussauswertung von && wird der gesamte Schnitttest sofort falsch, sobald auch nur eine Bedingung falsch ist
• Wenn man den Fall „mindestens eine Bedingung ist falsch“ über mehrere Tests hinweg verallgemeinert, lässt sich die Zahl der intersects()-Aufrufe selbst reduzieren
• Das entspricht der Idee des Separating Axis Theorem: Wenn sich die Projektionen auf einer Achse nicht überlappen, kollidieren die beiden Objekte nicht

Kandidaten per Transitivität von Ungleichungen verwerfen

• Schon die einzelne Bedingung object1.right > object2.left bietet Optimierungsspielraum
• Wenn drei Objekte A, B und C horizontal in der Reihenfolge A-B-C angeordnet sind, können die folgenden Prüfungen alle falsch sein

A.right > B.left // returns false
B.right > C.left // returns false
A.right > C.left // returns false

• Ist A > B falsch und B > C falsch, folgt aus der Transitivität von Ungleichungen, dass auch A > C falsch ist
• Daher lässt sich ohne Aufruf von intersects(A, C) feststellen, dass die beiden Objekte nicht kollidieren
• Diese Auslassung gilt nur, wenn die Objekte in einer bestimmten Reihenfolge stehen; da Objektlabels aber beliebig sind, kann man einfach das linke Objekt A, das mittlere B und das rechte C nennen
• Die Anordnung der Objekte in dieser logischen Reihenfolge ist genau das Sortieren

Sortieren nach dem Minimalwert auf der x-Achse

• Eine sortierte Liste ermöglicht es, die Transitivität von Ungleichungen auf viele Kandidaten zugleich anzuwenden
• Übliche schnelle Sortieralgorithmen haben O(n log n) und liegen damit unter O(n²)
• Da Objekte keine Punkte sind, sondern Intervalle auf der x-Achse einnehmen, verwendet man für die Sortierung nach x-Position die linke Begrenzung, also minimum x
• Am einfachen O(n²)-Code sind zwei Änderungen nötig
  • Vor den Schleifen werden die Bälle mit sortByLeft(balls) nach der x-Koordinate der linken Begrenzung sortiert
  • In der inneren Schleife wird bei ball2.left > ball1.right ein break ausgeführt

// sort by min x
sortByLeft(balls);

// for each ball
for (let i = 0; i < balls.length; i++) {
  const ball1 = balls[i];
  // check each of the other balls
  for (let j = i + 1; j < balls.length; j++) {
    const ball2 = balls[j];

    // stop when too far away
    if (ball2.left > ball1.right) break;

    // check for collision
    if (intersects(ball1, ball2)) {
      bounce(ball1, ball2);
    }
  }
}

• Die Sortierfunktion sortiert das Array nach der Differenz der linken Begrenzungen

function sortByLeft(balls) {
  balls.sort((a,b) => a.left - b.left);
}

Warum break sicher ist

• Wenn die Liste sortiert ist, gilt für jede beliebige positive ganze Zahl c die folgende Beziehung

balls[j + c].left >= balls[j].left

• Wenn der aktuelle Kandidat die folgende Bedingung erfüllt, überlappt das aktuelle Paar auf der x-Achse nicht

balls[j].left > ball1.right

• Kombiniert man beide Ungleichungen, ergibt sich folgende Beziehung

balls[j + c].left >= balls[j].left > ball1.right

• Aufgrund der Transitivität gilt auch balls[j + c].left > ball1.right; daher überlappen auch alle folgenden Kandidaten nicht mit dem aktuellen ball1 auf der x-Achse
• Sobald der aktuelle ball2 nicht mehr mit ball1 überlappt, kann der Rest der inneren Schleife ohne weitere Prüfungen abgebrochen werden
• Diese Optimierung beschränkt die tatsächlichen intersects()-Aufrufe auf Paare, die auf der x-Achse überlappen

Verbesserte Zeitkomplexität

• Die Sortierkosten fügen, bei schnellen Sortierverfahren wie Mergesort oder Quicksort, einen Term von O(n log n) hinzu
• Die doppelte Schleife mit frühem Abbruch lässt sich im Mittel als O(n + m) betrachten
  • m ist die Gesamtzahl der Überlappungen auf der x-Achse
  • Im Best Case gibt es keine Überlappungen; dann fällt kaum unnötige Arbeit an und die Laufzeit liegt nahe bei O(n)
  • Im Worst Case kann sie weiterhin auf O(n²) anwachsen
• Der Durchschnittsfall setzt voraus, dass die Objekte insgesamt gleichmäßig verteilt sind und pro Objekt nur wenige Kollisionen auftreten
• Insgesamt ergibt sich für Sortierung und Schleifen zusammen O(n log n + m)
• Der Ansatz ist aus zwei Gründen besser als das einfache Verfahren
  • n log n ist kleiner als n²
  • Er hängt teilweise von der Zahl der Überlappungen m ab und verarbeitet daher nicht mehr als nötig

Implementierungsaufwand und nächste Schritte

• Dieser sortierbasierte Ansatz ist ein guter Kompromiss: wenige Codeänderungen bei deutlich besserer Laufzeit-Performance
• In der Vergleichsdemo reduziert die sortierbasierte Paarprüfung die Zahl der intersects()-Tests pro Frame im Vergleich zur globalen Prüfung aller Paare sichtbar
• Die Sortierkosten werden in der Vergleichsvisualisierung nicht angezeigt; vorausgesetzt wird jedoch, dass die Schnitttests hinreichend teuer sind
• Weiterführende Ansätze und der finale Code folgen in Part 2

[GN⁺]

Meinungen auf Hacker News

• Interessant an diesem Ansatz ist, dass der Autor vorschlägt, für maximale Performance „schnelle“ Sortieralgorithmen wie Merge Sort/Quick Sort zu verwenden.
  In der Praxis kann aber ein „schlechterer“ Sortieralgorithmus, nämlich Insertion Sort, schneller sein.
  Die Objekte in einem Kollisionserkennungssystem bewegen sich zwischen Frames normalerweise nur ein wenig, sodass man die fast sortierte Liste aus dem vorherigen Frame beibehalten kann.
  Auf solchen Listen nähert sich Insertion Sort O(n), während Quick Sort sich O(n^2) annähern kann.

  • Der Autor behandelt in Teil 2 fast genau denselben Punkt.
    Er erklärt sinngemäß: „Die Sortierphase ist in der Analyse der Engpass, aber die meiste Zeit tut das Sortieren gar nichts. Die Liste ist fast immer schon aus dem vorherigen Frame sortiert. Selbst wenn die Sortierung kaputtgeht, ist sie normalerweise mit ein paar Vertauschungen wiederhergestellt. Hier ist ein Beispiel dafür, wie Insertion Sort arbeitet.“
  • Statt in jedem Schritt zu sortieren, kann man auch die Indexstruktur etwas lockerer machen und Kollisionskandidaten erfassen, wenn sich ein Objekt um weniger als Epsilon bewegt hat.
    Zum Beispiel kann man den Radius einer Kugel um Epsilon vergrößern.
    Solange sich die Kugel nicht um Epsilon bewegt hat, muss der Index nicht neu berechnet werden.
    Um Latenzspitzen beim notwendigen Neuberechnen zu vermeiden, kann man pro Frame 10 % sortieren und so einen hinterherhinkenden Index aufbauen.
    Nach 10 Frames hat man einen gültigen Index, solange die Position innerhalb von Epsilon zur Position vor 10 Frames liegt.
  • Dass Quick Sort auf einer fast sortierten Liste O(n^2) wird, passiert nur, wenn man den Pivot wirklich schlecht auswählt.
    Wählt man den Pivot zufällig, wird es O(n log n), und bei einer bereits fast sortierten Liste könnte man auch das mittlere Element der Liste als Pivot wählen.
    Allerdings ist Quick Sort selbst mit optimalem Pivot im Best Case O(n log n).
    Es gibt einfache Merge-Sort-Varianten, die O(n log k) laufen, wenn k die Anzahl der aufsteigenden/absteigenden Runs in den Daten ist.
    Das Standard-sort der Haskell-Standardbibliothek verwendet so einen Algorithmus, und bei Python dürfte es ähnlich sein.

• Der Artikel war sehr gut aufgebaut.
  Ich entwickle seit Ende der 90er in irgendeiner Form Spiele, und heute ist das meiste davon in Engines abstrahiert, aber solche Inhalte sind unerlässlich, um zu verstehen, wie Simulationen komplexer Systeme funktionieren.
  Danke an den Autor, dass er daraus einen zugänglichen Artikel gemacht hat.

• Beim Thema kontinuierliche Kollisionserkennung fand ich dieses Dokument immer gut: https://github.com/bepu/bepuphysics2/blob/master/Documentati...
  Auch die Library selbst ist in Sachen Performance hervorragend.
  Wegen der vielen Optimierungen ist sie allerdings etwas schwierig zu integrieren.

• Ich frage mich, ob die Aussage „Dieser naive Algorithmus läuft in Big-O-Termen in O(n2) Zeit“ stimmt.
  Die äußere Schleife i läuft n - 1-mal, und die innere Schleife j startet bei i + 1, läuft also nach und nach weniger als n - 1-mal, oder?
  Ich bin kein Informatiker und frage mich, ob man das bei großem n ungefähr als O(n2) ansieht oder ob es tatsächlich kleiner ist, wie es auf den ersten Blick wirkt.

  • Exakt n^2 ist es nicht.
    Für das i-te Element werden (n - i - 1) Vergleiche ausgeführt, und bei 0-basierter Indizierung ergibt sich insgesamt (n - 1) * n / 2 Vergleiche.
    Siehe https://en.wikipedia.org/wiki/Triangular_number.
    In der Big-O-Analyse macht das am Ende keinen Unterschied.
    Big O beschreibt das Verhalten, wenn n gegen unendlich geht, und dabei dominiert der quadratische Term.
  • Die „Optimierung“, die innere Schleife bei j = i + 1 beginnen zu lassen, dient dazu, nicht jedes Objektpaar zweimal zu prüfen.
    Außerdem verhindert sie, dass ein Objekt mit sich selbst geprüft wird.
    Da jedes Paar genau einmal geprüft wird, ist der Algorithmus O(n^2).
  • Big O ist lediglich eine Komplexitätsklassifikation, die beschreibt, wie die Anzahl abstrakter Operationen mit der Eingabegröße skaliert, also mit der Länge der Eingabeliste.
    Wenn man die Anzahl der Operationen allgemein analytisch als Funktion der Eingabegröße ausdrücken kann, behält Big O nur den größten Term und verwirft alle Koeffizienten.
    Es beschreibt nicht unbedingt die tatsächliche Performance eines Algorithmus.
    20n2^+5n und 2n^2 + 9001n sind beide O(n^2).
  • Es ist die Summe von 1 bis n, also n(n+1)/2.
    In der Big-O-Notation ignoriert man alle Koeffizienten und langsamer wachsenden Terme, daher reduziert sich das auf quadratische Komplexität.
  • Big O lässt sich vielleicht leichter verstehen, wenn man es ähnlich wie Grenzwertberechnungen in der Analysis betrachtet.

• Der Einsatz der Illustrationen war gut und wirkte angemessen.
  Manchmal fühlen sich Artikel mit interaktiven Illustrationen wie ein Vorwand an, möglichst viele coole Demos unterzubringen, und sie haben dann wie ein TED-Talk mehr Schmuck als Substanz.
  In diesem Artikel haben die Illustrationen den Inhalt aber nicht verdrängt.

• Teil 2: https://leanrada.com/notes/sweep-and-prune-2/
  Auch die anderen guten Artikel lohnen sich: https://leanrada.com/

• Vor langer Zeit habe ich etwas Ähnliches gemacht, aber statt zu sortieren habe ich pro Richtung Indexlisten gepflegt und die Objekte sich selbst einsortieren lassen.
  Zum Beispiel gibt es vier Listen wie objectIndicesSortedByLeftEdge/RightEdge/TopEdge/BottomEdge.
  Wenn sich ein Objekt horizontal bewegt, aktualisiert es seinen Index in den Arrays leftEdge und rightEdge.
  Denn selbst bei Bewegung reicht es meistens, nur ein oder zwei Indizes zu vertauschen.

  • Dieser Ansatz scheint vor allem für überwiegend statische Szenen nützlich zu sein.
    Je mehr dynamische Elemente hinzukommen, desto sinnvoller wirkt ein Ansatz, bei dem man den Graphen neu aufbaut.

• Ich sehe diesen Ansatz zum ersten Mal; ähnelt das nicht der Verwendung von etwas wie einem Quadtree, um die Zahl potenzieller Kollisionskörper zu reduzieren?

  • Ja.
    Allerdings sieht man Dinge wie k-d-Bäume eher beim Offline-Rendering als beim Echtzeit-Rendering.

• Mich interessiert die Stelle „Andere Ansätze wie räumliche Partitionierung oder Unterteilung in Raum-Bäume werde ich nicht behandeln“.
  Weiß jemand, ob der Algorithmus aus dem Artikel im Allgemeinen schneller ist als räumliche Partitionierung/Unterteilung in Raum-Bäume?
  Vor langer Zeit habe ich einen Ansatz mit Raum-Bäumen verwendet, und naiv betrachtet schien das ziemlich gut zu sein; aber das war in den 80ern vor dem Internet, daher habe ich nie recherchiert oder verglichen, welche Algorithmen andere nutzten.

  • Die Komplexität, räumliche Partitionierung oder Baumunterteilungen usw. zu pflegen, kann besonders bei sehr vielen beweglichen Objekten eine große Belastung sein.
    Eine einzelne Entity-Liste oder ein 256x256-Zellraster, in dem jede Zelle eine Entity-Liste enthält, zu verwalten, ist viel einfacher zu schreiben, zu debuggen und zu optimieren als eine komplexe Partitionierungsstruktur, bei der bei jeder Objektbewegung alle Bauminvarianten erhalten bleiben müssen.
    Zu Zeiten von DOOM oder Quake war die Performance solcher Basissysteme viel wichtiger als heute, daher war es für Engine-Autoren wohl sinnvoller, sehr komplexe Partitionierungssysteme zu bauen.
    Heutige CPUs sind sehr stark darin, sortierte Arrays zu durchlaufen, und wegen Pipelining ist das Verfolgen von verketteten Listen oder Bäumen relativ gesehen weniger vorteilhaft als früher.
    CPU-Zeit fließt heute eher in Dinge wie AI und Rendering als in die Verwaltung von Entity-Listen.