I was tinkering with the PICO-8 bubble screensaver today and I found a simple optimization that allows the game to support 50 bubbles instead of 40. (Edit: I’ve since optimized it again)
Background
The game needs to know which bubbles are colliding so that it can push them apart. The easiest method of finding which bubbles are colliding is to check each bubble against every other bubble. The problem with this approach is that it needs (n-1)^2 checks, which is a lot of checks and very performance expensive. Originally, I tried a bunch of ways to get this number lower, but what I settled on was dividing the screen into four sections and only checking against bubbles in the same section. This reduced the number of checks to about (n/4)^2*4 or 1/4 the checks (the division of the screen doesn’t guarantee an equal number of bubbles in each section and sometimes bubbles overlap the dividing line and are in both sections, so about 1/4.)
The new optimization
The optimization I found is once the game finds all a bubble’s collisions, remove the bubble from the list of bubbles to check. Then each subsequent bubble only has to check against the remaining bubbles. That’s about ((n-1)/4 triangular)*4 or ~2/3 of the collisions to check. This is an obvious change, but I didn’t think of it when I was originally making the game.
The gain is a 30% reduction in CPU usage at 40 bubbles. So now with the extra CPU usage freed, the game can handle 50 bubbles at a time. Not bad for one line of code I could’ve added earlier!
PS: I wrote this late at night, so let me know if my math is broken xD
nice post
Thanks! :)