[epiar-devel] The Epiar QuadTree

[Matthew Zweig]

> I don't entirely understand how the quadtree handling works to help you with this. Could you go into detail what a quadtree is again and how it helps in this situation vs just a list of planets with Cartesian coordinates? Is it that a quadtree helps you find the next nearest planet without doing it in O(n) time?
> 
> - Chris


I'm not sure if the QuadTree actually does make dealing with planets easier, but I think that I should take this time to explain how the QuadTree works.

I created a debug view for the QuadTree.  I don't expect to keep in release versions of Epiar, but it's helpful for working with the QuadTrees.
http://i.imgur.com/m1PW3.png

Basic Idea
The QuadTree is a reasonably simple recursive structure.  Each Quadtree has a center and a radius that define the space that it is responsible for.  A QuadTree starts as a 'leaf'.  When sprites are inserted into a quadtree leaf, the leaf adds them to a simple list.  When that list gets too full, the Leaf turns into a Node and inserts the sprites into its children leaves.  A Node splits its space into 4 quadrants, where each quadrant is represented by a subtree.  Whenever a sprite is inserted into a Node, the node passes it down to one of the 4 quadrants; all of the sprites are stored in the leaves of the tree.

Sparseness
The QuadTree implementation we're using is a sparse implementation, meaning that we don't create or maintain quadrants that do not have any objects in them.  ( A fully populated QuadTree would have 4^(H+1)-3 nodes where H is the tree height.  A tree height of 8 isn't unusual, which would mean 262141 Nodes if I did the math right.) Most Nodes do not need to populate each subtree, so while some areas have height 8, others need only height 1 or 2.

ReBallancing
We do periodic maintenance via the ReBallance function which turns leaves into nodes, nodes into leaves, and removes unused subtrees so that we get the best search results that we can.  You only need to ReBallance on insertions or deletions, but I found recently that in combat situations projectiles were causing some reballance thrash since they are added and deleted so much.  The current method is to set a dirty bit whenever sprites are inserted or deleted, and ReBallance recursively once per tick.  I'm still playing with this implementation though.

Out Of Bounds
Since each QuadTree is by definition a bounding box, it can only contain sprites within a specific area.  It would be fairly easy to implement an Infinite Canvas if we chose to abandon the QuadTree, but I don't think that that tradeoff is work it.
We do periodic maintenance via the FixOutOfBounds function.  Since we're not dealing with static objects, the sprites have a tendency to move outside of a given quadrant.  After all of the Sprites have been updated, we do a pass through the tree looking for sprites that don't belong in the QuadTree that they are currently in.  Any sprite that fails the boundary check is passed up to the parent node.  The parent node does a check to try and push each OOB sprite back down to one of it's children, then passes the rest back up.  When they reach the tree root they get returned to the SpriteManager.  On the Infinity branch, the SpriteManager reinserts the sprite into the appropriate quadrant (creating it if necessary).  On the current master branch, all ships that go out of bounds are permanently lost!  The Quadtree on master has a radius of 65536 pixels, but it's possible to get there if a ship gets really bored (or buggy).

Searching
This is the whole point of the QuadTree!  Whenever you need to search for sprites near a specific point (projectile collisions for example), you query the QuadTree giving it a point and radius.  The QuadTree Nodes recursively query their subtrees and the Leaves do range checks against each of their sprites.  So far this is just a O(N) search with a lot of overhead, but we haven't taken into account that we're doing spacial searching of a spacially sorted tree.  Each QuadTree can short circuit the search if it can determine apriori that none of its Sprites could possibly be within the search area.  For adequately narrow search criteria this can drastically cut down on the search time.  (If you do a search with a very large radius, the overhead can add up so don't do big searches without a good reason.)  Once the nearby list percolates back up to the SpriteManager, the list is sorted by distance from the search point.

The QuadTree is good for:
	Finding projectile collisions.
	Finding the Sprites that are currently on screen or on radar.

The QuadTree is not great for:
	Finding the closest ship inside of a huge radius.

(The QuadTree will find the closest ship inside a huge radius in reasonable time, but it isn't currently designed for this purpose.  We could solve this by having each Node maintain a list of all the sprites that it contains and short circuiting a search that fully encompasses tree.  Alternatively, we could add a FindNearest function that would return only one Sprite, but I'll need to think about that.)

I hope that this helps clear things up, let me know if anyone has any questions or suggestions,
~Matt Zweig