Welcome back! The game will have physics taking part in the magic system, and currently it has two types of physics in it: "pixel physics" (falling sand, flowing water, etc) and "rigid body physics" (boxes, balls, etc).
More physics is better, right? Sure, except for that right now they can't interact with each other at all. Which means a ball will fall straight through a sand pile. Or water falls straight through platforms rather than flowing around it. Not very good, so let's fix it!
A sketch of a solution
Let's understand how things are implemented currently:
- Pixel physics is implemented as a grid: a physics-pixel (grain of sand, drop of water, etc) always occupies exactly one space in this grid
- Rigid body physics is implemented as a collection of shapes (ball, rectangle, etc) which move around and can be at any position.
To make them aware of each other, in theory all we have to do is:
- Make pixel-physics aware of the physical space that rigid bodies take up, by somehow finding all pixels that overlap with a shape, and then marking those pixels as occupied in the pixel-physics grid.
- Make rigid bodies aware of the physical space that pixels take up, by somehow turning the pixels into a shape that we can tell the physics engine about. This should allow a ball to bounce off sand.
This will give us collisions between the two physics worlds - we'll tackle forces (like making balls float in water, or having a moving ball push falling sand) another time.
Marking shapes as occupied pixels
The simplest approach is to look at every shape we know about, then look at its axis-aligned bounding box (a rectangle parallel to the screen, known to fully enclose the shape, calculated by the off-the-shelf rigid body physics engine I'm using); for each pixel in the bounding box, check if it is inside the shape. For all pixels inside the shape, mark them as occupied in the pixel-physics simulatation.
This worked, but it was too slow, so I implemented a faster approach: look at all the pixels in the world, and ask the physics engine if they're in any shapes. This seems like it should be even slower, but it has two things going for it:
- It can use an existing data structure to speed up the lookups (which the rigid body physics engine needs to calculate anyway). This makes it faster.
- We always look at the same amount of pixels, and as more shapes are added, the amount of work to check each pixel only increases logarithmically rather than linearly (due to the aforementioned data structure). This stops it getting slower as quickly.
With that implemented, we can see water and sand respecting balls, boxes, and platforms:
This still isn't particularly fast; a still-faster way would be to remember which pixels are in a shape and rotate them when the shape moves (which seems to be what Noita does). That approach will also enable pixel-level destruction of shapes (imagine a wooden plank slowly getting consumed by fire).
But it's good enough for now, so let's move on.
Importing pixels as shapes
Fundamentally, the next task is the same as converting from a bitmap image (like a BMP or PNG) to a vector image (like an SVG): we have a bitmap of pixels, and we want to convert that to shape data.
This is challenging in the general case, but in our case we aren't necessarily looking for particularly smooth shapes, and fortunately the Noita developer briefly mentioned how they do it:
You apply a marching square algorithm to it which produces this outline of where all the pixels are... And that's a lot of vertices so what you do then is you give it to a Douglas-Peucker algorithm - that essentially smooths it out ... then you give it into a triangulation algorithm and you get a bunch of triangles [which you give to your rigid body physics engine].
So that's a 3 step process, but being lazy (as any gamer will tell you, all game developers are no-good lazy layabouts), I tried a simpler approach:
- Run the marching square algorithm
- Feed the result into the physics engine and let it deal with turning it into shapes
Marching Squares
What Marching Squares lets you do is take a scalar field and generate a contour from it; the intuition is that it lets you take a map and draw contour lines on it for a particular height.
Our case is actually simpler than that, because our "map" (pixel-physics grid) has only 2 "heights": occupied by a pixel, or not occupied by a pixel. So drawing the border between those should get us most of the way to the edge.
"Boris the Brave" wrote a great explanation of Marching Squares so I won't rehash it here; let's skip to the implemented result!
Simplifying marching squares output
I had planned to use the output of marching squares as-is, but what it actually produces is a whole bunch of line segments:
And particularly, all the line segments are produced as a big single collection, which causes problems:
- I don't know when line segments actually connect to each other, so I can't provide "closed" polygons to the physics library like it requires
- I can't tell when line segments are actually for a totally different polygon
- If pixels form a hollow shape (not diagrammed above), I can't tell what is the inside vs the outside of the shape
I addressed the first 2 problems by writing a sorting algorithm that works a little like merge-sort: for each line segment, try to match each of its ends to the open ends of shapes you've seen before. If there's no matching shape, create a new one; if both ends match the same shape then close the shape, or if two ends match two different shapes then merge those two shapes together.
It took quite some fiddly coding to implement this efficiently but it works well, and it lets us provide the resulting polygons to the rigid body physics engine:
(The 3rd problem I am still noodling on!)
Playable web build
You can play with these developments here (and no, it's not just you: the performance is not great.. see below):
Relevant controls to this update:
- Arrow keys to move camera
- B and G to create a box or circle at mouse cursor position
- Left click to draw physics-pixels (sand by default)
- Swap what you're drawing with number keys 1-5:
- 1 for Empty
- 2 for Solid
- 3 for Bricks
- 4 for Sand
- 5 for Water
- Set brush size for drawing with other number keys (6 is a single pixel, 0 is 64 pixels wide)
- C to clear physics-pixels when it all gets too slow (see next steps below)
- F1 to toggle drawing debug draw of rigid body physics (so you can see the final shapes)
Bad things that need fixing
If you play with the demo, you can see there's still a lot of room for improvement. Here's some of what's on my list:
- Performance is nowhere near good enough - even on desktop (the browser build actually runs at about the same speed today). My profiling shows that the slowest part is getting the physics engine to create a shape, so I guess my laziness failed, and I'll have to implement the shape simplification routine that the Noita developer mentioned. Eventually I'll need to multithread things too, but I'm holding off as long as possible because that will make it much harder to publish a well-performing web build.
- If you drop sand on top of a ball or box, the ball or box will often be pushed through any surface it's resting on. This is caused by the sand-shape being created as a fixed infinite-mass shape and sometimes overlapping the balls/boxes, but making the sand-shape a dynamic object doesn't seem like the right fix since we don't want to move the sand-shape as a single mass.
- Water isn't factored in at all yet: water shouldn't create a rigid body; it should just be displaced if something falls into it (and possibly apply some upwards buoyancy force).
- Work out some way to handle hollow shapes (the "problem 3" mentioned when talking about simplifying marching squares output).
- Make the player be able to stand on the generated shapes too, so you can walk up a sand pile. (This should be possible already, but it isn't, so I've probably overlooked something stupid.)