class AStar

A generic implementation of the A* search algoritm.

A* is a search algoritm and this is a ruby implementation of it. The implementation is such that you wrap the objects you want to find paths between, add them to a Hash where the keys are nodes and values neighbours of the corresponding nodes. You then provide this graph (hash) when you instantiate the AStar search class.

To find the shortest path, or most profitable between two nodes, you supply the start and goal nodes to the #search method and if a path can be found a list of the nodes making up the journey will be provided back. If no path can be found, nil is returned.

For implementation examples, refer to the rspec and test runner in the spec directory.

Credits: The gem is mostly a rubification of Justin Poliey’s Python implementation. Check out his excellent post on the subject at:

http://scriptogr.am/jdp/post/pathfinding-with-python-graphs-and-a-star

Public Class Methods

new(graph, maximize_cost=false) click to toggle source

Populate the search space and indicate whether searching should maximize estimated cost for moving between nodes, or whether it should be minimized.

Arguments: graph is a the search space on which the path finding should operate. It’s a plain hash with AStar nodes as keys and also for neighbor as the values. The value of each hash entry should be a list of neighbors. E.g. {node => [neighbour node, neighbour node]}

maximize_cost indicates that higher heuristic values and costs are better, such as higher profits. Normally it’s less that’s desired, for example for distance routing in euclidean space. This an optional argument and the default is to minimize cost (false).

# File lib/gastar.rb, line 42
def initialize(graph, maximize_cost=false)
  @graph = graph
  @maximize_cost = maximize_cost
end

Public Instance Methods

heuristic(node, start, goal) click to toggle source

Abstract method that an implementor must provide in a derived class. This function should return the estimated cost (a number) for getting to the goal node. In eucledian space (2D/3D), most likely the trigonometric distance (Pythagorean theorem). For other uses some other function may be appropriate.

Arguments: node is the current node for which cost to the goal should be estimated. start is the starting node. May or may not be useful to you, but is

provided all the same.

goal is the final destination node towards which the distance / cost should be estimated.

# File lib/gastar.rb, line 59
def heuristic(node, start, goal)
  raise NotImplementedError
end

search(start, goal) click to toggle source

Performs the actual path-finding. Takes two AStarNodes. start, is the origin for the search and goal where we want to get to. Returns the nodes (steps) including the start and goal nodes, that should be traversed if we were to follow the path.

# File lib/gastar.rb, line 67
def search(start, goal)
  openset = Set.new
  closedset = Set.new
  current = start

  if @maximize_cost  # serves to invert the comparison
    openset_min_max = openset.method(:max_by)
    flip = -1
  else
    openset_min_max = openset.method(:min_by)
    flip = 1
  end

  openset.add(current)
  while not openset.empty?
    current = openset_min_max.call{|o| o.g + o.h }
    if current == goal
      path = []
      while current.parent
        path << current
        current = current.parent
      end
      path << current
      return path.reverse
    end
    openset.delete(current)
    closedset.add(current)
    @graph[current].each do |node|
      next if closedset.include? node

      if openset.include? node
        new_g = current.g + current.move_cost(node)
        if (node.g - new_g) * flip > 0
          node.g = new_g
          node.parent = current
        end
      else
        node.g = current.g + current.move_cost(node)
        node.h = heuristic(node, start, goal)
        node.parent = current
        openset.add(node)
      end
    end
  end
  return nil
end