class ActiveBacon::A::Star

Public Class Methods

new(adjacency_func, cost_func) click to toggle source
# File lib/active_bacon/a/star.rb, line 13
      def initialize(adjacency_func, cost_func)
        @adjacency = adjacency_func
        @cost = cost_func
#        no use for distance function yet
#        @distance = distance_func
      end

Public Instance Methods

find_path(start, goal) click to toggle source
# File lib/active_bacon/a/star.rb, line 20
def find_path(start, goal)

  result = Hashie::Mash.new(:success? => false)

  visited = {}
 
  pqueue = PriorityQueue.new
  pqueue << [1,  [start,[], 0]]

  until result.success? || pqueue.empty?
    # e.g. start, [], 0
    spot, path_so_far, cost_so_far = pqueue.next

    # if already been there, then skip
    next if visited[spot]

    # [] + start
    new_path = path_so_far + [spot]

    # if goal == spot, return the result
    if goal == spot 
      result.path = new_path 
      result[:success?] = true
      result[:cost] = cost_so_far
    else
      # continue
      visited[spot] = cost_so_far

      @adjacency.call(spot).each do |new_spot|
        # if already been there, skip it
        next if visited[new_spot]
        this_cost = @cost.call(spot, new_spot)

        if this_cost 
          new_cost = cost_so_far + this_cost
          # add to queue
          pqueue << [ new_cost, [new_spot, new_path, new_cost]]
        end
      end
    end
  end # while

  result[:visited] = visited

  return result # success? is false
end