Package lejos.robotics.pathfinding

Class AstarSearchAlgorithm

java.lang.Object

lejos.robotics.pathfinding.AstarSearchAlgorithm

All Implemented Interfaces:

SearchAlgorithm

public class AstarSearchAlgorithm
extends java.lang.Object
implements SearchAlgorithm

This is an implementation of the A* search algorithm. Typically this object would be instantiated and then used in a NodePathFinder constructor, along with a set of connected nodes.

See Also:

NodePathFinder

Field Summary

Fields

Modifier and Type	Field and Description
(package private) int	main_loop
(package private) int	neighbor_loop
private static java.lang.String	STRING_NAME

Constructor Summary

Constructors

Constructor and Description
AstarSearchAlgorithm()

Method Summary

Modifier and Type	Method and Description
Path	findPath(Node start, Node goal) Method accepts a start node and a goal node, and returns a path consisting of a collection of waypoints which includes the startNode coordinates as the first waypoint, and the goal node coordinates as the final waypoint.
private static Node	getLowestCost(java.util.Collection<Node> nodeSet) Finds the node within a set of neighbors with the least cost (potentially shortest distance to goal).
private static void	reconstructPath(Node current_node, Node start, java.util.Collection<Waypoint> path) Given the current node and the start node, this method retraces the completed path.
java.lang.String	toString()

Methods inherited from class java.lang.Object

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

Field Detail

STRING_NAME

private static final java.lang.String STRING_NAME

See Also:

Constant Field Values

main_loop

int main_loop

neighbor_loop

int neighbor_loop

Constructor Detail

AstarSearchAlgorithm

public AstarSearchAlgorithm()

Method Detail

findPath

public Path findPath(Node start,
                     Node goal)

Description copied from interface: SearchAlgorithm

Method accepts a start node and a goal node, and returns a path consisting of a collection of waypoints which includes the startNode coordinates as the first waypoint, and the goal node coordinates as the final waypoint. Note: The startNode must be connected with other nodes (neighbors) that eventually connect to the goalNode.

Specified by:

findPath in interface SearchAlgorithm

Returns:

A collection of waypoints. Returns null if it fails to find a path.

getLowestCost

private static Node getLowestCost(java.util.Collection<Node> nodeSet)

Finds the node within a set of neighbors with the least cost (potentially shortest distance to goal).

Returns:

The node with the least cost.

reconstructPath

private static final void reconstructPath(Node current_node,
                                          Node start,
                                          java.util.Collection<Waypoint> path)

Given the current node and the start node, this method retraces the completed path. It relies on Node.getPredecessor() to backtrack using recursion.

Parameters:

current_node -

start -

path - The path output by this algorithm.

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object