A couple (new) questions on how you accomplish the Box2D rigidbodies in the falling sand simulation.

[DavidMcLaughlin208]

Hello, I stumbled upon your repo here where I was surprised to find another David M attempting to accomplish something similar.

I do not have a background in GameDev and have been working on creating a falling sand simulation and integrating Box2D. (Inspired by Noita also). I am not attempting to create an entire engine as that is beyond my current abilities and so am using LIBGDX as a pretty bare bones engine to handle most of the update logic myself.

My Repo: https://github.com/DavidMcLaughlin208/FallingSandJava
DevLog Video around integrating Box2D: https://youtu.be/_xFluvZCSaM?t=74

I have a couple questions not covered by the Noita dev tech talk or your answer in another issue where you talk about Box2D.
Issue: #3

1. How do you account for a Box2D object in the falling sand simulation when the rigidbody has rotated?

I am assuming you are using a 2D array at the core of your falling sand simulation. Lets say you have a box which is 3x3 and exists in the falling sand simulation. When the box rotates 45 degrees it will no longer easily fit into the 2D array. There will be 'holes' in the box where it does not easily fit into the 2D array. Here is an image of what I mean:

I can think of ways to be able to draw the object without the holes. But the falling sand simulation cannot account for these holes in the rectangle and you can see some sand has fallen into the box.

2. Did you write your own implementations of marching squares and Douglas Peucker algorithms?

In my implementation I used a custom Moore Neighbor tracing algorithm for finding the perimeter of polygons (although this doesnt account for holes in polygons) and a custom Visvalingam line simplification algorithm but I am running into issues with it. Is there a library you are using or is there source material you referenced?

I see you are close to releasing your code on Github. I will be glad to read through it (although I don't know C++) and get some understanding from the code itself. But would be interested in hearing how you solved these problems yourself.

[PieKing1215]

1. This is a very good question. Basically, I haven't really solved it yet.

This is still something I'm working on, as I only recently started working on this problem (my rigidbodies were just images and the individual pixels were not simulated until recently), and it's kind of been on hold until I release the initial code.
I don't know exactly what technique Noita uses for this, and I haven't really looked at anything else to figure out what the best way to solve this is.

What I have now is this:
To put the pixels into the world, for each pixel in the rigidbody's internal buffer, it tries to place the pixel in the "right" spot but if that spot is occupied, it tries to place it 1 pixel in each direction.
Then when it takes the pixels out of the world, for each pixel in the rigidbody's internal buffer, it compares the internal buffer pixel to the pixel in the "right" spot and 1 pixel in each direction to see if they match and removes it from the world if it does.
It feels super hacky but it does fix a lot of the holes that you get, though not all of them.

The main problem for me is that I would like there to be minimal "duplication", so just filling in the remaining gaps by copying nearby pixels would not be ideal for me.

This is probably the first thing I'm going to work on after going open source, and I'll add an update to this issue once I make more progress.

2. For marching squares, I'm using cpp-marching-squares which is a port of a public domain Java implementation.
   For Douglas Peucker I'm using this implementation, slightly modified to work with the data types I'm using for the rest of my code. This would be pretty straightforward to port, the only thing is that it doesn't provide an implementation for the "dist_to_line" function so you need to do it yourself.

[DavidMcLaughlin208]

Ah ok thanks for the explanation. Yeah I tried some method of having pixels belonging to rigidbodies occupy the holes adjacent to them, which mostly worked but was extremely resource intensive and wouldn't work as a long term solution. I'll watch this project to see if you are able to find a solution and will reach out here again if I am able to get one working.

I may try to reach out to the Noita devs to see if they will divulge their proprietary secrets.

---

Thank you for the resources regarding the algorithms!

[PieKing1215]

Ok I've been slowly rewriting this engine in another language and when I was doing rigidbodies I tried to solve this problem in a different way and I think it works out pretty nice. I figured I'd write it down here for now in case anyone finds this:

So basically, when I'm updating a rigidbody, I don't actually put all of the pixels into the world and then take them out again at the end of the tick.

I have it set up so my simulate_pixel function basically takes an x/y pos, a MaterialInstance, and some world context, and returns an Option<MaterialInstance>, which represents whatever that MaterialInstance "turned into". Importantly, the pixel at that x/y position in the world buffer does not actually have to be that MaterialInstance. The function is responsible for updating that pixel, which could mean moving it, therefore actually placing it into the world pixels, in which case it returns an empty Option, otherwise if it doesn't move/change it returns an Option containing the same MaterialInstance.
Another key factor in this function is that pixel lookups take into account pixels in rigidbodies, just by looping through them and doing the transformation (note: this part still does have the holes problem, but it's better to have it here as it doesn't cause deleting/duplicating pixels since the holey coordinates are not "saved" anywhere).

So when I'm updating a rigidbody, instead of moving all of the pixels into the world, I loop through each pixel in the body, transform the coordinates, and call the simulate_pixel function. If it returns an empty Option (ie. the body had sand that moved), the pixel is removed from the body, and if the Option has something, the pixel is kept (or changed to the new material) in the body.
(So if a body is made entirely of solid pixels, it stays exactly the same since simulate_pixel will always return an Option containing the same MaterialInstance it was given, since solid pixels don't move).

All of that has the effect of never deleting or duplicating pixels.
For rendering, instead of drawing each pixel myself, I'm just keeping and updating an image along with each rigidbody, so drawing it rotated doesn't show holes. (You could use a shader or something to render it aligned with the world pixel grid if desired)

There's still some things this doesn't immediately solve. For example, there's no way for pixels to be added to a rigidbody in simulate_pixel, only removed. So if you have like a bucket of sand, it can fall off of the rigidbody but not fall onto it (more precisely it will not "stick" and move into the rigidbody buffer). Though I don't see any reason this couldn't be added to this system.

Overall, it works much better than the way I was trying to do it before, (though my particles still need some collision polish).
Demo: (the pink pixels stay part of the body until it's tipped over)

TL;DR: Instead of putting rigidbody pixels into the world and ticking, have a function that simulates an arbitrary pixel at a position and tells you if it moved/changed, call that function for each pixel in the rigidbody, and remove it from the rigidbody and add it to the world if it moved.

[DavidMcLaughlin208]

Nice work! Seems like a solid approach and that demo looks great. What language are you using to rewrite the simulation?

[PieKing1215]

Rust; one of the main problems with this version is that I didn't know how to write good c++ at the start so 95% of it uses raw pointers. Also the build system for this version just breaks over time on its own apparently and is a mega hassle to get working. These problems made it pretty hard to debug random crashes or memory leaks, and Rust solves both of these problems for me by having much safer memory management and a far better build system (compared to what I was doing) while still having roughly equal performance. (I also just really like Rust as a language)

[elyshaffir]

...
TL;DR: Instead of putting rigidbody pixels into the world and ticking, have a function that simulates an arbitrary pixel at a position and tells you if it moved/changed, call that function for each pixel in the rigidbody, and remove it from the rigidbody and add it to the world if it moved.

Hi, I am also trying to create something similar but I am not sure if I understand you correctly so please correct me if I am wrong.
This algorithm is solving particle-to-rigidbody collisions right? what I mean by this is how do you handle if for example the player collides with simulated particles? from what I gather, sand falling on a player will bounce off of it but a player falling on sand will go through it / move the sand?

[PieKing1215]

Just for clarity, I'll mention the terminology I'm using since it can be confusing when there are like 4 "simulations" working together:

• Sand: pixels part of the base "falling sand" simulation (technically not just "sand" pixels, but solid, sand, liquid, gas)
• Particles: pixels that have a velocity or other more complex behavior
• Rigidbodies: complex physics objects composed of a grid of pixels, using a physics engine to compute physics
• Entities: simple physics objects limited to rectangle collision with no rotation, using velocity and for loops and stuff to compute physics (more limited than rigidbodies, but has pixel perfect collision)
  

That algorithm is mostly for sand -> rigidbody interaction. Like you said it handles sand falling onto rigidbodies and sand falling "out" of rigidbodies, but not rigidbodies landing into a bunch of sand or something.

What I do for rigidbody -> sand interaction is basically loop through every pixel in the rigidbody, transform the coordinates into world space, and check if there's a sand pixel in that location. If there is, I calculate the velocity of the rigidbody at that point (the physics engine I'm using has a velocity_at_point function that takes angular velocity into account), and apply an opposite force to the rigidbody at that point, as well as some general linear/angular velocity damping. I also try to displace the sand or turn it into a particle and send it flying depending on context, but I'm not really 100% happy with it.

This is the result of what I have right now:

I do want to make it so the rigidbodies will actually come to a full stop inside sand. It's entirely possible to do with this system, I just haven't done it yet.

Since you were talking about a player though, I will note that my player is actually an entity, not a rigidbody*. Entity collision isn't handled by the rigidbody physics engine, it's done manually (this is simplified) by adding velocity to position, looping through the rectangle collision box, looking for pixels at the new position, and stopping** the entity if it finds any. This means entities can safely stand on top of sand.
It's very similar to how Noita does it: the player and enemies (entities) can stand on sand, but boxes and other physics objects (rigidbodies) fall into it.

*It's a bit weird because the player entity does actually also have a rigidbody in the physics engine, but it's only used for entity <-> rigidbody interaction and doesn't interact with sand/particles at all
**I actually have it so you can displace a small amount of sand which turns into particles but that's beside the point

TL;DR: Rigidbodies have damping and other forces applied when they overlap sand. Player is actually an entity (rectangle hitbox, pixel perfect collision detection), which lets it stand on sand.

Hopefully that's helpful! Lmk if you have any followup questions

[elyshaffir]

Amazing answer, thank you!