class QuadTree
Constants
- NODE_CAPACITY
Attributes
ne[RW]
nw[RW]
objects[RW]
se[RW]
sw[RW]
Public Class Methods
new(boundary)
click to toggle source
# File lib/misc/quad_tree.rb, line 5 def initialize(boundary) @boundary = boundary @objects = [] end
Public Instance Methods
insert(game_object)
click to toggle source
# File lib/misc/quad_tree.rb, line 10 def insert(game_object) return false unless @boundary.contains?( game_object.location) if @objects.size < NODE_CAPACITY @objects << game_object return true end subdivide unless @nw return true if @nw.insert(game_object) return true if @ne.insert(game_object) return true if @sw.insert(game_object) return true if @se.insert(game_object) # should never happen raise "Failed to insert #{game_object}" end
query_range(range)
click to toggle source
# File lib/misc/quad_tree.rb, line 44 def query_range(range) result = [] unless @boundary.intersects?(range) return result end @objects.each do |o| if range.contains?(o.location) result << o end end # Not subdivided return result unless @ne result += @nw.query_range(range) result += @ne.query_range(range) result += @sw.query_range(range) result += @se.query_range(range) result end
remove(game_object)
click to toggle source
# File lib/misc/quad_tree.rb, line 30 def remove(game_object) return false unless @boundary.contains?( game_object.location) if @objects.delete(game_object) return true end return false unless @nw return true if @nw.remove(game_object) return true if @ne.remove(game_object) return true if @sw.remove(game_object) return true if @se.remove(game_object) false end
Private Instance Methods
subdivide()
click to toggle source
# File lib/misc/quad_tree.rb, line 69 def subdivide cx, cy = @boundary.center hx, hy = @boundary.half_dimension hhx = (cx - hx).abs / 2.0 hhy = (cy - hy).abs / 2.0 @nw = QuadTree.new( AxisAlignedBoundingBox.new( [cx - hhx, cy - hhy], [cx, cy])) @ne = QuadTree.new( AxisAlignedBoundingBox.new( [cx + hhx, cy - hhy], [cx, cy])) @sw = QuadTree.new( AxisAlignedBoundingBox.new( [cx - hhx, cy + hhy], [cx, cy])) @se = QuadTree.new( AxisAlignedBoundingBox.new( [cx + hhx, cy + hhy], [cx, cy])) end