Kollisionen

Steht die Figur an der Wand? Trifft der Pfeil? Das Spiel muss in jedem Bild herausfinden, welche Objekte sich berühren. Genau prüfen ist teuer, also wird geschickt vereinfacht.

Hüllkörper statt Dreiecke

Zwei Figuren mit je 20 000 Dreiecken exakt zu vergleichen, hieße im schlimmsten Fall 20 000 · 20 000 = 400 Millionen Dreieckspaare zu testen. Stattdessen bekommt jedes Objekt einen einfachen Hüllkörper, der es ganz umschließt: einen Quader, dessen Kanten parallel zu den Achsen liegen, oder eine Kugel.

Ein solcher Quader ist durch zwei Punkte bestimmt, die Ecke mit den kleinsten und die Ecke mit den größten Koordinaten:

quader = [[-1, 0, -1], [1, 2, 1]]      # [kleinste Ecke, größte Ecke]

Der Überlappungstest

In einer Dimension ist ein Quader ein Intervall. Zwei Intervalle überlappen, wenn jedes beginnt, bevor das andere endet. Zwei Quader überlappen genau dann, wenn das auf allen drei Achsen gilt. Findet sich eine Achse, auf der die Intervalle getrennt sind, gibt es keinen Treffer.

def ueberlappt(a, b):
    for achse in range(3):                      # 0 = x, 1 = y, 2 = z
        if a[1][achse] < b[0][achse] or b[1][achse] < a[0][achse]:
            return False                        # auf dieser Achse getrennt
    return True

Verschiebe den zweiten Quader. Erst wenn alle drei Achsen „überlappt“ melden, ist es ein Treffer. Der Test kostet höchstens sechs Vergleiche, unabhängig davon, wie viele Dreiecke die Figuren haben.

Kugeln

Zwei Kugeln berühren sich, wenn der Abstand ihrer Mittelpunkte höchstens so groß ist wie die Summe der Radien. Die Wurzel aus der Abstandsformel kann man sich sparen, indem man beide Seiten quadriert:

def kugeln_beruehren(m1, r1, m2, r2):
    dx, dy, dz = m2[0] - m1[0], m2[1] - m1[1], m2[2] - m1[2]
    return dx*dx + dy*dy + dz*dz <= (r1 + r2) ** 2

Grob, dann genau

Ein Hüllkörper ist größer als die Figur. Er kann einen Treffer melden, obwohl sich die Figuren nicht berühren, aber nie einen übersehen. Spiele prüfen deshalb in zwei Phasen: erst grob mit Hüllkörpern, und nur bei den wenigen gemeldeten Paaren genauer, etwa mit mehreren kleinen Hüllkörpern für Kopf, Rumpf und Arme.

Das eigentliche Problem: zu viele Paare

Der einzelne Test ist billig. Teuer wird die Anzahl. Wer jedes Objekt mit jedem anderen vergleicht, braucht bei n Objekten n · (n − 1) ÷ 2 Tests:

for i in range(n):
    for j in range(i + 1, n):
        if ueberlappt(huelle[i], huelle[j]):
            melde_kollision(i, j)

Der Aufwand wächst quadratisch, O(n²). Zehnmal so viele Objekte bedeuten hundertmal so viele Tests.

Die Lösung: ein Raster

Objekte, die weit auseinanderliegen, können sich nicht berühren. Man teilt die Welt deshalb in Zellen und merkt sich für jede Zelle, welche Objekte darin liegen. Getestet wird ein Objekt nur noch gegen die Objekte in seiner eigenen und den benachbarten Zellen.

zellen = {}                                         # Wörterbuch: Zelle -> Liste von Objekten
for i in range(n):
    zelle = (int(x[i] // g), int(y[i] // g))        # g = Zellengröße
    zellen.setdefault(zelle, []).append(i)

for i in range(n):
    zx, zy = int(x[i] // g), int(y[i] // g)
    for nx in (zx - 1, zx, zx + 1):
        for ny in (zy - 1, zy, zy + 1):
            for j in zellen.get((nx, ny), []):
                if j > i:
                    teste(i, j)

Sind die Objekte gleichmäßig verteilt, liegen in jeder Zelle nur wenige. Der Aufwand wächst dann annähernd linear mit n. Das Einsortieren kostet einen Durchlauf über alle Objekte, also O(n).