Class: AABBNode

Inherits:
Object show all
Includes:
AABBNodeDebugHelpers
Defined in:
lib/gamebox/core/aabb_node.rb

Overview

This is the primary element in an AABBTree. It acts as both containing elements and leaf elements. Leaves have an @object, containers have @a and @b nodes. All leaf nodes have a cached list of collisions that contain references to other nodes in the tree.

Instance Attribute Summary collapse

Instance Method Summary collapse

Methods included from AABBNodeDebugHelpers

#contains_children?, #each_leaf, #each_node, #root

Constructor Details

#initialize(parent, object, bb) ⇒ AABBNode

Returns a new instance of AABBNode.



9
10
11
12
13
14
15
16
 
# File 'lib/gamebox/core/aabb_node.rb', line 9

def initialize(parent, object, bb)
  @parent = parent
  @a = nil
  @b = nil

  @object = object
  @bb = bb
end

Instance Attribute Details

#a ⇒ Object

Returns the value of attribute a.



7
8
9
 
# File 'lib/gamebox/core/aabb_node.rb', line 7

def a
  @a
end

#b ⇒ Object

Returns the value of attribute b.



7
8
9
 
# File 'lib/gamebox/core/aabb_node.rb', line 7

def b
  @b
end

#bb ⇒ Object

Returns the value of attribute bb.



7
8
9
 
# File 'lib/gamebox/core/aabb_node.rb', line 7

def bb
  @bb
end

#cached_collisions ⇒ Object

Returns the value of attribute cached_collisions.



7
8
9
 
# File 'lib/gamebox/core/aabb_node.rb', line 7

def cached_collisions
  @cached_collisions
end

#object ⇒ Object

Returns the value of attribute object.



7
8
9
 
# File 'lib/gamebox/core/aabb_node.rb', line 7

def object
  @object
end

#parent ⇒ Object

Returns the value of attribute parent.



7
8
9
 
# File 'lib/gamebox/core/aabb_node.rb', line 7

def parent
  @parent
end

Instance Method Details

#disown_child(leaf) ⇒ Object 



88
89
90
91
92
93
94
95
96
97
98
99
100
 
# File 'lib/gamebox/core/aabb_node.rb', line 88

def disown_child(leaf)
  value = other(leaf)
  raise "Internal Error: Cannot replace child of a leaf." if @parent.leaf?
  raise "Internal Error: AABBNode is not a child of parent." unless self == @parent.a || self == @parent.b

  if @parent.a == self
    @parent.a = value
  else
    @parent.b = value
  end

  @parent.update_bb
end

#insert_subtree(leaf) ⇒ Object 



18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
 
# File 'lib/gamebox/core/aabb_node.rb', line 18

def insert_subtree(leaf)
  if leaf?
    new_node = AABBNode.new nil, nil, @bb.union_fast(leaf.bb)
    new_node.a = self
    new_node.b = leaf
    return new_node
  else
    cost_a = @b.bb.area + @a.bb.union_area(leaf.bb)
    cost_b = @a.bb.area + @b.bb.union_area(leaf.bb)

    if cost_a == cost_b
      cost_a = @a.proximity(leaf)
      cost_b = @b.proximity(leaf)
    end

    if cost_b < cost_a
      self.b = @b.insert_subtree leaf
    else
      self.a = @a.insert_subtree leaf
    end

    @bb.expand_to_include! leaf.bb
    return self
  end
end

#leaf? ⇒ Boolean

Returns:

  • (Boolean) 


70
71
72
 
# File 'lib/gamebox/core/aabb_node.rb', line 70

def leaf?
  @object
end

#other(child) ⇒ Object 



84
85
86
 
# File 'lib/gamebox/core/aabb_node.rb', line 84

def other(child)
  @a == child ? @b : @a
end

#proximity(other_node) ⇒ Object 



112
113
114
115
116
 
# File 'lib/gamebox/core/aabb_node.rb', line 112

def proximity(other_node)
  other_bb = other_node.bb
  (@bb.left + @bb.right - other_bb.left - other_bb.right).abs +
    (@bb.bottom + @bb.top - other_bb.bottom - other_bb.top).abs 
end

#query_subtree(search_bb, &blk) ⇒ Object 



59
60
61
62
63
64
65
66
67
68
 
# File 'lib/gamebox/core/aabb_node.rb', line 59

def query_subtree(search_bb, &blk)
  if @bb.collide_rect? search_bb
    if leaf?
      blk.call @object
    else
      @a.query_subtree search_bb, &blk
      @b.query_subtree search_bb, &blk
    end
  end
end

#remove_subtree(leaf) ⇒ Object 



44
45
46
47
48
49
50
51
52
53
54
55
56
57
 
# File 'lib/gamebox/core/aabb_node.rb', line 44

def remove_subtree(leaf)
  if leaf == self
    return nil
  else
    if leaf.parent == self
      other_child = other(leaf)
      other_child.parent = @parent
      return other_child
    else
      leaf.parent.disown_child leaf
      return self
    end
  end
end

#update_bb ⇒ Object 



102
103
104
105
106
107
108
109
110
 
# File 'lib/gamebox/core/aabb_node.rb', line 102

def update_bb
  node = self
  unless node.leaf?
    node.bb.refit_for! node.a.bb, node.b.bb
    while node = node.parent
      node.bb.refit_for! node.a.bb, node.b.bb
    end
  end
end