I finally did something I'd been meaning to do for quite some time: I replaced the naïve collision check in Little Bouncing Ball with one that uses a quadtree.

Previously, it would check every ball against every destructible object on every frame, and at many points this caused the framerate to drop drastically. And this is, of course, a problem.

My graduate research (back in the day) was on dynamic spatial partitioning, and on trying to make an adaptive spatial partitioning structure that would be ideal regardless of the topology, spacing, density, and so on for objects in a scene. And the data structure I developed was quite good and scaled to millions of objects just fine!

So I tried implementing that for LBB a couple months ago, and... it really sucked. Getting things even working was difficult, and once I did, I found the overhead of the data structure to more than counteract any performance gains it made. Because I was vastly overthinking this, on a game where it doesn't have to scale to millions of objects, it just has to do a couple hundred.

And another thing about my research structure is that the overall coordinate bounds are, well, unbounded, and it would adapt to where objects actually are. But in LBB they more or less live within a 1280x720 rectangle, and so it's, you know, okay to have a fixed top-level node.

So that's what I did.

Anyway, before, during the really intense scenes, the profiler reported about 50% of the frame time being taken up by Actor:checkHitBalls(). And now that I have a quadtree in place, the profiler reports... about 50% of the frame time being taken up by QuadTree:Visit() and Actor:checkHitBalls() together.

However! The frame time is now much, much shorter, so this is a pretty big win.

The actual implementation ends up building a very coarse quadtree, mostly because of how the objects are sized and spaced apart in the level. If an object straddles multiple quadtree cells, it just keeps it in the internal node. So a lot of objects end up straddling boundaries way further up in the tree than it should. (This is a thing that was also addressed by my highly-scalable partitioning data structure, because the cell sizes adapted to where objects were, not based on the regular partitioning of the space.) This means that there's still some tuning that can be done to improve things; for example, I could work backwards from the typical object size to determine the ideal root cell bounds, so that more things fall into smaller/deeper buckets. Or I could simply allow objects to live multiple leaf nodes, and be smarter about how I track ball-object interactions, and so on, but I suspect that doing these things would bring back heavy overhead that doesn't actually help performance any.

Anyway, now the limiting factor in many sections is the complexity of the RoamingEye shader. For some reason the adaptive rendering stuff isn't being as aggressive as it could be at turning down the display resolution during these segments and so the framerate still drops to 30 sometimes, so I need to figure out something there.

As far as the whole quadtree-tuning thing goes, here's an example of the problem:

Here you can see the quadtree cells (this debug view only shows cells which have occupants, and not all the cells that exist in the tree but you get the idea). The problem here is that the game grid is essentially more or less made of 32x32 tiles which are offset by 32 units from the edges. (There aren't actually any tiles in this game; that's just how brick objects tend to be placed.) So for better tiling I'd want the quadtree boundaries to end to fall on multiples of 32.

1280/32 = 40, and 720/32 = 22.5. Neither of these are particularly good increments!

So, the next power-of-two interval up from 40 is 64, and from 22.5 is 32. So what happens if we make the quadtree 2048x1024 instead?

Well, the boundaries line up much better and the cells are a lot smaller now, but there's still a bunch of objects that are seen as straddling a barrier where they shouldn't. Ah, but the problem there is that I'm being silly about how I consider things which are tangent to a line. So with a tiny logic fix there:

Well, that's looking better, but it occurs to me that the problem here is that the cells are all squashed rectangles. Oh, but we could make them square, by making the root node 2048x2048:

That's looking better, but surely it could work better for more of the scenes by offsetting the grid by, say, one "tile" up and to the left?

  (insert Italian Chef Kiss emoji here)

The finer granularity of the quadtree doesn't actually help performance in this case (the smaller per-cell object count is countered by the larger number of cells to traverse) but it's still nice for aesthetics. Another potential tweak to do in the future would be to only split cells which have a certain number of objects in them, for example, but that's not something to worry about for this game.