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