Devlog #9:
Intro
I added spatial partitioning to the engine to speed up collisions when you have a lot of balls in a scene.
Partitioning explanation
Spatial partitioning is an optimization that divides the world into a grid, so balls only check other balls that are in close cells, instead of every ball checking all others, which is O(n^2). It seems pretty simple, but I tried 4 different ways before getting a good result. Judging by the time logged, I struggled.
First Attempt (Dense grid)
I first tried a naive implementation, which was making a big grid, with each cell having a list of pointers to balls that are in it. The problem is, each cell needs to have the total amount of balls that could be in it allocated.
For the best performance, each grid cell should be the same size as a ball, and for the size I use here, you need the grid dimensions to be in the 100s. with 1000 balls, and with 64 bit pointers, you could have 1000 * 8 * 300 * 300 bytes allocated total, ~720 MB. You can get away with a lot less pointers, but that still wasn’t satisfying, or flexible.
Second Attempt (Sparse grid)
My second try was a grid, but you only store cells which have balls in them. This doesn’t solve the high number of pointers per cell, but it uses less cells overall. It should’ve been easier, but C doesn’t have any built in hashmaps. The physics code doesn’t use many libraries, and I didn’t want to rely on more, so I had the bright idea to make my own hashmap. It didn’t work and I gave up, and that was the end of the sparse grid.
Third Attempt (Resizable arrays)
The third attempt was like the first, but I decided to try allocating the memory on the fly, when balls moved around, but it didn’t work out.
Working Attempt!! (Sorting)
The most successful attempt was a grid, every cell is allocated, and yet, uses the least memory. Instead of storing pointers, each cell only stores two things: An offset and a length. Just indices into the ball array, which sounds easy, but then you realize - the balls are in a random order. To fix this, when updating the grid, you sort the balls into the cell they’re in. You may think that going into the dark cave of sorting is a bad idea, but here, it’s just a counting sort. Then it sets each cell’s fields, and you have your partitions.
Detecting Collisions
Collisions are easier than constructing the grid, you just check every ball, find its cell, check balls in close cells, then you’re done.
Struggles
There was a lot of friction with memory errors. To fix them, I learned GDB, and learnt about sanitizers, which detect lots of hard to catch memory errors.
One time the program would randomly crash, and it was really hard to fix, but a sanitizer detected an easy out of bounds error when rendering. Not even a physics thing. :(
Sorry!!
Sorry for the long post, and the time it took me to post it, The devlog guide says to keep it short and post often, but I fell down a rabbit hole with optimizing, and was putting off writing as I knew it would be unwieldy in length.
I haven’t implemented partitioning in 3d yet, but it should be easy to transfer over.
It’s hard to see the balls in the video, but I want to keep the video smaller.
It gets laggy in the video as well, but there are 7000 balls in the scene at the end, and I check collisions 15 times per frame, I am also recording too.
Try it out
If you read all the way down here, you might want to try the engine. I have a build on my pages, but it’s kinda slow on web.
- Click to attract
- P to set where the balls shoot to when spawned
- Enter to spawn balls
- Scroll to change spawn speed
(at least until I change the demo). On some screens the simulation doesn’t show up until you click fullscreen.
Sorry for weird wording, max devlog size is 4k characters.
