Class: Mormon::OSM::Algorithm::Astar
- Defined in:
- lib/mormon/osm_router.rb
Overview
A* Algorithm
Instance Method Summary collapse
- #enqueue(node_start, node_end, node_finish, current_queue, weight = 1) ⇒ Object
- #route(node_start, node_end, transport) ⇒ Object
Methods inherited from Base
Constructor Details
This class inherits a constructor from Mormon::OSM::Algorithm::Base
Instance Method Details
#enqueue(node_start, node_end, node_finish, current_queue, weight = 1) ⇒ Object
69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 |
# File 'lib/mormon/osm_router.rb', line 69 def enqueue(node_start, node_end, node_finish, current_queue, weight = 1) # Add another potential route to the queue # if already in queue return if @queue.any? { |other| other[:node_end] == node_end } distance = distance(node_start, node_end) return if weight.zero? distance = distance / weight # Create a hash for all the route's attributes current_distance = current_queue[:distance] nodes = current_queue[:nodes].dup nodes << node_end queue_item = { distance: current_distance + distance, max_distance: current_distance + distance(node_end, node_finish), nodes: nodes, node_end: node_end } # Try to insert, keeping the queue ordered by decreasing worst-case distance ix = @queue.find_index { |other| other[:max_distance] > queue_item[:max_distance] } || -1 @queue.insert(ix, queue_item) end |
#route(node_start, node_end, transport) ⇒ Object
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 64 65 66 67 |
# File 'lib/mormon/osm_router.rb', line 37 def route(node_start, node_end, transport) return "no_such_transport" unless @router.loader.routing[transport] return "no_such_node" unless @router.loader.routing[transport][node_start.to_s] # Start by queueing all outbound links from the start node @router.loader.routing[transport][node_start.to_s].each do |neighbor, weight| enqueue(node_start, neighbor.to_i, node_end, { node_end: nil, distance: 0, nodes: [node_start] }, weight) end closed = [node_start] # Limit for how long it will search (0..10000).each do next_item = @queue.shift return "no_route" unless next_item x = next_item[:node_end] next if closed.include?(x) # Found the end node - success return ['success', next_item[:nodes]] if x == node_end closed << x @router.loader.routing[transport][x.to_s].each do |node, weight| enqueue(x, node.to_i, node_end, next_item, weight) unless closed.include?(node.to_i) end if @router.loader.routing[transport][x.to_s] end 'gave_up' end |