lejos.robotics.pathfinding
Class ShortestPathFinder

java.lang.Object
  extended by lejos.robotics.pathfinding.ShortestPathFinder
All Implemented Interfaces:
PathFinder

public class ShortestPathFinder
extends 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
 class ShortestPathFinder.Node
           
 
Constructor Summary
ShortestPathFinder(LineMap map)
           
 
Method Summary
 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()
           
 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(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(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 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