Package lejos.robotics.pathfinding

Class DijkstraPathFinder

  • All Implemented Interfaces:
    PathFinder
    public class DijkstraPathFinder
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 the A* algorithm, a variant of the Dijkstra shortest path algorithm It uses the Node inner class for its internal representation of points.
    Author:
    Roger Glassey

    • Field Detail

      • _count

        protected int _count

      • _blocked

        protected boolean _blocked
        set by segmentBlocked() used by findPath()

      • _candidate

        protected java.util.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

      • _reached

        protected java.util.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

      • _map

        protected java.util.ArrayList<Line> _map
        The map of the obstacles

    • Constructor Detail

      • DijkstraPathFinder

        public DijkstraPathFinder​(LineMap map)

    • Method Detail

      • findRoute

        public Path findRoute​(Pose start,
                      Waypoint finish,
                      LineMap theMap)
               throws DestinationUnreachableException
        Finds the shortest path from start to finish using the map (or 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();

      • setMap

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

      • setMap

        public void setMap​(LineMap theMap)

      • 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

      • initialize

        protected void initialize()

      • segmentBlocked

        protected boolean segmentBlocked​(DijkstraPathFinder.Node from,
                                 DijkstraPathFinder.Node theDest)
        helper method for findPath(). Determines if the straight line segment crosses a line on the map. Side effect: creates nodes at the end of the blocking line and adds them to the _candidate set
        Parameters:
        from - the beginning of the line segment
        theDest - the end of the line segment
        Returns:
        true if the segment is blocked

      • getBest

        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.
        Parameters:
        currentDestination - : the current destination node, (in the Candidate set)
        Returns:
        the node the node which could be the last node in the shortest path

      • inReachedSet

        protected boolean inReachedSet​(DijkstraPathFinder.Node aNode)
        helper method for findPath; check if aNode is in the set of reached nodes
        Parameters:
        aNode -
        Returns:
        true if aNode has been reached already

      • inCandidateSet

        protected boolean inCandidateSet​(DijkstraPathFinder.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

      • getRoute

        protected Path getRoute​(DijkstraPathFinder.Node destination)
        helper method for find path()
        calculates the route backtracking through predecessor chain
        Parameters:
        destination -
        Returns:
        the route of the shortest path

      • getMap

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

      • getIterationCount

        public int getIterationCount()

      • getNodeCount

        public int getNodeCount()