Module org.bzdev.base
Package org.bzdev.util

Class AStarSearch<Node>

java.lang.Object
org.bzdev.util.AStarSearch<Node>
Type Parameters:
Node - the type of a node
public class AStarSearch<Node> extends Object
A* search. The A* search algorithm finds a path that minimizes a quantity f(n) = g(n) + h(n) where
  • g(n) is the cost or length of a path traversing a graph from a starting node to node n.
  • h(n) (a heuristic) is an estimate of the cost or length of the shortest path to a desired final node, and must be zero at the goal. If h(n) ≤ d(n,m) + h(m) for each edge (n, m), where d(n,m) is the distance or cost of an edge connection node n to node m, then the A* algorithm will find an optimal path without removing a node from a priority queue more than once.

For cases where g represent path lengths on a flat surface, a suitable choice of h(n,m) is ((xn-xm)2 + (xn-xm)2)1/2 where the XY coordinates of n are (xn,yn) and the XY coordinates of m are (xm,ym). If paths more or less follow a rectilinear grid, then a suitable choice is |xn-xm| + |yn-ym|.

For more details, see the Wikipedia article A* search algorithm, which the preceding text paraphrases.

This implementation requires that the user provide a data structure representing a node, a function to return a stream of the neighbors of a node, a function g(n,m) that computes the cost of an edge connecting node n to node m, and a function h(n,ng) that computes an estimate of the cost from node n to the goal (node ng). A stream of neighboring nodes should not include duplicates.

  • Constructor Details

    • AStarSearch

      public AStarSearch(Function<Node,Stream<Node>> getNeighbors, ToDoubleBiFunction<Node,Node> g, ToDoubleBiFunction<Node,Node> h)
      Constructor. The first argument is an implementation of a functional interface that must return a new supplier each time it is called. The supplier must provide the neighboring nodes, without duplicates, for the node passed to getNeighbors, followed by null to indicate that all the neighboring nodes have been provided. The function g is used to compute the "distance" between neighboring nodes, and the function h is a heuristic estimating the distance from some node to a goal node. When h is null, a default heuristic that produces the same results as Dijkstra's shortest path algorithm is used.

      Each node ni keeps track of two distances: gi and hi. For the initial node ns, gs = 0 and hs = h(ns, ng) where ng is the final node (or "goal"). A priority queue that initial contains just ns determines the order in which nodes are processed. At each step, a node ni with the minimum value of gi + hi is removed from the priority queue. For neighbors of ni that have not been previously removed from the priority queue, there are two cases:

      • For a neighbor nj that has never been on the priority queue, gj = gi + g(ni,nj) and hj = h(nj, ng)
      • For a neighbor nj that is on the priority queue, gj is set to gi + g(ni,nj) if this would decrease the value of gj.
      When the final node is reached, a list of nodes from the starting node to the final node is returned.

      Note: The function h(n,m) should be idempotent: it will be called when an event-queue entry is created and its value will then be cached.

      Parameters:
      getNeighbors - a function that returns a stream of neighboring nodes for node supplied as its argument
      g - a function that returns the distance from the node given by its first argument to the node given by its second argument.
      h - a heuristic function that returns an estimate of the distance from the node given by its first argument to the node given by its second argument; null for a default that always returns 0

  • Method Details

    • search

      public List<Node> search(Node start, Node goal)
      Search for a path between two nodes. This is equivalent to calling search(start,goal,false).
      Parameters:
      start - the initial node in a path
      goal - the final node in a path
      Returns:
      a list of the nodes from the initial node to the final node, inclusive

    • search

      public List<Node> search(Node start, Node goal, boolean pollOnce)
      Search for a path between two nodes, specifying if a node can not be added to the priority queue after being polled or have its values updated by a neighbor.

      If the heuristic h(n) satisfies the condition h(n) ≤ g(n,m) + h(m), then pollOnce should be set to false as each node will be polled at most once. Setting pollOnce to true otherwise may reduce the amount of searching performed, but possibly at the cost of finding a worse path. A timing test suggested a slight increase in running time if pollOnce is set to true when the condition h(n) ≤ g(n,m) + h(m) holds.

      Parameters:
      start - the initial node in a path
      goal - the final node in a path
      pollOnce - true if a node provided by the priority queue via a call to poll() will not be added to the priority queue again or have its values updated by a neighbor
      Returns:
      a list of the nodes from the initial node to the final node, inclusive