After a long hiatus of blog articles, I though I’d dash off a few thoughts inspired by a bug I’m fixing.

I’ve been editing rooms and puzzles for some time, not always as productively as I should imagine or like but with always forward progress. I have here a door which is threaded by a peg, and the peg cannot be removed until a long needle is slid away from it. And I encountered a bug where certain parts of the needle did not collide with the peg.

I’ve been working for so long on physical puzzles, and they all “just work” that I’d forgotten how limited the physics actually is. I’d forgotten all the shortcuts and hacks and compromises of the past…

In the beginning. I though, oh, everything in the game will be either small moveable thingums, or large immovable walls. And that the things would move slowly if not majestically. So the execution was:

• hash objects into 16x16x16 bins
• small <16-size movable objects live in 1 bin
• large immovable objects would be placed into multiple bins, but not exactly all the bins they touch
• small moving objects would inspect all 27 bins of their neighborhood for collisions (this is why big objects don’t exactly need to be in all their bins)
• as an optimization, each bin has pointers to its 26 neighbor bins. this helped performance a lot.

and on the whole life was good.

First Complication: Pushing large objects. For comic effect, it was nice for the player or a moving game object to be able to shove a large object such as a big sliding door. So, no problem, added a “bin radius” field to the collision object. This is just the span of the object, over two over bin size. And rounded down, since moving objects check all 27 neighbors. This is enough information to remove from all bins, and insert to all new bins, when shoved.

Second Complication: Fast moving objects. Although moving 16 units in one 60th of a second tick seems very fast –. Wait a moment, what’s a unit. Metareal takes place in a dimensionless, abstract universe of no specific real world scale. But between you and me, a unit is about 1 meter. So anyway, moving 16 units in a tick seems plenty fast. But with the vagaries of acceleration and playful physics, as well as the occasional “bullet”, it happens. Yet another easy fix: Rather than check just the 27 bins around the mover, sweep that box, adding by nines additional squares of bins to check.

Third Complication & Final Straw: Large moving objects. So then we come back to the peg and the needle. I saw that the peg could push the needle anywhere along its length… but the needle would float through the peg except at its center.

It’s a bug. Bug bug buggery bug.

Here I was, happily building puzzles, believing in the laws of physics, and then this. And in a mad couple of hours of rereading my own old code, I remembered all these handy shortcuts. So it’s time to revisit the strategy.

• hash objects into 16x16x16 bins
• each object will live in exactly the bins it spans. So even a small object might be in 8 bins.
• a moving object will check the full complement of its own bins, swept in the direction of its movement.
• as an optimization, each bin has pointers to its six cardinal neighbors.

This reimplementation, my project this warm July afternoon in Arkansas, 2021, is completely and rigorously correct for any size object and any size motion.

Evolution is Good. And despite the torturous journey, I remain pleased with the process. Was it “right” to start with a broken, barely working, and not that much easier solution? Who cares! It got me going, and lo these years I understand the problem and the solution ever better. When I did the first version, I truly couldn’t have invented this later more correct and probably more performant solution. Fermentation takes time, and here we are.