Spatial partitioning

Today I messed with spatial partitioning, finally getting a first-pass on a quadtree working.

This is still inefficient and not fully correct (it's allowing some pointless dead space) but it's nice to have a basic version in place. I feel like I understand the concept in a way I hadn't fully grasped previously - even though it's not particularly difficult.

For the uninitiated: Quadtrees are a bit like binary trees for cutting an area up into pieces, except rather than 2 splits (left and right), they split into 4 pieces each time. They recursively subdivide the space up, as you can see in the picture (the squares getting smaller where there is more 'stuff').

This is because it is much faster to make queries about a particular area in space when you structure things into a tree in this way. The number of 'jumps' (checks to make) from node to node in the tree can be tiny, even for a tree that spans a huge amount of space.

The reason for these 'queries' is to reduce the amount of collision checks: Instead of having every object in the world check for collision against every other, we can reduce the work to only checking against objects found to be in the same 'area' in the tree.

It's important to note too that this isn't a 'premature optimization': brute force collision simply isn't going to work for the intended scale of this game and it will break down very quickly. I want to get a solid approach in early so it's less daunting a prospect [vs. retrofitting it in later]

Anyway: Onward to refining this to a more performant implementation, and resolving issues around objects spanning across areas (the 'loose' part in a loose quadtree)