Class: Polaris

Inherits:
Object
  • Object
show all
Defined in:
lib/polaris.rb,
lib/polaris/version.rb

Overview

Polaris is a star that guides, aka “The North Star”. It implements the A* algorithm.

Defined Under Namespace

Modules: VERSION

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(map) ⇒ Polaris

Returns a new instance of Polaris.



10
11
12
13
 
# File 'lib/polaris.rb', line 10

def initialize(map)
  @map = map
  @nodes_considered = 0
end

Instance Attribute Details

#nodes_considered ⇒ Object (readonly)

Returns the value of attribute nodes_considered.



8
9
10
 
# File 'lib/polaris.rb', line 8

def nodes_considered
  @nodes_considered
end

Instance Method Details

#guide(from, to, unit_type = nil, max_depth = 400) ⇒ Object

Returns the path without the from location. Returns nil if max_depth is hit or if no path exists.



17
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
 
# File 'lib/polaris.rb', line 17

def guide(from, to, unit_type=nil, max_depth=400)
  return nil if @map.blocked?(from, unit_type) || @map.blocked?(to, unit_type)
  from_element = PathElement.new(from)
  from_element.dist_from = @map.distance(from,to)
  open = PriorityQueue.new { |x, y| (x <=> y) == -1 }
  open.push from_element, from_element.rating
  closed = SplayTreeMap.new
  step = 0
  
  until open.empty? || step > max_depth
    step += 1
    
    current_element = open.pop
    @nodes_considered += 1
    
    loc = current_element.location
    if @map.cost(loc,to) == 0
      path = []
      until current_element.parent.nil?
        path.unshift current_element
        current_element = current_element.parent
      end

      return path
    else
      closed.push loc, current_element
      @map.neighbors(loc).each do |next_door|
        next if closed.has_key? next_door

        el = PathElement.new(next_door,current_element)

        if @map.blocked? next_door, unit_type
          closed.push el.location, el
        else
          current_rating = current_element.cost_to + @map.cost(loc, next_door)

          # add to open
          el.cost_to = current_rating
          el.dist_from = @map.distance(next_door,to)
          
          open.push el, el.rating
        end
      end
    end
  end
  nil
end