Class: Shortest::Path::AStar

Inherits:
Object
  • Object
show all
Defined in:
lib/shortest/path/astar.rb

Instance Method Summary collapse

Constructor Details

#initialize(dist, cost, graph, start, goal) ⇒ AStar

Returns a new instance of AStar.



21
22
23
24
25
 
# File 'lib/shortest/path/astar.rb', line 21

def initialize(dist, cost, graph, start, goal)
  @graph = graph
  @dist  = dist ; @cost = cost
  @start = start ; @goal=goal
end

Instance Method Details

#search ⇒ Object 



27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
 
# File 'lib/shortest/path/astar.rb', line 27

def search
  been_there = {}
  pqueue = Shortest::Path::PriorityQueue.new
  pqueue << [1, [@start, [], 0]]
  while !pqueue.empty?
    spot, path_so_far, cost_so_far = pqueue.next
    next if been_there[spot]
    newpath = path_so_far + [spot]
    return newpath if (spot == @goal)
    been_there[spot] = 1
    @graph.neighbors(spot).each do |newspot|
      next if been_there[newspot]
      tcost = @cost.call(spot, newspot)
      next unless tcost
      newcost = cost_so_far + tcost
      pqueue << [newcost + @dist.call(@goal, newspot), [newspot, newpath, newcost]]
    end
  end
  return []
end