Welcome back, Everyone. It’s been a few months since I added generators to my Falling Sand Simulator.
I recently had been inspired to work on this project after watching this GDC from Nolla Games. This GDC talks about how Nolla Games created their Falling Everything Engine. If anyone is interested in Falling Sand Sim development, I would highly recommend watching it. Moving forward, I’m going to try to implement some of the techniques in my project. Starting with Physics.
I found it fascinating that they actually have two systems running for their Falling Sand simulation: the cellular automata system and an actual physics engine. Here is what they do. On the first part of the frame, they simulate each element through the physics engine. On the second part of the frame, they convert the element to cellular automata and run the cellular automata rules. They get the benefits of both worlds. Fascinating!
Recalling how our Falling Sand works, Elements don’t have memory. As a consequence, we don’t have the attributes that the physics engine would need when you’re converting from cellular back to physics. However, we will try to work towards that in the future, but not in this chapter.
In this Falling Sand chapter, we will have elements spawn in the physics engine first, then when they stop moving, they get converted to cellular automata.
To get started, let’s compile a grocery list of things we need to implement this.
Our Grocery List
- We need a physics engine.
- We need to create a system to keep track of the physical elements we create in the physics engine. Oh, and we need to render them too!
- We need a way to add a collider to the cellular automata world so physical elements could bounce off it.
- We need to create a new generator that’s specifically for creating physical elements.
Our Physics Engine
To avoid creating one from scratch, I found this awesome physics engine called Aether.Physics2D. It has everything I need to get started despite the documentation being in development.
The API for this library is straightforward. Here’s an example of how to create an object:
//Create a world
World _world = new World();
// Create an object
Vector2 position = new Vector2(100, 100);
Body obj = _world.CreateBody(position, 0, BodyType.Dynamic);
Fixture fixture = obj.CreateCircle(1, 1f);
// Give it some bounce and friction
fixture.Restitution = 0.3f;
fixture.Friction = 0.5f;
// Update the world
_world.Step(deltatime);This creates the world and the object. The world is where all your physical objects are simulated. Each object could be either a Dynamic, Kinematic, or Static body.
Dynamic bodies are moved by forces and collision solvers. Great for environment objects.
Kinematic bodies are moved by you and collision solvers. Great for player objects.
Static bodies don’t move at all by the engine, but you can move them manually. Perfect for ground.
In our project, the cellular automata world will be a single static body and element bodies will be dynamic.
Colliders in this physic engine are called Fixtures. There are plenty of helper functions to create different types of fixtures. Some examples are a circle, a rectangle and you could even make a compound fixture made of many fixtures.
Warping our Physics Engine
We are going to implement an adapter pattern for the physics engine, meaning I’m going to make a wrapper class around this engine called PhysicsEngineSystem. This class will cover handling the engine, but this would allow me in the future to replace this with my own homebrew system if I wanted to.
On top of this wrapper, I going to keep note of scale. Remember the cellular automata system is much smaller than what we see on screen. With that being said, positions in the Physics Engine must scale to the cellular automata system’s world.
public class PhysicsEngine: System, UpdateSystem
{
private World _world;
private int _scale;
public int Scale => _scale;
public BodyCollection Bodies => _world.BodyList;
public PhysicsEngine()
{
_world = new World();
_world.Gravity = new(0, 9.8f);
_scale = 0;
}
public PhysicsEngine(int scale) : this()
{
_scale = scale;
}
public void Update(GameTime gameTime)
{
_world.Step((float)gameTime.ElapsedGameTime.TotalSeconds);
}
public Body CreateBody(Vector2 vector, float rot, BodyType type)
{
return _world.CreateBody(vector, rot, type);
}
public void Destroy(Body body)
{
this._world.Remove(body);
}
}Debugging Physical Elements
I’m going to rely on other classes for creating objects at the correct scale, but I need scale here to render colliders at the correct locations for debugging.
public class PhysicsDebugRenderer : System, IDrawSystem
{
private PhysicsEngine _physicsEngine;
private bool _drawDebug;
public PhysicsDebugRenderer(PhysicsEngine _physicsEngine)
{
this._physicsEngine = _physicsEngine;
_drawDebug = false;
Input.Keyboard.KeyPressed += OnKeyPressed;
}
private void OnKeyPressed(object sender, KeyboardEventArgs arg)
{
if(arg.Key == Microsoft.Xna.Framework.Input.Keys.P)
{
_drawDebug = !_drawDebug;
}
}
public void Draw(GameTime gameTime, SpriteBatch spriteBatch)
{
if (!_drawDebug)
return;
spriteBatch.Begin();
for (int i = 0; i < _physicsEngine.Bodies.Count; i++)
{
var body = _physicsEngine.Bodies[i];
var position = body.Position;
var rotation = body.Rotation;
if (body.FixtureList.Count == 0)
continue;
foreach (var fixture in body.FixtureList)
{
DrawFixture(spriteBatch, fixture, position, rotation);
}
}
spriteBatch.End();
}
private void DrawFixture(SpriteBatch spriteBatch, Fixture fixture, Vector2 position, float rotation)
{
var shape = fixture.Shape;
if (shape is nkast.Aether.Physics2D.Collision.Shapes.PolygonShape polygonShape)
{
DrawPolygon(spriteBatch, polygonShape, position, rotation);
}
else if (shape is nkast.Aether.Physics2D.Collision.Shapes.CircleShape circleShape)
{
DrawCircle(spriteBatch, circleShape, position, rotation);
}
}
private void DrawCircle(SpriteBatch spriteBatch, CircleShape circleShape, Vector2 position, float rotation)
{
//omited
}
private void DrawPolygon(SpriteBatch spriteBatch, PolygonShape polygonShape, Vector2 position, float rotation)
{
var vertices = polygonShape.Vertices;
// Draw rectangle if it is a rectangle
if(vertices.Count == 4)
{
DrawRectangle(spriteBatch, polygonShape, position, rotation);
return;
}
//omitted
}
private void DrawRectangle(SpriteBatch spriteBatch, PolygonShape polygonShape, Vector2 position, float rotation)
{
//omitted
}
}Tracking and Creating our Physical Falling Sand elements
Let’s have a system called SandPhysicsSystem handle our physical Falling Sand elements. The system will call the PhysicsEngineSystem when it needs to create a new body for an element.
Tracking our Physical Falling Sand Elements
Now to track elements, we could have a class called ElementBody that contains the physical body, element type and a position buffer (More on that later).
public class ElementBody
{
public Body Body { get; private set; }
public ElementTypes type { private set; get; }
Queue<Vector2> lastPositions;
//for shouldConvert()
static readonly int numOfDistanceSamples = 6;
static readonly float distanceThreshold = .2f;
public ElementBody(Body body, ElementTypes element) : base()
{
this.Body = body;
this.type = element;
lastPositions = new Queue<Vector2>();
lastPositions.Enqueue(this.Body.Position);
}
public bool shouldConvert()
{
// More on this later
}
}Creating our Falling Sand Physical Elements
When creating an element, the SandPhysicsSystem will call PhysicsEngineSystem for a body, then create new ElementBody and assign the body and elementType to it. Lastly, the element is added to a ElementBody List to keep track of them.
internal class SandPhysicsSystem : System, UpdateSystem
{
private PhysicsEngine _physicsEngine;
public SandAutomataSystem _automataSystem;
public List<ElementBody> _elementBodies;
private Random random;
public SandPhysicsSystem(PhysicsEngine physicsEngine, SandAutomataSystem automataSystem)
{
_physicsEngine = physicsEngine;
_automataSystem = automataSystem;
random = new Random();
int scale = _automataSystem.scale;
_elementBodies = new List<ElementBody>();
CreateWorldBorder();
}
public ElementBody CreateElementBody(Vector2 worldPosition, int element)
{
int scale = _automataSystem.scale;
//Scale down to cellular automata system levels
Vector2 position = new Vector2((int)worldPosition.X >> scale, (int)worldPosition.Y >> scale);
var b = _physicsEngine.CreateBody(position, 0, BodyType.Dynamic);
ElementBody _elementBody = new ElementBody(b);
b.FixedRotation = true;
Fixture efixture = b.CreateRectangle(1, 1, 1f, new(.5f, .5f));
efixture.Restitution = 0.5f;
efixture.Friction = 0.8f;
_elementBodies.Add(_elementBody);
return _elementBody;
}
public void CreateWorldBorder()
{
// Creates World borders on the bottom, left and right side of the simulation.
}
public void Update(GameTime gameTime)
{
//more on this later
}
}Rendering our Falling Sand Physical Elements
The ElementBody list allows me to know where and how to render these in a different system. For now, I just render these the classical way to render anything in Monogame. Nothing special here but I do replace it later. Right now, every physical element is rendered as sand.
public void Draw(GameTime gameTime, SpriteBatch spriteBatch)
{
int scale = _sandPhysicsSystem._automataSystem.scale;
spriteBatch.Begin();
for(int i = 0; i < _sandPhysicsSystem._elementBodies.Count; i++)
{
Vector2 position = new Vector2(
_sandPhysicsSystem._elementBodies[i].Body.Position.X,
_sandPhysicsSystem._elementBodies[i].Body.Position.Y
);
float f_scale = 0b0001 << scale;
Rectangle sourceRectangle = new Rectangle(0, 0, 10, 10);
spriteBatch.Draw(_sandTexture, position * f_scale, sourceRectangle, Color.White);
}
spriteBatch.End();
}Our First Trial
Here is what we have so far. You likely noticed the huge lag spike when all the bodies meet the ground. I’m not sure how to optimize this other than reducing the number of bodies. Even later in this project, I’m still curse by it, but I do find ways to hide it by accident while developing other parts.
Converting Falling Sand Physical Elements to Cellular Automata Elements
Now we should find a way to convert physical elements into cellular automata elements.
My first thought was to test if the velocity and acceleration magnitudes are zero, however, I wasn’t able to a way to get the physics engine to spit out acceleration.
Creating a Buffer of Positions
The only other solution I could think of and ultimately went with, was keeping a buffer of positions over time for each element and testing the distances between them. Now this is terrible for memory but at least I’m able to track it. This is where the shouldConvert function comes in.
Every time I call it, it will add up all the distances relative to neighboring positions in the buffer and test if the sum is less than the distanceThreshold. If it is than, it has not been moving for a while and should be converted to cellular automata.
public class ElementBody
{
Queue<Vector2> lastPositions;
static readonly int numOfDistanceSamples = 6;
static readonly float distanceThreshold = .2f;
public bool shouldConvert()
{
if (lastPositions.Count < numOfDistanceSamples)
{
lastPositions.Enqueue(this.Body.Position);
return false;
}
lastPositions.Dequeue();
lastPositions.Enqueue(this.Body.Position);
float sumofDistances = 0;
for (int i = 0; i < lastPositions.Count - 1; i++)
{
Vector2 a = lastPositions.ElementAt(i);
Vector2 b = lastPositions.ElementAt(i + 1);
//Calculate distance between two points
float distance = (float)Math.Sqrt(Math.Pow(a.X - b.X, 2) + Math.Pow(a.Y - b.Y, 2));
sumofDistances += Math.Abs(distance);
}
//If the sum of distances is less than the threshold,
//then the element is not moving
if (sumofDistances < distanceThreshold)
{
return true;
}
return false;
}
}Now since I’m thinking about it, I should have used a circular array solution for this, but that’s an optimization solution for later.
Trying Our Conversion
In our SandPhysicsSystem, if we loop through and each ElementBody and call shouldConvert every frame, we will eventually get cases where we know when we should convert them. Converting them meaning we will destroy the physical element and placing an element in the cellular automata system in the same position roughly.
public void Update(GameTime gameTime)
{
List<int> toConvert = new List<int>();
for (int i = 0; i < _elementBodies.Count; i++)
{
var el = _elementBodies[i];
if (el.shouldConvert())
{
toConvert.Add(i);
}
}
for (int i = toConvert.Count - 1; i >= 0; i--)
{
int index = toConvert[i];
var el = _elementBodies[index];
_elementBodies.RemoveAt(index);
_physicsEngine.Destroy(el.Body);
//Should convert here
}
}Here is what we have now. Please keep in mind that for every disappearance of an element we should be placing an element in the cellular automata system.
Converting a Falling Sand Physical Element
Now let’s handle the conversion. It really simple since our physics engine is at the scale of our Falling Sand Cellular Automata system.
private void OnConvertToAutomata(short element, Vector2 position)
{
int x = (int)position.X;
int y = (int)position.Y;
_automataSystem.placeElementAt(ElementTypes.Sand,x,y,PositionType.LocalSpace);
}Oddly enough, this part of the logic actually helps hide the lag spikes that we saw earlier.
Almost there…
Now this is great and all, but we don’t have the cellular automata world communicating with the physics world yet. Right now, physical elements will go through the automata world. Now to fix this, we’re going to have to use a greedy meshing tactic.
Representing Our Falling Sand Cellular Automata World in the Physics World
On my first try on representing our Falling Sand cellular automata world in the physical world, I created a new square body for every solid element in the cellular automata world every frame. That was… a terrible idea. The lag spikes I was getting from the physics engine felt like it was multiplied by 10 times.
Introducing Greedy Meshing
After some time, I discovered greedy meshing from “Greedy Meshing Voxels Fast – Optimism in Design Handmade Seattle 2022” by Davis Morley.
In order to represent our cellular automata world, we will write a greedy meshing algorithm that spits out a bunch of rectangle fixtures that can apply to single static automata world body.
My implementation of the greedy mesh algorithm goes like this…
Create a Boolean array of your world where true is solid and false is non-solid.
For each solid(true) element,
- Create a 1 by 1 rectangle
- Try to grow it horizontally until you run into a non-solid(false)
- Try to grow it vertically, you must repeat step 2 on a neighboring vertical row until you run into a non-solid
- Mark all the elements that are in the rectangle as non-solid(false)
In my Falling Sand project, I start from the last element of my array since that’s the bottom right of the screen.
For growing horizontally, I just test the left neighboring cell until I can’t.
For growing vertically, I test the above neighboring row until I can’t.
When I create rectangles, I have to create them as Vertices as that’s what the fixtures need when you create when you create them.
Greedy Meshing Class
I made a class strictly dedicated to this called GreedyMeshSolver.
public abstract class GridMeshSolver
{
public abstract Vector2[] Solve(bool[] grid, int width, int height);
}
public class GreedyMeshSolver : GridMeshSolver
{
public override Vector2[] Solve(bool[] grid, int gridWidth, int gridHeight)
{
List<Vector2> vertices = new List<Vector2>();
for(int i = grid.Length - 1; i > 0; i--)
{
if (!grid[i]) continue;
int x = i % gridWidth;
int y = i / gridWidth;
int width = 1;
int height = 1;
grid[i] = false;
// grow Vertically
while (true)
{
if (y - height < 0) break;
int index = x + (y - height) * gridWidth;
if(!grid[index]) break;
grid[index] = false;
height++;
}
// grow Horizontally left
while (true)
{
if (x - width < 0) break;
int index = x - width + y * gridWidth;
if (!grid[index]) break;
bool canGrow = true;
for (int j = 1; j < height; j++)
{
int index2 = x - width + (y - j) * gridWidth;
if (!grid[index2])
{
canGrow = false;
break;
}
}
if (canGrow)
{
for (int j = 0; j < height; j++)
{
grid[x - width + (y - j) * gridWidth] = false;
}
width++;
}
else
{
break;
}
}
Vector2 offset = new Vector2(width - 1, height - 1);
Vector2[] vertics = new Vector2[4];
vertics[0] = new Vector2(x, y + height);
vertics[1] = new Vector2(x, y);
vertics[2] = new Vector2(x + width, y);
vertics[3] = new Vector2(x + width, y + height);
for (int j = 0; j < vertics.Length; j++)
{
vertics[j] -= offset;
}
vertices.AddRange(vertics);
}
return vertices.ToArray();
}
}
Using Our Greedy Meshing Class
Here is how I use the GreedyMeshSolver in the SandPhysicsSystem.
public class SandPhysicsSystem : System, IFixedUpdateSystem
{
public Body _automataWorld;
private List<Vertices> _worldVertices = new List<Vertices>();
private GridMeshSolver _gridMeshSolver;
public SandPhysicsSystem(PhysicsEngine physicsEngine, SandAutomataSystem automataSystem)
{
_automataWorld = _physicsEngine.CreateBody(new(0, 0), 0, BodyType.Static);
_gridMeshSolver = new GreedyMeshSolver();
}
public void GenerateWorldCollider()
{
_worldVertices.Clear();
//true == solid, false == empty
bool[] grid = new bool[_automataSystem.elements.Length];
for (int i = 0; i < _automataSystem.elements.Length; i++)
{
grid[i] = (_automataSystem.elements[i] != -1);
}
var vertices = _gridMeshSolver.Solve(grid, _automataSystem.width, _automataSystem.height);
for (int i = 0; i < vertices.Length; i += 4)
{
Vector2[] v = new Vector2[4];
v[0] = vertices[i];
v[1] = vertices[i + 1];
v[2] = vertices[i + 2];
v[3] = vertices[i + 3];
Vertices verts = new Vertices(v);
_worldVertices.Add(verts);
}
if (_worldVertices.Count == 0) return;
while (_automataWorld.FixtureList.Count > 0)
{
_automataWorld.Remove(_automataWorld.FixtureList[0]);
}
_automataWorld.CreateCompoundPolygon(_worldVertices, 1f);
}
public void FixedUpdate(GameTime gameTime)
{
GenerateWorldCollider();
ConvertAnyElementThatAreNotMoving();
Debug.StickyLog.Log("Element Bodies:", _elementBodies.Count.ToString());
}
}
Check out those Colliders!
Now jumping into the future where I can paint physical Falling Sand elements, here is what the colliders look like.
In a future optimization, I would like to make this algorithm run in chunks instead of on the whole world.
Adding support to paint physical elements in our Falling Sand Controller
Painting with physical elements is easy as painting with the old Falling Sand cellular automata way. The only difference is where the element starts at, which is the physics engine. We got to remember about the scale again, but it’s the same thing.
If I refactored my Generator code to use abstraction, I really just have to update the PlaceElement for the physical elements:
internal class PhysicsElementGenerator : ElementGenerator
{
private SandPhysicsSystem _system;
private Random random = new Random();
public PhysicsElementGenerator(SandPhysicsSystem system) : base()
{
_system = system;
}
public override void PlaceElement(int x, int y, PositionType positionType)
{
Vector2 position = new Vector2(x, y);
var b = this._system.CreateElementBody(position,Element);
int k = random.Next(0, 2) == 0 ? -1 : 1;
b.Body.ApplyLinearImpulse(new((float)random.NextDouble() * 10 * k, (float)random.NextDouble() * 20));
}
}As a bonus, using abstraction will allow me to switch between different generators based on the elements. For example, if there’s something that doesn’t need to move at all, then I would use the cellular automata generator to place it.
There you have it…
Here is what we have now. However, I made some small changes that are not mentioned here.
There was a chance that the physical element tries to place itself in a non-empty space in the Cellular automata world. To resolve it, I just find the nearest empty cell above the location and fling it upwards as a physical element again. To my surprise, this makes a splash effect.
I modified the pixel array that goes into the world texture for rendering to include the physical elements as well. That way the shaders could still take full effect of the physical elements.
Lastly, for the PhysicsEngine class, I made it using an Object Pool for creating new bodies. Since I’m creating and deleting bodies rapidly, I thought it would be a good idea to give the Garage Collector a break. 🙂
So, what’s happening next?
In the next Falling Sand chapter, I think I want to focus on bringing a new element. Stone is on my mind right now. It’s the perfect element to test how the simulation in different scenarios. Stone wouldn’t react to physics or anything for now but I’m thinking of adding a structure support system. With stone, I could make the world bottomless, so elements could fall off the world completely. I could make the ground a couple layers thick of stone.
Another thing would be to revamp the painting system. I don’t have a proper delete tool, and I would like to make the print brush area visible with different print brushes.
One last challenge would be to crazy enough to take my greedy mesh result and actual render a mesh for the world, instead of a big texture. This could allow me to improve the graphics greatly, but this is scary topic. Stay tuned.
If you like to try out the current build of this project, check out the Falling Sand Simulation by LeoTheLegion (itch.io) page. 🙂