Class: Moon::Quadtree

Inherits:
Object show all
Defined in:
lib/moon/packages/physics/quadtree.rb

Overview

Based on github.com/timohausmann/quadtree-js ported to moon, mruby

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(bounds, max_objects = 10, max_levels = 4, level = 0) ⇒ Quadtree


21
22
23
24
25
26
27
28
# File 'lib/moon/packages/physics/quadtree.rb', line 21

def initialize(bounds, max_objects = 10, max_levels = 4, level = 0)
  @bounds = bounds
  @max_objects = max_objects
  @max_levels = max_levels
  @level = level
  @objects = []
  @nodes = []
end

Instance Attribute Details

#boundsMoon::Rect (readonly)


6
7
8
# File 'lib/moon/packages/physics/quadtree.rb', line 6

def bounds
  @bounds
end

#levelInteger (readonly)


12
13
14
# File 'lib/moon/packages/physics/quadtree.rb', line 12

def level
  @level
end

#max_levelsInteger (readonly)


10
11
12
# File 'lib/moon/packages/physics/quadtree.rb', line 10

def max_levels
  @max_levels
end

#max_objectsInteger (readonly)


8
9
10
# File 'lib/moon/packages/physics/quadtree.rb', line 8

def max_objects
  @max_objects
end

#nodesArray<Moon::Quadtree> (readonly)


16
17
18
# File 'lib/moon/packages/physics/quadtree.rb', line 16

def nodes
  @nodes
end

#objectsArray<Moon::Rectangular> (readonly)


14
15
16
# File 'lib/moon/packages/physics/quadtree.rb', line 14

def objects
  @objects
end

Instance Method Details

#clearObject

Clear the Quadtree


113
114
115
116
117
118
119
120
121
# File 'lib/moon/packages/physics/quadtree.rb', line 113

def clear
  objects.clear
  nodes.each do |node|
    node.clear if node
  end
  nodes.clear

  self
end

#get_index(rect) ⇒ Moon::Rect


44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
# File 'lib/moon/packages/physics/quadtree.rb', line 44

def get_index(rect)
  vert_mp = bounds.x + bounds.w / 2
  horz_mp = bounds.y + bounds.h / 2

  top_quadrant = rect.y < horz_mp && rect.y + rect.h < horz_mp
  bot_quadrant = rect.y > horz_mp

  if rect.x < vert_mp && rect.x + rect.w < vert_mp
    if top_quadrant
      return 1
    elsif bot_quadrant
      return 2
    end
  elsif rect.x > vert_mp
    if top_quadrant
      return 0
    elsif bot_quadrant
      return 3
    end
  end

  -1
end

#insert(rect) ⇒ Moon::Rect


69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
# File 'lib/moon/packages/physics/quadtree.rb', line 69

def insert(rect)
  unless nodes.empty?
    index = get_index(rect)

    return nodes[index].insert(rect) if index != -1
  end

  objects.push rect

  if objects.size > max_objects && level < max_levels
    split if nodes.empty?

    i = 0
    while i < objects.length
      index = get_index(objects[i])

      if index != -1
        nodes[index].insert(objects.delete_at(i))
      else
        i = i.succ
      end
    end
  end
end

#retrieve(rect) ⇒ Moon::Rect


95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
# File 'lib/moon/packages/physics/quadtree.rb', line 95

def retrieve(rect)
  index = get_index(rect)
  result = [].concat(objects)

  unless nodes.empty?
    if index != -1
      result.concat(nodes[index].retrieve(rect))
    else
      nodes.each do |node|
        result.concat(node.retrieve(rect))
      end
    end
  end

  result
end

#splitself


31
32
33
34
35
36
37
38
39
40
41
# File 'lib/moon/packages/physics/quadtree.rb', line 31

def split
  next_level = level + 1
  r1, r2, r3, r4 = bounds.split

  nodes[0] = self.class.new(r1, max_objects, max_levels, next_level)
  nodes[1] = self.class.new(r2, max_objects, max_levels, next_level)
  nodes[2] = self.class.new(r3, max_objects, max_levels, next_level)
  nodes[3] = self.class.new(r4, max_objects, max_levels, next_level)

  self
end