|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object lejos.robotics.pathfinding.DijkstraPathFinder
public class DijkstraPathFinder
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 the A* algorithm, a variant of the Dijkstra shortest path algorithm It uses the Node inner class for its internal representation of points.
Nested Class Summary | |
---|---|
protected class |
DijkstraPathFinder.Node
|
Field Summary | |
---|---|
protected boolean |
_blocked
set by segmentBlocked() used by findPath() |
protected ArrayList<DijkstraPathFinder.Node> |
_candidate
the set of nodes that are candidates for being in the shortest path, but whose distance from the start node is not yet known |
protected int |
_count
|
protected ArrayList<Line> |
_map
The map of the obstacles |
protected ArrayList<DijkstraPathFinder.Node> |
_reached
the set of nodes that are candidates for being in the shortest path, and whose distance from the start node is known |
Constructor Summary | |
---|---|
DijkstraPathFinder(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 (or collection of lines) in the constructor. |
protected DijkstraPathFinder.Node |
getBest(DijkstraPathFinder.Node currentDestination)
Helper method for findPath() returns the node in the Reached set, whose distance from the start node plus its straight line distance to the destination is the minimum. |
int |
getIterationCount()
|
protected ArrayList<Line> |
getMap()
|
int |
getNodeCount()
|
protected Path |
getRoute(DijkstraPathFinder.Node destination)
helper method for find path() calculates the route backtracking through predecessor chain |
protected boolean |
inCandidateSet(DijkstraPathFinder.Node aNode)
helper method for findPath; check if aNode is in the set of candidate nodes |
protected void |
initialize()
|
protected boolean |
inReachedSet(DijkstraPathFinder.Node aNode)
helper method for findPath; check if aNode is in the set of reached nodes |
void |
lengthenLines(float delta)
lengthens all the lines in the map by delta at each end |
protected boolean |
segmentBlocked(DijkstraPathFinder.Node from,
DijkstraPathFinder.Node theDest)
helper method for findPath(). |
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 |
Field Detail |
---|
protected int _count
protected boolean _blocked
protected ArrayList<DijkstraPathFinder.Node> _candidate
protected ArrayList<DijkstraPathFinder.Node> _reached
protected ArrayList<Line> _map
Constructor Detail |
---|
public DijkstraPathFinder(LineMap map)
Method Detail |
---|
public Path findRoute(Pose start, Waypoint finish) throws DestinationUnreachableException
findRoute
in interface PathFinder
start
- the initial robot posefinish
- the final robot location
DestinationUnreachableException
- if, for example, you nave not called setMap();public Path findRoute(Pose start, Waypoint finish, LineMap theMap) throws DestinationUnreachableException
start
- the initial robot posefinish
- the final robot locationtheMap
- the LineMap of obstacles
DestinationUnreachableException
- if, for example, you nave not called setMap();public void setMap(ArrayList<Line> theMap)
public void setMap(LineMap theMap)
public void lengthenLines(float delta)
delta
- added to each end of each lineprotected void initialize()
protected boolean segmentBlocked(DijkstraPathFinder.Node from, DijkstraPathFinder.Node theDest)
from
- the beginning of the line segmenttheDest
- the end of the line segment
protected DijkstraPathFinder.Node getBest(DijkstraPathFinder.Node currentDestination)
currentDestination
- : the current destination node, (in the Candidate set)
protected boolean inReachedSet(DijkstraPathFinder.Node aNode)
aNode
-
protected boolean inCandidateSet(DijkstraPathFinder.Node aNode)
aNode
-
protected Path getRoute(DijkstraPathFinder.Node destination)
destination
-
protected ArrayList<Line> getMap()
public int getIterationCount()
public int getNodeCount()
public void addListener(WaypointListener wpl)
addListener
in interface PathFinder
public void startPathFinding(Pose start, Waypoint end)
startPathFinding
in interface PathFinder
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |