This post is Part 3 of 3 about Metareal’s collision subsystem.

In Part 1 and Part 2, we described how boxes can fly through spaces, hit each other, push each other, and stop when they hit walls.

In this final Part we’ll look at a few glossed-over details… And then the rather glamorous feature which allows several boxes to be treated together as a composite volume.

The Fabric Of Space

I just read in the Wikipedia that empty space in our universe contains about a trillionth of an erg per cubic centimeter. That works out a millions of an erg per cubic meter. “Good heavens!”

But that’s not important. In the Meteral world, we need to know where things are. We consider each “thing” as a box-shape (or a collection of box shapes). This is described as a position (X,Y,Z), and a radius in each axis (Rx, Ry, Rz).

To detect collisions, both for physical movement and also for game triggers, we need to ask: “Which boxes, if any, are we touching?” One way would be to check every single box in the world.

Even for Metareal’s modest universe of about ten thousand anticipated objects, this would be quite slow. Time is framerate and all that.

There are a number of well-known techniques for optimizing this (K-dimensional trees & oct trees are two of them) but I chose a simple one: fixed-size bins. Since objects in Metareal are all in a bounded area about 1200 units across, and somewhat evenly distributed, this works well.

Each bin is 16 units across. Why 16? Trial and error, and most objects are less than 16 units big. To check for a collision, we just look in the bin where our collider is (its center point), as well as the 26 bins adjacent to it. Ah, you say, But what about objects that are bigger than 16 units? Well… I put them in all the bins that they’d hit. It’s a little bit inelegant for large objects, but seems to work.

When an object moves, we see if its center has changed bins. If so, we remove it from all the bins it was in (usually just 1, but more for a big object) and add it to all the bins it will be in. Again, somewhat dorky for large objects, but it works for now.

Many bins are empty. To locate a bin, we index into a std::map<long, Bin> with a 48 bit hash derived from 16 bits each for X, Y, and Z bin-position. (With a 1200 unit world and 16 unit bins, could fit into 8 bits per axis and an int map index… but it’s fine.) The way std::map works, bins pop into existence the first time it is accessed.

Ball Vs Wall

In Part 2, we described how collisions know when to stop: When the thing moving or something it’s pushing hits a wall. This feature is actually very slightly deeper. Every object has an Inertia value, which represents how hard it is to push. And every movement has a Force value, which is how big an object it can push. If the Force is bigger than the Inertia, then the thing can be pushed. Else, it is stopped. In a chain of several objects moving, the original Force is transferred through all the pushed things.

A wall is a thing with a relatively high Inertia. I’ve often had bugs where a Metareal room accidentally had a low Inertia, and would move around. It is disorienting and then the hallways no longer line up. 🙂

Complex Collision Volumes

I’ve found you can get quite far with a world whose only colliders are box-shaped. Especially in this game, where the physics are inherently… boxey! Still, it’s valuable to have other shapes, for certain kinds of puzzles where you push or manipulate pieces with corners or fitting areas and such.

The implementation builds the technique described in Part 2, and is almost disappointingly simple. To move a compound collider, move each of its component boxes as a single box, and the resulting possible movement is whichever of them can move the least. When it pushes other objects, they each check how for their components can move.

Illustrated above is a simple volume pushing a compound volume.

Shown below is the movement of several linked compound objects. It alternates between the game-render view, and a debug view showing the component volumes.

Now, because I sometimes let my code evolve a bit too long before refactoring, the actual data structure is that each CollisionVolume object includes a std::vector of all its fused CollisionVolumes. And they all point to each other. Which is maybe an odd way to do it and slightly wasteful of space, but it works and that is that for now!