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:

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:

Output of Marching Squares algorithm (after sorting its line segments into contiguous polygons).

2. 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:

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.

3. Simplify the polygons using the Ramen-Douglas-Pecker algorithm, just like we did before:

Simplified polygons and their holes, using the same color scheme as above.

4. Instead of using Earclipping ¹ 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": ²

Result of triangulating the simplified polygons and their holes.

5. 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:

6. We can finally pass those triangles to our off-the-shelf rigid-body physics engine to create the final colliders: ³

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:

Or cover a body in sand:

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

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?)

M-M-M-M-Multiplayer

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: ⁴

• You can relive my formative childhood years and all cram behind one keyboard with 3 other friends, or use 4 gamepads like the rich kids with consoles used to - or a mix of keyboard and gamepads, of course.
• I want drop-in/drop-out multiplayer, so folks can join or leave at any time, so to join as an extra player, just press a button on a gamepad (or a key from a different keyboard control-map, like the arrow keys), and you'll be (literally) dropped in.
• This all works on the playable web build too.

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:

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:

• Obviously you can press F1 for full help, but the rough 4 sets of keyboard controls are WASD, IJKL, Arrow keys and Numpad-8456.
  • You can see some keys for Fire and elements - none of that is implemented just yet. Soon! (hopefully)
• Turning on free-look mode (detaching the camera from the players) has been moved to F4 to avoid a keyboard conflict, and you can't spawn new players while in Freelook mode either.

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

²

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.

Unconstrained vs Constrained Delaunay triangulation for our example polygon.