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

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

- (AABBTree) initialize

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

- (Object) items (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

- (Object) collisions(item, &blk) 



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

- (Object) insert(item) 



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

- (Object) query(search_bb, &callback) 



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

- (Object) remove(item) 



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

- (Object) update(item) 



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