com.kuka.graph.alg
Class RRAStar<N>

java.lang.Object
  com.kuka.graph.alg.RRAStar<N>

Type Parameters:

N - the node type

public final class RRAStar<N>
extends Object

Implements the RRA* (Reverse Resumable A*) algorithm as described in Cooperative Pathfinding by David Silver. The RRA* algorithm is a modified A* search in a reverse direction.

The search starts at the specified goal node g, and heads towards the start node s. Instead of terminating at s, the search continues until a specified node n is expanded (see getCost(Object) and getSuccessor(Object), where the argument is the node n).

Constructor Summary

RRAStar(Graph<N,?> graph, CostFunction<N,?> cost, N start, N goal)
Creates a new RRA* algorithm instance.

Method Summary

double	getCost(N node) Returns the cost of the optimal path from the given node to the goal node specified in the constructor.
N	getSuccessor(N node) Returns the successor of the given node in the optimal path to the goal node specified in the constructor.
RRAStar<N>	setEdgeFilter(GraphElementFilter<Edge<N>> edgeFilter) Sets the filter specifying whether an edge may be traversed or must not be included in the path.
RRAStar<N>	setNodeFilter(GraphElementFilter<N> nodeFilter) Sets the filter specifying whether a node may be traversed or must not be included in the path.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

RRAStar

public RRAStar(Graph<N,?> graph,
               CostFunction<N,?> cost,
               N start,
               N goal)

Creates a new RRA* algorithm instance. The search starts at the specified goal node and is directed to the specified start node.

Parameters:

graph - the graph to traverse

cost - the cost to use for traversal

start - the start node

goal - the goal node

Method Detail

setNodeFilter

public RRAStar<N> setNodeFilter(GraphElementFilter<N> nodeFilter)

Sets the filter specifying whether a node may be traversed or must not be included in the path.

Parameters:

nodeFilter - the filter specifying whether a node may be traversed or must not be included in the path

Returns:

this algorithm

setEdgeFilter

public RRAStar<N> setEdgeFilter(GraphElementFilter<Edge<N>> edgeFilter)

Sets the filter specifying whether an edge may be traversed or must not be included in the path.

Parameters:

edgeFilter - the filter specifying whether an edge may be traversed or must not be included in the path

Returns:

this algorithm

getCost

public double getCost(N node)

Returns the cost of the optimal path from the given node to the goal node specified in the constructor.

Parameters:

node - the node for which to return the cost

Returns:

the cost of the optimal path from the given node to the goal

getSuccessor

public N getSuccessor(N node)

Returns the successor of the given node in the optimal path to the goal node specified in the constructor. If no path exists from the specified node to the goal node null is returned. If the node is the goal node the same node is returned.

Parameters:

node - the node for which to return the successor

Returns:

the successor of the given node in the optimal path to the goal node (can be null)