Class: QuadTree

Inherits:
Object
  • Object
show all
Defined in:
lib/misc/quad_tree.rb

Constant Summary collapse

NODE_CAPACITY = 
12

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(boundary) ⇒ QuadTree

Returns a new instance of QuadTree.



5
6
7
8
 
# File 'lib/misc/quad_tree.rb', line 5

def initialize(boundary)
  @boundary = boundary
  @objects = []
end

Instance Attribute Details

#ne ⇒ Object

Returns the value of attribute ne.



3
4
5
 
# File 'lib/misc/quad_tree.rb', line 3

def ne
  @ne
end

#nw ⇒ Object

Returns the value of attribute nw.



3
4
5
 
# File 'lib/misc/quad_tree.rb', line 3

def nw
  @nw
end

#objects ⇒ Object

Returns the value of attribute objects.



3
4
5
 
# File 'lib/misc/quad_tree.rb', line 3

def objects
  @objects
end

#se ⇒ Object

Returns the value of attribute se.



3
4
5
 
# File 'lib/misc/quad_tree.rb', line 3

def se
  @se
end

#sw ⇒ Object

Returns the value of attribute sw.



3
4
5
 
# File 'lib/misc/quad_tree.rb', line 3

def sw
  @sw
end

Instance Method Details

#insert(game_object) ⇒ Object 



10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
# 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) ⇒ Object 



44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
 
# 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) ⇒ Object 



30
31
32
33
34
35
36
37
38
39
40
41
42
 
# 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