Improving the foundation of our falling sand simulator

Formalize particles and material rules

In the previous post, our Grid held hex strings, or a 0. If we want to be able to add new particles with different rules, we need to lay a strong foundation to build upon - that is, storing objects, not colors.

This turns the falling sand demo into a more extensible particle simulation, where each material can eventually own its own behavior.

Let's introduce the Particle.

class Particle {
  constructor({color, empty} = {}) {
    this.color = color;
    this.empty = empty ?? false;
  }
  // We'll use this later!
  update() {}
}

It has a color, and an indication of whether or not it is empty.

That small change gives the simulation a vocabulary for materials instead of treating every cell as just a color.

Let's extend it to create Sand...

class Sand extends Particle {
  static baseColor = "#dcb159";
  constructor(p) {
    super({color: p.varyColor(Sand.baseColor)});
  }
}

And add an empty particle, which every single pixel other than sand, will be. That's right, lots of instances of Empty.

class Empty extends Particle {
  static baseColor = window.background;
  constructor() {
    super({empty: true});
  }
}

Now we can just keep track of our "current particle type" and then add a little palette to choose between them!

Just hit "Start Rendering", and when you're ready for the next step, "Pause Rendering". The current approach is very inefficient, and we're going to improve it starting in the next step, so let's not waste computation by keeping this running.

Performance and bug fixes for the falling sand simulation

If you want to skip all this performance stuff, click here to go straight to the new functionality!

A larger canvas

If we try to make our canvas larger, we notice we get a pretty harsh slow down.

Just hit "Start Rendering" and make some sand to see how slow the canvas (and whole post) gets!

Let's do some profiling to see why that is.

For browser-based particle systems, performance problems often come from per-cell work repeated thousands of times per frame.

(Make sure to hit "Pause Rendering", or the whole post is going to continue to be slow)

Unnecessary color parsing

So I jumped in Chrome DevTools and hit the performance tab, record and played around in our canvas.

Wow! The vast majority of the processing is going to Color._parseInputs

This is the current implementation - where color is a hex string, like #fff123.

function setPixel(p, i, color) {  // color is a string
  const index = 4 * i;
  p.pixels[index] = p.red(color);  // Parse string
  p.pixels[index + 1] = p.green(color);  // Parse string
  p.pixels[index + 2] = p.blue(color);  // Parse string
  p.pixels[index + 3] = p.alpha(color);  // Parse string
}

Parsing the color from a string for every channel of every pixel on every frame is expensive! Fortunately now that we know what the problem is, it's a pretty simple fix. We just need to calculate the channels at particle creation time, which we can do in our approach with p.color, then we don't need to do any parsing at draw time, because we're passing around an object with the channels pre-calculated.

In a real-time falling sand simulation, even small per-pixel costs compound quickly because the draw loop touches the grid every frame.

p.backgroundColor = p.color(window.background);
p.varyColor = (color) => {
  // Skipping the color varying logic for brevity
  // See the previous post for how we did it!
  return p.color(`hsl(${hue}, ${saturation}%, ${lightness}%)`);
};

What a dramatic improvement. The key takeaway here isn't that string parsing is slow. It's that profiling is an incredibly powerful tool for understanding the performance of an application. We shouldn't blindly optimize according to what we think might work. We should profile and tackle the bottlenecks it identifies!

This is the practical workflow for optimizing canvas simulations: profile first, find the actual bottleneck, then reduce repeated work.

Only redraw changed particles

So, we removed our string parsing- what's the next step?

Instead of updating our buffer for every cell in our simulation, let's keep a Set of indices of the pixels we modified, and only update them!

This is a dirty-cell optimization: only cells that changed need to be pushed back into the canvas pixel buffer.

Additionally, now that we're tracking updates, we can automatically pause the simulation when it's not updating, and resume when the user interacts with it.

So, let's introduce the Set, and keep track of whether we cleared all pixels last render.

initialize(width, height) {
  super.initialize(width, height);
  this.modifiedIndices = new Set();
  this.cleared = false;
}

Now we need to create an entry point to set values in the grid that we'll always use now. It will take note of the index that was modified.

setIndex(i, particle) {
  super.setIndex(i, particle);
  this.modifiedIndices.add(i);
}

This one's easy - if we cleared this frame, take note!

clear() {
    super.clear();
    this.cleared = true;
}

update runs at the beginning of every frame, so let's make sure to reset our modified indices and whether we've cleared.

update() {
  this.cleared = false;
  this.modifiedIndices = new Set();
  super.update();
}

If we're trying to update an empty space, just return.

updatePixel(i) {
  if (this.isEmpty(i)) { return; }
  super.updatePixel(i);
}

And if we're trying to swap empty space, just return.

swap(a, b) {
  if (this.grid[a].empty && this.grid[b].empty) {
    return;
  }
  super.swap(a, b);
}

Finally, our draw. If we cleared, clear all the pixels. If we modified any pixels, then just set those!

draw(p) {
  if (this.cleared) {
    p.clearPixels();
  } else if (this.modifiedIndices.size) {
    this.modifiedIndices.forEach((index) => {
      p.setPixel(index, this.grid[index].color || p.backgroundColor);
    });
  }
  p.updatePixels();
}

Wait a sec - we're still calling p.updatePixels every frame!

Yeah- so we actually clear the screen at the beginning of every loop, so if we don't call it, it'll be a blank canvas unless we're updating which isn't what we want. So let's tackle this a different way.

Unless we tell it not to, our simulation will tell the renderer to keep updating at 60 fps, using a fair amount of processing power. If the particles aren't moving and you've stopped interacting with it, it doesn't need to keep draining your battery or spinning up your fans. So the rule we need to implement is, if we didn't clear our canvas, update pixels, click on, or touch the screen, stop running our draw loop.

First, the check for whether it needs updating...

needsUpdate() {
  return this.cleared || this.modifiedIndices.size;
}

And that's it!

And now our pausing and resuming logic!

In p5.js, you can do this with p.loop() and p.noLoop(), I just renamed them for clarity.

In essence, we're pausing any time the grid doesn't need an update, and resuming if we detect any user events. We could take this further by checking if the event is executing within the bounds of the canvas.

class EfficientLogic extends SlowLogic {
  logic(p, grid) {
    super.logic(p, grid);
    p.mouseDragged = () => {p.resume();}
    p.mouseMoved = () => {p.resume();}
    p.mousePressed = () => {p.resume();}
    p.touched = () => {p.resume();}
    p.after = () => {
      // If there's no reason to update, pause drawing to save cpu / battery!
      if (!grid.needsUpdate()) {
        p.pause();
      }
    }
  }
}

We're incrementing a counter any time there's an update to verify our logic is working as expected- that is the frame should stop incrementing when we aren't sending events and sand isn't falling.

Frame: 0

So - we have a relatively efficient renderer now! (and no more manual toggling of rendering) Pretty cool. But, there's more to do.

Fix the left bias

If you've been playing around with these, you may have noticed a frustrating left-bias.

(Try just holding / drawing in a single place for a little while)

Shout out to @jakear from HN for the suggested fix.

So, what's going on here? Well, when we update our pixels, we're going from the end to the beginning. This means that we're running the rules for each particle from right to left for each row, so the right particles will always execute their rules before the left ones, causing a bias.

Update-order bias is another common falling sand bug: the simulation looks directional because one side of each row always gets first chance to move.

What can we do?

Fortunately, we can randomly decide whether each row updates left-to-right or right-to-left, which reduces directional bias while keeping the simulation simple.

Save the row count so we can refer to it during update.

initialize(width, height) {
  super.initialize(width, height);
  this.rowCount = Math.floor(this.grid.length / this.width);
}

The core logic change: instead of iterating from end to beginning, we give ourselves an opportunity to change the direction we iterate for each row. We still iterate last row to first, but we randomly swap the direction we iterate.

update() {
  this.cleared = false;
  this.modifiedIndices = new Set();

  for (let row = this.rowCount - 1; row >= 0; row--) {
    const rowOffset = row * this.width;
    const leftToRight = Math.random() > 0.5;
    for (let i = 0; i < this.width; i++) {
      // Go from right to left or left to right depending on our random value
      const columnOffset = leftToRight ? i : -i - 1 + this.width;
      this.updatePixel(rowOffset + columnOffset);
    }
  }
}

While we're here... it's currently possible to overflow to the other side of the screen. Due to not properly checking bounds in our updatePixel function. Let's fix that!

Bounds checks matter in grid-based particle systems because the array is one-dimensional even though the simulation behaves like a two-dimensional world.

updatePixel(i) {
  const below = i + this.width;
  const belowLeft = below - 1;
  const belowRight = below + 1;
  const column = i % this.width;

  if (this.isEmpty(below)) {
    this.swap(i, below);
  // Check to make sure belowLeft didn't wrap to the next line
  } else if (this.isEmpty(belowLeft) && belowLeft % this.width < column) {
    this.swap(i, belowLeft);
  // Check to make sure belowRight didn't wrap to the next line
  } else if (this.isEmpty(belowRight) && belowRight % this.width > column) {
    this.swap(i, belowRight);
  }
}

So, because belowLeft and belowRight are calculated by adding or removing 1, if our particle was on the left or right edge of the screen, these variables could have represented a pixel on the next line! Fortunately we can check to make sure that they are actually in the right direction (less than our current column for left, and more than our current column for right).

Introduce velocity and acceleration

So here we are, spending all this time improving performance, surely there's a reason other than disciplined engineering practices! Right?

Right! Now that we've dramatically improved performance, we can update particles more than once per frame! Why is this a big deal? Because it means we can add acceleration and velocity and make the simulation feel much more fluid.

We need to wrap up this post as it's getting very long, so we're only going to tackle 1D velocity for now.

There are two key methods we'll need to make: updateVelocity and getUpdateCount. These methods will maintain the velocity of a particle, and communicate to our update function, how to update the particle based on its velocity. There are a few other changes we'll too.

Let's introduce our particle with velocity.

Adding the parameters we'll need...

// Our sand particle
constructor(p) {
  super(p);
  this.maxSpeed = 8;
  this.acceleration = 0.4;
  this.velocity = 0;
  this.modified = false;
}

Next, we need to keep track of our velocity, updating it according to acceleration and not allowing it to exceed maxSpeed.

updateVelocity() {
  let newVelocity = this.velocity + this.acceleration;

  if (Math.abs(newVelocity) > this.maxSpeed) {
    newVelocity = Math.sign(newVelocity) * this.maxSpeed;
  }

  this.velocity = newVelocity;
}

We then want to ensure we can reset the velocity (when it collides with something).

resetVelocity() {
  this.velocity = 0;
}

Now to the key logic for making use of velocity in our simulation... To make use of velocity, we're going to run the updatePixel function some number of times according to the velocity. Now if the velocity is 1, 2, or 3 (i.e. discrete) this isn't so hard! getUpdateCount would just return velocity.

But how do we deal with a velocity of 1.5 or 0.5?

The approach we're going to use is that any remainder of a whole number will be the probability that the update will occur this frame. Not perfect, but simple to implement.

getUpdateCount() {
  const abs = Math.abs(this.velocity);
  const floored = Math.floor(abs);
  const mod = abs - floored;
  // Treat a remainder (e.g. 0.5) as a random chance to update
  return floored + (Math.random() < mod ? 1 : 0);
}

Finally we want to have a generic update method that tells us if our particle was modified, i.e. "is in motion". To tell our modification tracking system that it shouldn't stop rendering.

update() {
  if ((this.maxSpeed ?? 0) === 0) {
    this.modified = false;
    return;
  }
  this.updateVelocity();
  this.modified = this.velocity !== 0;
}

And that's our particle!

Now we need to update our Grid update logic, and we'll be done. We're replacing the current code which just calls this.updatePixel(index).

const particle = this.grid[index];

// Update our velocity and save whether we modified the particle
particle.update();

if (!particle.modified) {
  continue;
}

// Make sure we note it was modified, as movement
// is probabilistic now.
this.modifiedIndices.add(index);

// Update the number of times the particle instructs us to
for (let v = 0; v < particle.getUpdateCount(); v++) {
  const newIndex = this.updatePixel(index);

  // If we swapped the particle to a new location,
  // we need to update our index to be that new one.
  // As we are repeatedly updating the same particle.
  if (newIndex !== index) {
    index = newIndex;
  } else {
    particle.resetVelocity();
    break;
  }
}

The very last step is that we update our updatePixel method to return the index of the index it was swapped with, or itself if it was not swapped.

So, we've made it to the end and I didn't even mention how to implement Wood. How might it be implemented, now that we have a concept of particles we can extend, and velocity?