Was ist ein guter, einfacher Algorithmus zur Kollisionserkennung in 2D-Rechtecken?

Question

Ich entwerfe ein Tutorial zur Kollisionserkennung für junge Erwachsene, also möchte ich, dass es so einfach wie möglich ist, um es einfacher zu erklären.

Die Anforderungen sind sehr einfach. Die Welt ist 2D und enthält nur Rechtecke (beliebiger Größe). BSP und sogar Quadtrees scheint, als wäre es Overkill (wieder liegt die Betonung auf Einfachheit), aber ich hätte gerne etwas effizienteres als Brute-Forcing durch alle n (n-1)/2 möglichen Kollisionen.

2D, Rechtecke nur und einfach.

Kann jemand auf einen Algorithmus hinweisen, den ich nachschlagen kann? Ist ein Quadtree-Algorithmus, wonach ich suche?

EDIT: Auch die Rechtecke werden nie gedreht (ich halte es einfach). Und um Ihnen eine Vorstellung davon zu geben, in welchem ​​Umfang ich arbeite, wird es in der Größenordnung von ein paar hundert Rechtecken auf dem Laptop/Desktop Ihres typischen Benutzers (weniger als 5 Jahre alt) in Python mit Pygame implementiert sein.

Answer 1

Meiner Erfahrung nach sind alle Breitphasen-Kollisionserkennungsalgorithmen relativ subtil und schwer zu verstehen. Wenn man bedenkt, wie billig Rechteck-Kollisionstests sind, würde ich die Lektion mit dem n^2-Algorithmus strukturieren, dann als Bonus Material, vielleicht die Idee der räumlichen Indexierung einzuführen. Mit weniger als Hunderten von Rechtecken wette ich, dass der dumme Weg schnell genug ist.

Ein Quadtree wäre für Ihre Zwecke in Ordnung, aber denken Sie daran, dass Sie, wenn Sie mit Nichtpunkten arbeiten, das Rechteck in einen Knoten einfügen müssen, der alle Quadranten enthält, die es schneidet. Wenn Sie dann etwas testen, das sich in einem niedrigen Knoten befindet, müssen Sie mit allen Rezepten in diesem Knoten und in allen seinen Vorfahren testen!

Sie könnten auch einen Sortier- und Sweep-Algorithmus in Erwägung ziehen, da Sie bereits über Achsen ausgerichtete Bounding-Boxen verfügen.

Answer 2

Eine einfache Strategie, die auf einem einfachen 2D-Spiel Erkennung in einem frühen Versuch beschleunigt wurde eine Liste durch die längere Abmessung Kollisionsphase wie diese bestand aus etwas sortiert zu halten:

for i in 0..n 
    j = i+1 
    while rect[j].left < rect[i].right 
     check for collision in y 
     j=j+1 
    endwhile 
endfor 

Answer 3

Hier ist ein einfaches Algorithmus, der die Dinge ein wenig beschleunigt und achsenbündige Rechtecke bearbeitet.

Wählen Sie eine der Achsen als "sortierte Achse" aus. Für diese Beschreibung werde ich sagen, dass die X-Achse sortiert ist. Geben Sie jedes Rechteck als zwei Knoten an, einen Knoten "Enter" und einen Knoten "Exit" auf der sortierten Achse. Die Enter-Knoten müssen immer einen niedrigeren Wert auf der Achse haben als die Ausgangsknoten.

Erstellen Sie eine sortierte Liste aller Eingabe- und Ausgabepunkte.

Gehen Sie die sortierte Liste. Wenn Sie jeden "Enter" -Knoten drücken, fügen Sie ihn zu einer Liste von "eingegebenen" Rechtecken hinzu und führen Sie dann eine Brute-Force-Kollisionserkennung für alle anderen Knoten in der "Eingelesenen" -Liste durch. Wenn Sie jeden "Exit" -Knoten berühren, entfernen Sie ihn aus der Liste "Eingereicht".

Sie können den Leser dann durch eine Übung führen, in der die "eingegebene" Liste selbst auf der Y-Achse mit "Enter" und "Exit" -Punkten auf der Y-Achse sortiert ist.