Fast collision checks in MMBasic without a square root

Collision detection in my MMBasic game was one of the spots where I actually sat down and measured what was worth doing. Two takeaways stuck: you don’t need SQR, and the fancy spatial grid doesn’t automatically beat a plain nested loop.

Skip the SQR

The classic “do these two circles overlap” question has an elegant answer that doesn’t need a square root. Instead of computing the distance and comparing it to the sum of the radii, you compare the squared values. Mathematically the same thing, but the machine doesn’t have to call SQR.

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

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

Sounds like nitpicking, but once that runs in a nested loop every frame, it shows up.

Bounding box pre-check vs squared distance

I started with a pre-check using ABS(dx) < r AND ABS(dy) < r. The idea: if the bounding box rectangle doesn’t even overlap, skip the proper collision check entirely.

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

It works, but every ABS call has a cost too. When I refactored, I replaced the pre-check with the squared-distance comparison directly, since it avoids SQR and is precise enough as a coarse filter.

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

In my measurements that was the faster path. My guess is that ABS in the interpreter is more expensive than a multiplication of a value with itself, but I won’t pin myself to that.

A spatial grid isn’t always worth it

The next reflex was a spatial grid. Split the screen into 100×100-pixel cells, sort each asteroid into a cell, only check neighbours. Sounds textbook.

I built it and timed it against plain O(n²) with 50 asteroids over 1000 iterations. The result surprised me: at the object counts you see in an Asteroids clone, the overhead of rebuilding the grid every iteration was bigger than the savings on the pair checks. The trade-off only flips when you push the count much higher.

What I took away: before reaching for a clever data structure, measure first. For a game with a few dozen objects the straight O(n²) loop with a squared-distance pre-check is plenty. Spatial grids and quadtrees are tools for object counts a vector game on a CMM2 rarely hits.

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

That exact loop is what’s running in production in my game, and it holds 60 fps without breaking a sweat.