Class AStar<GP extends GraphPath<GP,​ST,​PT>,​ST extends GraphSegment<ST,​PT>,​PT extends GraphPoint<PT,​ST>>

  • Type Parameters:
    GP - is the type of the graph graph itself.
    PT - is the type of node in the graph
    ST - is the type of edge in the graph
    Direct Known Subclasses:
    RoadAStar

    public class AStar<GP extends GraphPath<GP,​ST,​PT>,​ST extends GraphSegment<ST,​PT>,​PT extends GraphPoint<PT,​ST>>
    extends Object
    This class provides an implementation of the famous A* algorithm.
    Since:
    13.0
    Version:
    17.0 2020-01-04 14:41:42
    Author:
    Stéphane GALLAND
    Maven Group Id:
    org.arakhne.afc.core
    Maven Artifact Id:
    mathgraph
    • Constructor Detail

      • AStar

        public AStar​(AStarHeuristic<? super PT> heuristic,
                     AStarPathFactory<GP,​ST,​PT> pathFactory1)
        Constructor.
        Parameters:
        heuristic - is the heuristic to use by the A* algorithm.
        pathFactory1 - is the factory to create new paths.
      • AStar

        public AStar​(AStarHeuristic<? super PT> heuristic,
                     Class<? extends GP> pathType)
        Constructor.
        Parameters:
        heuristic - is the heuristic to use by the A* algorithm.
        pathType - is the type of the path to create.
    • Method Detail

      • addAStarListener

        public void addAStarListener​(AStarListener<ST,​PT> listener)
        Add listener on A* algorithm events.
        Parameters:
        listener - the listener.
      • removeAStarListener

        public void removeAStarListener​(AStarListener<ST,​PT> listener)
        Remove listener on A* algorithm events.
        Parameters:
        listener - the listener.
      • setClosedNodeReopeningEnabled

        public void setClosedNodeReopeningEnabled​(boolean enableClosedNodeReopening1)
        Change the flag that permits to reopen the closed A* nodes.
        Parameters:
        enableClosedNodeReopening1 - is true to enable the closed A* nodes; false to never reopen the closed A* nodes.
      • isClosedNodeReopeningEnabled

        @Pure
        public boolean isClosedNodeReopeningEnabled()
        Replies the flag that permits to reopen the closed A* nodes.
        Returns:
        true if the closed A* nodes could be reopened; false if the closed A* nodes will be never reopened.
      • getPathFactory

        @Pure
        public AStarPathFactory<GP,​ST,​PT> getPathFactory()
        Replies the path factory used by the A* algorithm.
        Returns:
        the factory
      • setEvaluationHeuristic

        public AStarHeuristic<? super PT> setEvaluationHeuristic​(AStarHeuristic<? super PT> heuristic)
        Set the evaluation heuristic used by the A* algorithm.
        Parameters:
        heuristic - is the evaluation heuristic.
        Returns:
        the old heurisstic.
      • getEvaluationHeuristic

        @Pure
        public AStarHeuristic<? super PT> getEvaluationHeuristic()
        Replies the evaluation heuristic used by the A* algorithm.
        Returns:
        the heurisstic.
      • setSegmentReplacer

        public AStarSegmentReplacer<ST> setSegmentReplacer​(AStarSegmentReplacer<ST> replacer)
        Set the object to use to replace the segments in the shortest path.
        Parameters:
        replacer - is the new replacer.
        Returns:
        the old replacer
      • getSegmentReplacer

        @Pure
        public AStarSegmentReplacer<ST> getSegmentReplacer()
        Replies the object used to replace the segments in the shortest path.
        Returns:
        the segment replacer, or null if none.
      • setSegmentOrientationTool

        public AStarSegmentOrientation<ST,​PT> setSegmentOrientationTool​(AStarSegmentOrientation<ST,​PT> tool)
        Set the tool that permits to retreive the orinetation of the segments.
        Parameters:
        tool - the tool for retreiving the orientation of the segments.
        Returns:
        the old tool.
      • getSegmentOrientationTool

        @Pure
        public AStarSegmentOrientation<ST,​PT> getSegmentOrientationTool()
        Replies the tool that permits to retreive the orinetation of the segments..
        Returns:
        the tool.
      • setCostComputer

        public AStarCostComputer<? super ST,​? super PT> setCostComputer​(AStarCostComputer<? super ST,​? super PT> costComputer)
        Set the tool that permits to compute the costs of the nodes and the edges.
        Parameters:
        costComputer - is the object that permits to compute the costs.
        Returns:
        the old cost computer.
      • getCostComputer

        @Pure
        public AStarCostComputer<? super ST,​? super PT> getCostComputer()
        Replies the tool that permits to compute the costs of the nodes and edges.
        Returns:
        the cost computer
      • estimate

        @Pure
        protected double estimate​(PT p1,
                                  PT p2)
        Evaluate the distance between two points in the graph.

        By default, this function uses the heuristic passed as parameter of the constructor.

        Parameters:
        p1 - the first point.
        p2 - the second point.
        Returns:
        the evaluated distance between p1 and p2.
      • computeCostFor

        @Pure
        protected double computeCostFor​(PT pt)
        Compute and replies the cost to traverse the given graph point.
        Parameters:
        pt - the point.
        Returns:
        the cost to traverse the point.
      • computeCostFor

        @Pure
        protected double computeCostFor​(ST segment)
        Compute and replies the cost to traverse the given graph segment.
        Parameters:
        segment - the segment.
        Returns:
        the cost to traverse the segment.
      • translateCandidate

        @Pure
        protected AStarNode<ST,​PT> translateCandidate​(PT endPoint,
                                                            AStarNode<ST,​PT> node)
        Translate the A* node. This function is invoked prior to any treatment with the given A* node. It is assumed that this function replies a good translation of the given node for the A* algorithm; or it replies null if the given node is the target node of the A* algorithm, ie. it corresponds to the given endPoint.

        By default, this function replies the node itself.

        Parameters:
        endPoint - is the end point given to solve function.
        node - is the current A* node to translate.
        Returns:
        the translation of the node, or null if the node corresponds to the endPoint.
      • newPath

        @Pure
        protected GP newPath​(PT startPoint,
                             ST segment)
        Create an empty path.

        By default this function invokes the path factory passed as parameter of the constructor.

        Parameters:
        startPoint - is the first point in the path.
        segment - is the first connection to follow.
        Returns:
        the path instance.
      • addToPath

        protected boolean addToPath​(GP path,
                                    ST segment)
        Add the given segment into the given path.

        By default this function invokes the path factory passed as parameter of the constructor.

        Parameters:
        path - is the path to build.
        segment - is the segment to add.
        Returns:
        true if the segment was added; otherwise false.
      • solve

        @Pure
        public GP solve​(PT startPoint,
                        PT endPoint)
        Run the A* algorithm assuming that the graph is oriented is an orientation tool was passed to the constructor.

        The orientation of the graph may also be overridden by the implementations of the A* nodes.

        Parameters:
        startPoint - is the starting point.
        endPoint - is the point to reach.
        Returns:
        the found path, or null if none found.
      • solve

        protected GP solve​(AStarNode<ST,​PT> startPoint,
                           PT endPoint)
        Run the A* algorithm assuming that the graph is oriented is an orientation tool was passed to the constructor.

        The orientation of the graph may also be overridden by the implementations of the A* nodes.

        Parameters:
        startPoint - is the starting point.
        endPoint - is the point to reach.
        Returns:
        the found path, or null if none found.
      • newAStarNode

        @Pure
        protected AStarNode<ST,​PT> newAStarNode​(PT node,
                                                      double cost,
                                                      double estimatedCost,
                                                      ST arrival)
        Create a instance of A* node.
        Parameters:
        node - is the node of the graph to put in the A* node.
        cost - is the cost to reach the node.
        estimatedCost - is the estimated cost to reach the target.
        arrival - is the segment, which permits to arrive at the node.
        Returns:
        the A* node.
      • findPath

        @Pure
        List<AStarNode<ST,​PT>> findPath​(AStarNode<ST,​PT> startPoint,
                                              PT endPoint)
        Run the A* algorithm and tries to find a path from the startPoint to the endPoint.
        Parameters:
        startPoint - is the starting point.
        endPoint - is the point to reach.
        Returns:
        the close list of the A* algorithm.
      • createPath

        @Pure
        GP createPath​(AStarNode<ST,​PT> startPoint,
                      PT endPoint,
                      List<AStarNode<ST,​PT>> closeList)
        Create the path from the given close list.
        Parameters:
        startPoint - is the starting point.
        endPoint - is the ending point.
        closeList - is the close list.
        Returns:
        the path, or null if no path found.
      • replaceSegment

        @Pure
        protected ST replaceSegment​(int index,
                                    ST segment)
        Invoked to replace a segment before adding it to the shortest path.

        * By default, this function invoked the AStarSegmentReplacer associated to this AStar algorithm.

        Parameters:
        index - is the position of the segment in the path.
        segment - is the segment to replace.
        Returns:
        the replacement segment or the segment itself.
      • invalidPathSegmentFound

        @Pure
        protected boolean invalidPathSegmentFound​(int index,
                                                  ST segment,
                                                  GP path)
        Invoked when a segment could not be added into the path.

        In standard AStar implementation, this function replies false.

        Parameters:
        index - is the index of the invalid segment.
        segment - is the segment that cannot be added
        path - is the current state of the path.
        Returns:
        true if the path building should continue, false if the path building should stop and replies a null path.