Kollisionserkennung war in meinem MMBasic-Spiel einer der Punkte, an denen ich tatsächlich gemessen habe, was sich lohnt und was nicht. Zwei Erkenntnisse haben sich dabei gefestigt: SQR braucht es nicht, und das schicke Spatial-Grid gewinnt nicht automatisch gegen die einfache Doppelschleife.

SQR sparen

Die klassische Frage „berühren sich zwei Kreise" lässt sich elegant ohne Wurzel beantworten. Statt den Abstand auszurechnen und mit der Summe der Radien zu vergleichen, vergleicht man die quadrierten Werte. Mathematisch ist es das Gleiche, der Rechner spart die SQR-Operation.

dx = ax(i) - ax(j)
dy = ay(i) - ay(j)
r  = asize(i) + asize(j)

IF dx*dx + dy*dy < r*r THEN
  ' Kollision
END IF

Klingt nach Mikrokosmos, aber wenn das pro Frame für jedes Paar in einer doppelten Schleife läuft, ist das spürbar.

Bounding-Box-Pre-Check vs Squared-Distance

In meinem Code hatte ich erst einen Pre-Check mit ABS(dx) < r AND ABS(dy) < r. Die Idee dahinter: wenn schon das Bounding-Box-Rechteck nicht überlappt, brauche ich die richtige Kollision gar nicht zu rechnen.

IF ABS(dx) < r AND ABS(dy) < r THEN
  CheckCollision(i, j)
END IF

Funktioniert, aber jeder ABS-Aufruf kostet auch etwas. Beim Refactoring habe ich den Pre-Check direkt durch den Squared-Distance-Vergleich ersetzt, weil der ohne SQR auskommt und für den ungenauen ersten Filter völlig reicht.

IF dx*dx + dy*dy < r*r THEN
  CheckCollision(i, j)
END IF

Bei mir war das die schnellere Variante. Ich glaube, das liegt daran, dass ABS im Interpreter teurer ist als die Multiplikation mit sich selbst, aber nageln will ich mich darauf nicht.

Spatial-Grid lohnt nicht immer

Der nächste Reflex war, ein Spatial-Grid einzubauen. Bildschirm in 100×100-Pixel-Zellen aufteilen, jeden Asteroiden in seine Zelle einsortieren, nur Nachbarn prüfen. Klingt schön nach Lehrbuch.

Ich habe es gebaut und gegen die simple O(n²)-Variante gemessen, mit 50 Asteroiden über 1000 Iterationen. Das Ergebnis war für mich unerwartet: bei den Größenordnungen, die in einem Asteroids-Klon vorkommen, war der Overhead vom Grid-Aufbau in jeder Iteration größer als die Ersparnis bei den Vergleichen. Erst bei deutlich mehr Objekten kippt das.

Was ich daraus mitgenommen habe: bevor ich eine schicke Datenstruktur einbaue, messe ich erst. In einem Spiel mit ein paar Dutzend Objekten reicht der direkte O(n²)-Loop mit Squared-Distance-Pre-Check. Spatial-Grids und Quadtrees sind Werkzeuge für Größenordnungen, die ein Vektor-Spiel auf einem CMM2 selten erreicht.

FOR i = 0 TO max_obj - 1
  IF aactive(i) THEN
    FOR j = i + 1 TO max_obj - 1
      IF aactive(j) THEN
        dx = ax(j) - ax(i)
        dy = ay(j) - ay(i)
        r  = asize(i) + asize(j)
        IF dx*dx + dy*dy < r*r THEN
          CheckCollision(i, j)
        END IF
      END IF
    NEXT j
  END IF
NEXT i

Genau dieser Loop läuft bei mir im Spiel produktiv, und er hält die 60 fps locker.