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

Slow Rush Studios

◂  Pixel Perfect Rendering
News index
Optimizing the Physics Bridge  ▸

Bridging Physics Worlds


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:

To make them aware of each other, in theory all we have to do is:

  1. 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.
Sketch of solution showing water pixels flowing around the ball
Marking grid positions as occupied should make water flow around shapes.
  1. 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.
Sketch of solution showing water pixels flowing around the ball
Importing clumps of physics-pixels as shapes should allow the ball to bounce off sand piles.

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:

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

Notice the sand and water now actually goes around shapes.

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:

  1. Run the marching square algorithm
  2. 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.

Example of marching squares run on an actual topographical map
Map on the left, marching squares output on the right. (Source: Baeldung)

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!

The red is the outline around the pixels (I turned off the pixel rendering for clarity); first I spawn some water, then some sand, and you can see the outline following along.

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:

Line segments surrounding filled in pixels
Red line segments show the approximated output of running Marching Squares on the yellow sand pixels (line segments connect together in reality; I've only drawn them separated to show the joins).

And particularly, all the line segments are produced as a big single collection, which causes problems:

  1. 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
  2. I can't tell when line segments are actually for a totally different polygon
  3. 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:

Creating shapes from the sand means that our boxes and balls will collide with sand now!

(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):

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

Relevant controls to this update:

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:

◂  Pixel Perfect Rendering
News index
Optimizing the Physics Bridge  ▸