Spatial Partitioning

By Aaron Holowienka

This week’s big task was to implement spatial partitioning. I had learned a little about spatial partitioning in an earlier class, but did not remember much, so I decided to just go straight into making a quadtree. I thought I did this pretty effectively, so I moved on to doing an octree, which I again thought went alright. Upon showing this to my team and then doing a little research I quickly realized I didn’t actually do an octree at all. All I did was split the terrain of our map into eight buckets.

After this I did a little research on true quadtrees and then started over. I ended up going with a quadtree because our game doesn’t really have any verticality, so I can ignore a dimension. Implementing the quadtree was fairly straight forward, with the only hiccup being accounting for the size of our objects and our world. The one tutorial I followed just used points and leaves that can only hold a single point, but that wasn’t practical for our game. I had to make the smallest bucket a square unit bigger than our biggest cover to ensure that everything fits into a bucket, which also required me to allow for leaves to be capable of holding multiple objects. This was simple, but the biggest problem was solving objects that overlap multiple leaves, to which I solved by sending each corner of the bottom of our objects into the quadtree, so they are all accounted for. I still have to solve the problem of a corner sitting on an exact border of two leaves, but that is where I am starting next week.