Game Development Reference
In-Depth Information
Visual representation of quadtree
Implementing A Quadtree
There are some implementations of quadtree available for Ruby -
rquad
,
rubyquadtree
and
coupled) to our game using the pseudo code from Wikipedia.
Axis Aligned Bounding Box
One of prerequisites of quadtree is
Axis aligned bounding box
, sometimes referred to as
“AABB”. It is simply a box that surrounds the shape but has edges that are in parallel with
the axes of underlying coordinate system. The advantage of this box is that it gives a rough
estimate where the shape is and is very efficient when it comes to querying if a point is
inside or outside it.