Class: Mormon::OSM::Algorithm::Astar

Inherits:
Base
  • Object
show all
Defined in:
lib/mormon/osm_router.rb

Overview

A* Algorithm

Instance Method Summary collapse

Methods inherited from Base

#initialize

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