Collision Detection mit Spatial Hash Maps

Was sind Spatial-Hash-Maps lassen sich wie folgt zusammenfassen.

Spatial-Hash-Maps sind ein Prozess in die Verteilung in einem 3D- oder 2D-Raum auf einen 1D-Hash-Table projiziert werden.

Wozu benötigt man das?

Wie dem Titel zu entnehmen sind Spatial-Hash-Maps eine einfache und effiziente Lösung, um Kollisionen zwischen einer großen Anzahl an Objekten zu erkennen.

Soll für ein beliebiges Objekt im Raum überprüft werden, ob es mit anderen kollidiert, ist ein gängiger Brute-Force-Ansatz, die Distanz zu jedem Objekt im Raum zu berechnen und die Objekte zurückgeben, wessen Abstände unter einem festgelegten Wert. Will man nun die Kollisionen aller n Objekte pro Frame berechnen müssen wäre der Aufwand pro Frame O(n2). Mit jedem weiteren Objekt steigt der Aufwand exponentiell.

Besonders für Einsatzfälle wie RTS-Spiele, in welchen mit großen Anzahlen von Einheiten gehandhabt werden muss, ist dieser Ansatz nicht geeignet. An diesem Punkt kommen die Spatial-Hash-Maps in's Spiel.

Das Grundprinzip

Stellt man sich einen 2D-Raum vor – 100 x 100 Einheiten – jede Zelle hat eine breite von 25 Einheiten. Die Größe der Zellen definiert sozusagen unsere Auflösung, für die Kollisions-Erkennung.

Würde man diese Zellen von links oben nach rechts unten durchnummerieren und die Objekte in diese Zellen einsortieren, lassen sie sich als eindimensionale Liste darstellen. Dort wird deutlich, dass die Erkennung, ob Objekte kollidieren schnell überprüft werden kann. Objekte in Zelle 2 können unmöglich mit Objekten in Zelle 4 kollidieren. Das Überprüfen einer Kollision hätte somit einen Aufwand von O(1).

Die eindimensionale Liste und das Einfügen der Objekte in diese Liste ist der Kernaspekt der Spatial-Hash-Maps. Die 2D-Koordinaten eines Objekts wird mittels einer Hash-Funktion auf einen Index der Hash-Map gemapped und somit eingefügt. Im Gegensatz zu herkömmlichen Hash-Sets, bei denen man versucht die Einträge über die Liste zu verteilen, versuchen Spatial-Hash-Maps den Spatial-Aspekt beizubehalten und eine räumliche Distanz zu wahren.

Flächendeckende Kollision

Was aber, wenn Objekte den Raum betreten, welche größer sind als eine Einheit. Somit bestünde die Möglichkeit, dass ein Objekt in zwei Zellen gleichzeitig ist.

Um diesen Fall mit zu berücksichtigen, müssen die vier Punkte der Bounding-Box berücksichtig werden. Die Bounding-Box kann jede geometrische Form einnehmen. In diesem Fall sei angenommen, es handelt sich um ein Quadrat. In diesem Fall würde für jeden der vier Eckpunkte den Hash-Wert berechnen und das Objekt in jeden der Zellen schreiben, sofern es nicht schon dort gespeichert wurde.

Dieser Ansatz funktioniert allerdings nicht, sollte das Objekt größer werden, als eine Zelle. An dieser Stelle müsste bei einer quadratischen Bounding-Box an jeder Kante ein interpolierter Mittelwert plus einen Mittelpunkt berücksichtigt werden. Damit würde sichergestellt, dass das Objekt nicht eine gesamte Zelle "überspannen" kann.

Einheitenbewegung

Interessant bei dem Aufwand des Brute-Force-Ansatzes und der Spatial-Hash-Maps ist, dass bisher nicht über das Aktualisieren der Einheitenpositionen geredet wurde. Hierbei wäre der Aufwand für den Brute-Force-Ansatz 0 da keine Datenstruktur existiert, die für die Kollisions-Erkennung benutzt wird. Die Einheiten bewegen sich und haben keinen Einfluss auf die Berechnung an sich. Der Aufwand, um die Spatial-Hash-Map auf die Einheitenbewegung aktualisiert wird, liegt bei O(n). Für jede Einheit müssen die Hash-Werte neu berechnet werden, die Zellen neu gefüllt.

Zusammenfassend wäre der Aufwand der Spatial-Hash-Map trotzdem sehr viel effizienter, auch wenn das Aktualisieren im Vergleich aufwändiger ist.