More progress: Quad trees
Today's subject: quad trees. Here is a nice little tutorial on the subject.
Until now I was using a naive method of rendering the level shapes (polygons and circles): I looped through them all, did a bounding box check* to see if they're visible in camera, and rendered if they were. This works fine for small levels (and indeed for the current test level, although I keep adding more and more stuff to it — nevertheless it's still quite modest in size), but for larger levels it can become a problem, especially on slower machines.
So I decided to add quad trees to speed up the level rendering process. The level shapes are stored in three different quad trees (one for collidables, one for background and one for foreground shapes). The trees are queried for visible objects, which then get rendered. Works nice and smooth, and the performance goes through the roof, right? Well… not quite.
Since the level shapes can have various opacities, it is important to render them exactly in the order that is specified during level creation (in the Inkscape SVG file). In the triangulation & convex decomposition process the original shapes get split up. It was not a problem during the naive approach — the shape parts were in a list and the original order was preserved. Quad tree on the other hand doesn't necessarily preserve that order, to my great disappointment. It makes sense of course, I just hadn't thought about it until I saw the effect: a few of the level shapes were rendered out of order.
At first I tried to come up with a way to partition the quad tree so that the order would stay correct, but that didn't work too well. In the end I ended up just sorting the queried objects before rendering. That works perfectly, but introduces a new speed hit; the sort. So in all, the supposedly great speed increases of the mighty quad tree turned out to be only a modest gain, since I now need to sort the visible pieces.. Still, I'm confident that the quad trees were worth it, as the levels keep getting bigger and more complex it will surely show more greater effect. 🙂 And at least I found that enormous bug in the bounding box culling! 😉
Check out a few debug screens below, quad trees are the white lines.
*) I actually found one of the most stupid bugs I've ever done in the bounding box check code. It was actually checking bounds from the world origin (0,0) to the object lower right corner, instead of from the object upper left to lower right! That means that the bounding boxes got very big and only the objects to right and down from the camera view were culled properly.. Ouch.
Follow @mhgames_
