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