Dealing With Thousands Of Game Objects - Developing Games With Ruby - page 161

18 def intersects? (other)
19 ocx, ocy = other . center
20 ohx, ohy = other . half_dimension
21 odhx = (ohx - ocx) . abs
22 return false unless ( @center [0] + @dhx ) >= (ocx - odhx)
23 return false unless ( @center [0] - @dhx ) <= (ocx + odhx)
24 odhy = (ohy - ocy) . abs
25 return false unless ( @center [1] + @dhy ) >= (ocy - odhy)
26 return false unless ( @center [1] - @dhy ) <= (ocy + odhy)
27 true
28 end
29
30 def to_s
31 "c: #{ @center } , h: #{ @half_dimension } "
32 end
33 end

If you dig in 10-partitioning/specs , you will find tests for this implementation
too.

The math used in AxisAlignedBoundingBox#contains? and
AxisAlignedBoundingBox#intersects? is fairly simple and hopefully very fast,
because these methods will be called billions of times throughout the game.

QuadTree For Game Objects

To implement the glorious QuadTree itself, we need to initialize it with boundary, that
is defined by an instance of AxisAlignedBoundingBox and provide methods for
inserting, removing and querying the tree. Private QuadTree#subdivide method will
be called when we try to insert an object into a tree that has more objects than it's
NODE_CAPACITY .
10-partitioning/misc/quad_tree.rb

1 class QuadTree
2 NODE_CAPACITY = 12

attr_accessor :ne , :nw , :se , :sw , :objects

3

4
5 def initialize (boundary)
6 @boundary = boundary
7 @objects = []
8 end
9
10 def insert (game_object)