Optimizing Particle Systems with a Grid Lookup and Spatial Hashing

In this article we pick up from where we left off in the previous tutorial on particle systems. The main bottle-neck of our primitive collision system is the number of checks that have to be made to determine if two particles collide. In this naive approach, each particle is compared against each other particle, which is a rapidly increasing number of checks, the more particles there are in the scene. In this post we'll have a look at a method to optimize this.

To recap the previous post; last time we dealt with the fundamentals of object oriented programming, to create a system with multiple entities that can interact with each other according to our specifications. We also implemented the physics involved in making our particles move around on the canvas, such that they fall towards the bottom of the canvas, and collide with the boundaries of the canvas as well as each other.

Here's what we'll have put together by the end of this tutorial - (might not display in email):

On Algorithmic Complexity

Before we try to optimize our particle system it's probably best to have a look at algorithmic complexity - what that actually means - and how to asses whether a piece of code is considered efficient at what it does, or not.

In the case of our particle system, as we crank the number of particles in the scene we'll quickly reach a threshold where it takes the CPU more time to execute one iteration of the draw loop, than the duration of a single frame. Say we have two particles in the scene, we would just have to make a single check.

Now say we have four particles in the scene, how many collision checks do we have to make to determine if any two particles are colliding? The first particle would have to be checked against the other three, the second one against the third and the fourth, and the third one against the fourth. So 6 checks in total.

Now let's crank up the number of particles even more, what if we have 20 particles? That would be 190 checks, for 50 particles 1225 checks, and so on. And that's assuming that we've implemented our code in an efficient manner, our final code from the last time doesn't actually remember that particles that have already been checked against each other, hence there's multiple duplicate checks as well.

At a larger number of particles, this will cause noticeable visual stutter/lag as the browser is playing catch-up with the frame rate, never really making it in time. Moreover, Javascript is not the fastest language out there. When working with the java-like processing language, instead of P5, we can get away with a lot more inefficiency, due to it being a compiled language, as opposed to it's browser compatible younger sibling P5.

Towards a more efficient approach

Well, how do we make this more efficient? I talked about the powerful grid lookup method in a previous article:

A Simple Solution for Shape Packing in 2D

Shape packing is a popular type of sketch in gen-art, but is often trickier than it might seem when you try to pack anything more complicated than a simple circle. In this post we’ll have a look what goes into collision detection as well as a strategy to pack any arbitrary shape in 2D.

Ahmad MoussaGorilla Sun

Back then however, it was in the context of a static sketch - this time around we're dealing with moving particles that can update their positions, which is slightly trickier.

We can make an optimization to our procedure based on a simple observation: if two particles are very far apart, we don't need to check if they collide - we only need to check for collisions between particles that lie in each other's vicinity. For this we need some way to determine what particles are close to each other and which aren't.

One strategy in that regard is a grid lookup. A grid lookup divides the canvas into smaller rectangular patches, where each patch knows which particles it currently contains. This way we only need to check into which patch a particle falls into, fetch the other particles that are currently in that patch and compare against them.

I believe that this is also frequently called spatial hashing, where the canvas (or the scene in the case of a video game), is divided into several bins/buckets, each of which has knowledge about which particles/entities it contains. Spatial hashing doesn't necessarily have to be done with a grid, but can frequently make use of some other data structure.

Now, let's get started on implementing a grid lookup!

Implementing a Grid Lookup

The best way to represent our grid is by modeling it as another object:

class Grid {
  constructor(canv_wid, canv_hei, s) {
    
    this.cellSize = s;
    
    this.numCols = Math.ceil(canv_wid / s);
    this.numRows = Math.ceil(canv_hei / s);
    
    this.cells = [];
    
    for (let x = 0; x < this.numCols; x++) {
      this.cells[x] = [];
      for (let y = 0; y < this.numRows; y++) {
        this.cells[x][y] = [];
      }
    }
  }
}

There's a few things that we need to do in the constructor to set up our grid. The constructor takes as inputs the dimensions of the canvas as well as a size parameter which determines how large the grid patches are - this parameter will be important later on. Here you might notice that these rectangular patches are also called cells. I'll use both terms interchangeably.

Next we need to determine how many columns and rows of patches there need to be to cover the entire canvas. This is done by dividing the respective canvas dimensions by the cell size parameter. We are taking the ceiling of this computed value to ensure that the entire canvas is covered by cells.

In this manner we have essentially created a 2 dimensional array of cells that cover the canvas. Each cell itself is an array that will in the future contain a number of particles.

Adding and Removing Particles

This grid is only useful if we can also add and remove particles to/from it. We'll do this via member functions:

addParticle(particle){
  let col_idx = Math.floor( particle.pos.x / this.cellSize);
  let row_idx = Math.floor( particle.pos.y / this.cellSize);

  this.cells[col_idx][row_idx].push(particle)
  particle.gridCell = { col: col_idx, row: row_idx }
}

Depending on the particle's position we need to compute into which grid cell it falls. We do so by dividing it's coordinates by the cell size, and then floor that number to an integer such that we can use it as an index to access the grid. Then we simply push that particle to the array of particles that represents the corresponding grid cell.

There's also another special thing that we need to do here, we have to add a new property to our particle object called gridCell - the particle itself also needs to know in which grid cell it falls into, this is important for us to fetch nearby particles to check for collisions. Hence, we simply add the indices of the grid cell as a property to the particle.

Now removing a particle is done in a very similar manner:

removeParticle(particle) {
  let { col: col_idx, row: row_idx } = particle.gridCell
  let cell = this.cells[col_idx][row_idx];
  let arr_idx = cell.indexOf(particle);
  cell.splice(arr_idx, 1);
}

Here we destructure the particle's gridCell property - which we created when we added it to the grid - into a column and row index. We'll also get the index of this particle in the particle array of the cell and make use of the splice function to remove it.

Getting a Particle's Neighbours

Now for the main purpose of the grid, fetching a given particle's neighbors:

getNeighbors(particle) {
  let top_left = [
    floor((particle.pos.x - particle.radius) / this.cellSize),
    floor((particle.pos.y - particle.radius) / this.cellSize),
  ]

  let bottom_right = [
    floor((particle.pos.x + particle.radius) / this.cellSize),
    floor((particle.pos.y + particle.radius) / this.cellSize),
  ]

  let neighbors = []
  for (let i = top_left[0]; i <= bottom_right[0]; i++) {
    for (let j = top_left[1]; j <= bottom_right[1]; j++) {
      if (i < 0 || j < 0 || i >= this.numCols || j >= this.numRows) continue
      let c = this.cells[i][j]
      for(let p of c){
        // don't add the particle itself
        if(p != particle) neighbors.push(p)
      }
    }
  }

  return neighbors
}

We essentially need to determine all the cells that the given particle is touching - for this we need to consider it's radius. We find the column and row indices for the cell that the particle's top leftmost part falls into, as well as the indices of the cell where it's bottom rightmost part falls into. Then we loop over all the cells in between, because these could potentially have particles that we're colliding with.

We fetch all of the particles that are inside of these cells and return them in form of an array.

Changes to the main draw loop

The draw loop needs to account for our grid lookup:

function draw() {
  background(220);

  for (let p of particles) {
    let neighbors = grid.getNeighbors(p)
    p.checkCollision(neighbors)
    p.updateState();
    p.display();
    p.displayDirection();
  }

  for (let p of particles) {
    p.checkEdges();
  }

  // reset the grid by removing all particles and adding them again
  for (let p of particles) {
    grid.removeParticle(p)
    grid.addParticle(p)
  }
}

The checkCollision() function of each particle now accepts an input parameter, which is simply a list of particles - it's neighboring particles. The function itself didn't change overall except that it now loops over this list instead of all other particles.

We also check for the canvas boundaries in a separate step after collisions have been resolved. We want to make sure that the particles never leave the canvas, as it would throw an error when we try to look up a particle that is outside of the canvas boundaries.

Lastly, and very importantly, we need to account for the movement of the particles, there's a chance that they will end up in different grid cells every frame. This can simply be solved by removing all particles from the grid and then adding them again. This can however also be done at the end of a particle's update function:

grid.removeParticle(this)
grid.addParticle(this)

The grid lookup in action

And here's all of what we covered in action, click and drag your mouse across the canvas to generate new particles:

If you're on firefox this sketch might run just a little bit slow at a very large number of particles ~5k, whereas it runs decently on the other common browsers like Chrome and Brave.

Comparison with the naive Approach

So how much faster is this method to the naive approach in which we loop over all other particles? Let's do a little test and compare the average time it takes the draw loop to compute one iteration of our system.

Not a super accurate test by any means, but simply using javascript's console.performance() function I measured the time to compute all of the functions related to computing and drawing the particles:

function draw(){

  // other code
  
  let start = performance.now();
  // particle code goes here

  let end = performance.now();
  sumFrameDuration += end - start

  // other code
  
  if(frameCount > 1200){
    console.log(sumFrameDuration/1200)
    noLoop()
  }
}

I ran both the naive approach from last time as well as the one with the grid lookup method on 5000 particles, for a duration of 20 seconds and 60 FPS. The naive approach takes roughly 203 ms per frame, whereas the grid lookup only takes roughly 4 ms!

That is much, much faster!

Further Improvements ... ?

There's a few things that we can do to further improve this - starting with the obvious ones:

1. We only need to check for collision with the canvas boundaries if the particle is in one of the grid cells located at the border of the grid.
2. We also only need to update a particle's grid cell if it's new position falls into a new grid cell.

We can account for both of these things in one swoop by modifying the code in our draw loop:

for (let p of particles) {
    let neighbors = grid.getNeighbors(p)
    p.checkCollision(neighbors)
    p.updateState();
}
  
for (let p of particles) {
  let px = ( p.pos.x / grid.cellSize ) | 0
  let py = ( p.pos.y / grid.cellSize ) | 0

  if( px == 0 || px == grid.numCols-1 || py == 0 || py == grid.numRows-1 ){
    p.checkEdges();
  }

  if( px != p.gridCell.col || py != p.gridCell.row){
    grid.removeParticle(p)
    grid.addParticle(p)
  }

  p.display();
}

We can also save a couple of micro-barks by using a nifty bit shifting trick to floor the numbers.

Computing Square roots

The Euclidian distance requires the computation of a square root, this is not efficient and can quickly add up to a significant overhead. Thing is, we don't actually have to compute the square root, we can do without it and substitute with an alternative measurement that works just as well and doesn't require a square root - the squared distance:

function squareDist(p1, p2) {
  return (p1.x - p2.x)**2 + (p2.y - p1.y)**2
}

For this we also need to modify the calculation of the collision resolution:

checkCollision(otherParticles) {
  for (let n = 0; n < otherParticles.length; n++) {
	let other = otherParticles[n]
    if (this != other) {
      let distance = squareDist(this.pos, other.pos);
      let minDistance = (this.radius + other.radius)**2; // squared sum

      if (distance <= minDistance) {
        // everthing here stays the same

        // Repulsion force needs to be divided by square of mass
        this.pos.sub(p5.Vector.div(repulsion, this.mass**2));
        other.pos.add(p5.Vector.div(repulsion, other.mass**2));
      }
    }
  }
}

I'm also not certain if the other p5 vector operations are the fastest out there, so there might be some merit in improving those as well.

Duplicate Collision Checks

There's a fantastic series of videos on this very topic - particularly for game development - by SimnDev on Youtube, the linked video is the second part in which he talks about optimizing his grid lookup method with various tricks:

One of them is a simple query counter to avoid duplicate collision checks. We add a counter to the grid class and a counter to each particle. The grid's counter gets initialized to 0, whereas the particle counters are initialized to a value of -1.

Now in the method that fetches a particle's neighbors, we increment this counter indicating that a new query has been made. Before we add a particle to the array that will be returned we check if it's query counter is equal to the current query's value, if it is then we have seen this particle already. Otherwise we haven't encountered it yet and add it to the array, and also update it's query counter:

let neighbors = []
let queryId = this.queryIds++ // the grid's query counter

for (let i = top_left[0]; i <= bottom_right[0]; i++) {
  for (let j = top_left[1]; j <= bottom_right[1]; j++) {
    if (i < 0 || j < 0 || i >= this.numCols || j >= this.numRows) continue
      let c = this.cells[i][j]
      for (let p of c) {
      // don't add the particle itself and check query id
      if (p != particle && queryId != p.queryId ) { 
        neighbors.push(p);
        p.queryId = queryId; // assign new query id
      }
    }
  }
}

return neighbors

Other ideas

There's some more ideas here:

1. Replacing the for ... of loops with imperative loops could also have some merit as it seems that imperative loops are slightly faster. But then we would also have to manually access the arrays which I'm not certain would ultimately win us any time. Worth a try though.
2. Choosing the optimal cell size is also very important, as it balances between the accuracy of the collision detection and the speed of the overall procedure. I think that a cell size that's slightly larger than the largest diameter of any particle is best in this case. But if you have wildly varying particle sizes then a different value might be better.

Improved Grid Performance

I did another test, this time with 10k particles at 60fps for 20seconds, and with all of these small improvements we shave off 2ms on average, which I think is pretty good all things considered.

At a larger number of particles we will probably notice an even larger difference, at lower particle numbers we might actually be a bit slower due to all of the checks adding an overhead instead of making things faster.

And here you can try it for yourself - the difference is most likely not very noticeable though:

Considerations

I ended up spending much more time on this than I initially anticipated, finding myself descending an optimization rabbit hole. Here I have to ask myself though - what's the point of all of this?

What is an actual use case of a large particle system in Javascript? I don't actually know; this could be useful for a browser based video game in which we have to determine collisions between entities in the game, but then again, it would have to be a very special type of game to require such a large number of particles/entities/units. In that case you should probably consider using something other than JS. If it has to be in the browser then a shader is probably the way to go, otherwise you'd just use a compiled language that just inherently runs faster than JS.

That aside, it's still an interesting problem worth exploring, even though the upper bound of this grid lookup method is reached fairly quickly it's still useful for many things, for instance something I did with random walkers where I had to find nearby nodes quickly:

Closing Thoughts

For the sake of completeness here's the code for the three versions that we ultimately ended up with - the naive approach, the grid implementation, and the improved grid implementation:

This has been a very satisfying learning experience, and I might just try to build my own little game in the coming weeks - it's been something that I've wanted to do for a while now, and a little shmup (shoot em up) doesn't seem so complicated anymore.

That's it from me, let me know what you thought about this article in the comments 👇 otherwise consider sharing the post with friends and family on your socials, as well as signing up to the newsletter to receive updates whenever there's new content. Cheers, happy coding ~ Gorilla Sun 🌸