Class: AABBTree

Inherits:
Object show all
Extended by:
Forwardable
Includes:
AABBTreeDebugHelpers
Defined in:
lib/gamebox/core/aabb_tree.rb

Overview

AABBTree is a binary tree where each node has a bounding box that contains its children’s bounding boxes. It extrapolates and expands the node bounding boxes before inserting to lower the amount of updates to the tree structure. It caches all leaf node collisions for quick lookup.

Constant Summary collapse

DEFAULT_BB_SCALE = 
1
VELOCITY_SCALE = 
3

Instance Attribute Summary collapse

Instance Method Summary collapse

Methods included from AABBTreeDebugHelpers

#each, #each_leaf, #each_node, #valid?

Constructor Details

#initialize ⇒ AABBTree

Returns a new instance of AABBTree.



14
15
16
17
 
# File 'lib/gamebox/core/aabb_tree.rb', line 14

def initialize
  @items = {}
  @root = nil
end

Instance Attribute Details

#items ⇒ Object (readonly)

Returns the value of attribute items.



10
11
12
 
# File 'lib/gamebox/core/aabb_tree.rb', line 10

def items
  @items
end

Instance Method Details

#collisions(item, &blk) ⇒ Object 



24
25
26
27
28
29
30
 
# File 'lib/gamebox/core/aabb_tree.rb', line 24

def collisions(item, &blk)
  leaf = @items[item]
  return unless leaf && leaf.cached_collisions
  leaf.cached_collisions.each do |collider|
    blk.call collider.object
  end
end

#insert(item) ⇒ Object 



32
33
34
35
36
37
 
# File 'lib/gamebox/core/aabb_tree.rb', line 32

def insert(item)
  raise "Adding an existing item, please use update" if @items[item]
  leaf = AABBNode.new nil, item, calculate_bb(item)
  @items[item] = leaf
  insert_leaf leaf
end

#query(search_bb, &callback) ⇒ Object 



19
20
21
22
 
# File 'lib/gamebox/core/aabb_tree.rb', line 19

def query(search_bb, &callback)
  return unless @root
  @root.query_subtree search_bb, &callback
end

#remove(item) ⇒ Object 



39
40
41
42
43
44
45
 
# File 'lib/gamebox/core/aabb_tree.rb', line 39

def remove(item)
  leaf = @items.delete item
  if leaf
    @root = @root.remove_subtree leaf 
    clear_cached_collisions leaf
  end
end

#update(item) ⇒ Object 



47
48
49
50
51
52
53
54
55
56
57
58
 
# File 'lib/gamebox/core/aabb_tree.rb', line 47

def update(item)
  node = @items[item]
  if node && node.leaf?
    new_bb = calculate_bb(item)
    unless node.bb.contain? item.bb
      node.bb = new_bb
      clear_cached_collisions node
      @root = @root.remove_subtree node
      insert_leaf node
    end
  end
end