Slow Rush Studios logo,
    depicting an apprehensive-looking snail rushing forward

Slow Rush Studios

◂  Designing a Magic System
News index
Discord and Making a Splash  ▸

Atomic Holes and Multiplayer


This week, it's my birthday!

To celebrate, I fixed the biggest outstanding bug in the "moving bodies to atoms" physics bridge: terrain can now have holes in it, without glitching out moving bodies!

Plus, the game now supports multiple players, including via gamepad controllers!

Wholly Holey Terrain

Previously, we had this freaky bug where a moving body covered in atoms would explode:

Before: covering a moving body will make it 'explode out'.

This was happening because the way we create the collider for the covering-atoms (see Bridging Physics Worlds) would always build a polygon without holes, so when the moving body found suddenly itself overlapping a collider then it'd glitch out (full explanation at Playing Nice with Moving Bodies).

So I changed how we create colliders:

  1. I still generate the initial outline of polygons using Marching Squares as before; I use a mildly-complicated sorting routine to connect the separate line segments it outputs into contiguous polygons:
Marching squares on a sample input
Output of Marching Squares algorithm (after sorting its line segments into contiguous polygons).
  1. Before simplifying, I check to see if any of the polygons is the first "inner" polygon inside another.
    • This turned out to be easy because my sorting routine accidentally (but usefully) made it so that polygons-which-are-actually-holes-in-an-outer-polygon are recorded with reverse "winding" (vertices in counter-clockwise order, rather than clockwise order). So I detect those and store them as holes in the outer polygon:
Hole identification
What we get after matching holes to their containing polygons. Polygons are drawn in purple-to-green gradient; holes are drawn in red-to-yellow gradient (notice holes always have counter-clockwise 'winding'); the tiny circles are vertices.
  1. Simplify the polygons using the Ramen-Douglas-Pecker algorithm, just like we did before:
Polygon simplification
Simplified polygons and their holes, using the same color scheme as above.
  1. Instead of using Earclipping 1 to break the polygon into triangles that can be turned into a collider, I use Constrained Delaunay triangulation to do that. "Constrained" here basically means I can say "hey, when breaking this polygon into triangles, definitely make sure these edges are included as-is": 2
Triangulated polygon
Result of triangulating the simplified polygons and their holes.
  1. Unfortunately, the result always gives a convex polygon, and holes are filled in with triangles too: the Delaunay triangulation algorithm doesn't have a way to say "never create triangles in these areas". So I manually find those triangles whose centers are outside the polygon (or contained in a hole) using a raycasting approach and chuck 'em in the bin:
Polygon triangulated with excess triangles
  1. We can finally pass those triangles to our off-the-shelf rigid-body physics engine to create the final colliders: 3
Final colliders generated
Red lines show the final colliders we get (the green boxes are the bounding boxes - you can ignore those).

At last the colliders generated look fairly sane (especially bearing in mind we are quite zoomed in here).

Now we can finally put a moving body in a fully-sealed-cave and have it work fine:

Previously this moving body would have been just been pinned in place; now it falls to the floor as you'd expect.

Or cover a body in sand:

At last, you can cover a moving body fully in sand and it just.. lies there, instead of flipping out.
(But you can still grab it and move it, which is nice!)

You can even put a moving body inside another moving body!

A moving body in a moving body, and for good measure I put some sand in there too!

Well, okay, keeping sand inside a body still only works as well as it did in the last few weeks (which is to say: not super well), because that's totally separate from anything we just talked about.

But still, we have Wholly Holey Terrain now!

Though I can't say we have Wholly Holey Holy Terrain. (Unless... hmmm... a special type of atom which destroys undead enemies if they set foot on it?)


I thought the next thing I should do is make players able push atoms (falling sand and especially water) around in the same way that moving bodies can, but I got distracted and instead added support for having more than one player - this is meant to be a couch co-op game after all, so "local multiplayer" is a key part of it.

So, you can now play with 4 players: 4

Jaw-dropping local multiplayer action.

And, yes, we have hats now too. I'm told they're all the rage.

In-game Help

With 4 sets of keyboard controls on top of all the debugging shortcuts I added, I was having a hard time remembering what key did what.

So I added (a completely-over-engineered-in-hindsight control mapping system inspired by Rewired and) a very basic help menu that explains controls:

You can access the help menu by pressing F1. (Sorry for the invisible cursor! You get the idea though.)

M-M-M-M-Multiplayer web build‎

Here you go, plug in your gamepad (or your keyboard with arrow keys) and try drawing some sand on a body or spawning a second player:

Click to focus, then play with keyboard and mouse. No mobile support! Give feedback.

That's all for now folks - see you next week!


It is possible to extend the earclipping algorithm so that it supports holes in polygons as detailed here. But Delaunay triangulation tends to result in higher quality triangulations (defined as fewer triangles with one very small angle) than earclipping at the cost of slightly worse performance (and having to trim the triangles we don't want in the next step - that's step 5 in the list above), so I wanted to give it a shot3. But I may end up having to go back and try extending earclipping to support holes if performance here ends up being a problem!


What difference does Constrained Delaunay triangulation actually make? The triangulation library I'm using has a nice illustration here that shows the difference: the same vertices are in use in both, but the edges chosen are not the same.

That said, after implementing Constrained Delaunay Triangulation I realized that the edges that Unconstrained Delaunay Triangulation tends to create are usually good enough for me. So maybe I could just use the Unconstrained variant and that'd be faster?

On the other hand, the routine in the next step to discard unwanted triangles (i.e. step 5 in the list above) is using an optimization that relies on being able to identify which triangles are touching known constrained edges. So at some point I'll measure and see which way actually performs better.

Example of unconstrained delaunay triangulation
Example of constrained delaunay triangulation
Unconstrained vs Constrained Delaunay triangulation for our example polygon.

The keen-eyed among you will have noticed that the collider generated by the rigid body physics engine is, in fact, not entirely composed of triangles. This is because I've asked the physics engine to combine triangles together, which it seems to do using the Hertel Mehlhorn algorithm. I don't really know anything about it other than what that linked abstract says. But, as I write this update, it occurs to me that this merging of triangles probably does weaken the argument of "Constrained Delaunay Triangulation gives better triangles than earclipping-with-hole-support does".


Well, actually, I haven't actually added a 4-player limit, so the only limit is the number of keyboard mappings defined (4) and the number of simultaneous controllers supported by the gamepad library I'm using (8). So technically, if you have controllers coming out of your ears, you could play with 12 people at once. I might even keep that indefinitely as an available option - but in practice, 1-4 people is what I'll be aiming to tune the gameplay for.

◂  Designing a Magic System
News index
Discord and Making a Splash  ▸