Package lejos.robotics.pathfinding

Class ShortestPathFinder

java.lang.Object

lejos.robotics.pathfinding.ShortestPathFinder

All Implemented Interfaces:

PathFinder

public class ShortestPathFinder
extends java.lang.Object
implements PathFinder

This class calculates the shortest path from a starting point to a finish point. while avoiding obstacles that are represented as a set of straight lines. The path passes through the end points of some of these lines, which is where the changes of direction occur. Since the robot is not point, the lines representing the obstacles should be lengthened so the actual robot will miss the actual obstacles. Use the lengthenLines() method to do this. Uses modification of the A* algorithm,which is a a variant of the Dijkstra shortest path algorithm. This variant adds nodes needed. It uses the Node inner class for its internal representation of points.

Author:

Roger Glassey

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
class	ShortestPathFinder.Node

Constructor Summary

Constructors

Constructor	Description
ShortestPathFinder(LineMap map)

Method Summary

Modifier and Type	Method	Description
void	addListener(WaypointListener wpl)
Path	findRoute(Pose start, Waypoint finish)	Finds the shortest path from start to finish using the map (or collection of lines) in the constructor.
Path	findRoute(Pose start, Waypoint finish, LineMap theMap)	Finds the shortest path from start to finish using the map ( collection of lines) in the constructor.
int	getIterationCount()
java.util.ArrayList<Line>	getMap()
int	getNodeCount()
boolean	inCandidateSet(ShortestPathFinder.Node aNode)	helper method for findPath; check if aNode is in the set of candidate nodes
void	lengthenLines(float delta)	lengthens all the lines in the map by delta at each end
void	setDebug(boolean yes)
void	setMap(java.util.ArrayList<Line> theMap)
void	setMap(LineMap theMap)
void	startPathFinding(Pose start, Waypoint end)

Methods inherited from class java.lang.Object

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

Constructor Detail

ShortestPathFinder

public ShortestPathFinder(LineMap map)

Method Detail

findRoute

public Path findRoute(Pose start,
                      Waypoint finish)
               throws DestinationUnreachableException

Finds the shortest path from start to finish using the map (or collection of lines) in the constructor.

Specified by:

findRoute in interface PathFinder

Parameters:

start - the initial robot pose

finish - the final robot location

Returns:

the shortest route

Throws:

DestinationUnreachableException - if, for example, you nave not called setMap();

findRoute

public Path findRoute(Pose start,
                      Waypoint finish,
                      LineMap theMap)
               throws DestinationUnreachableException

Finds the shortest path from start to finish using the map ( collection of lines) in the constructor.

Parameters:

start - the initial robot pose

finish - the final robot location

theMap - the LineMap of obstacles

Returns:

the shortest route

Throws:

DestinationUnreachableException - if, for example, you nave not called setMap();

inCandidateSet

public boolean inCandidateSet(ShortestPathFinder.Node aNode)

helper method for findPath; check if aNode is in the set of candidate nodes

Parameters:

aNode -

Returns:

true if aNode has been reached already

setMap

public void setMap(java.util.ArrayList<Line> theMap)

setMap

public void setMap(LineMap theMap)

setDebug

public void setDebug(boolean yes)

lengthenLines

public void lengthenLines(float delta)

lengthens all the lines in the map by delta at each end

Parameters:

delta - added to each end of each line

getMap

public java.util.ArrayList<Line> getMap()

getIterationCount

public int getIterationCount()

getNodeCount

public int getNodeCount()

addListener

public void addListener(WaypointListener wpl)

Specified by:

addListener in interface PathFinder

startPathFinding

public void startPathFinding(Pose start,
                             Waypoint end)

Specified by:

startPathFinding in interface PathFinder