Package org.arakhne.afc.math.graph.astar
Class AStar<GP extends GraphPath<GP,ST,PT>,ST extends GraphSegment<ST,PT>,PT extends GraphPoint<PT,ST>>
- java.lang.Object
-
- org.arakhne.afc.math.graph.astar.AStar<GP,ST,PT>
-
- Type Parameters:
GP
- is the type of the graph graph itself.PT
- is the type of node in the graphST
- 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
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description protected class
AStar.Candidate
Candidate node in the A* algorithm, and its related information.protected static class
AStar.CloseComparator<ST extends GraphSegment<ST,PT>,PT extends GraphPoint<PT,ST>>
Comparator used to sort the close list of A* algorithm.protected static class
AStar.OpenComparator<ST extends GraphSegment<ST,PT>,PT extends GraphPoint<PT,ST>>
Comparator used to sort the open list of A* algorithm.
-
Constructor Summary
Constructors Constructor Description AStar(AStarHeuristic<? super PT> heuristic, Class<? extends GP> pathType)
Constructor.AStar(AStarHeuristic<? super PT> heuristic, AStarPathFactory<GP,ST,PT> pathFactory1)
Constructor.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description void
addAStarListener(AStarListener<ST,PT> listener)
Add listener on A* algorithm events.protected boolean
addToPath(GP path, ST segment)
Add the given segment into the given path.protected double
computeCostFor(PT pt)
Compute and replies the cost to traverse the given graph point.protected double
computeCostFor(ST segment)
Compute and replies the cost to traverse the given graph segment.(package private) GP
createPath(AStarNode<ST,PT> startPoint, PT endPoint, List<AStarNode<ST,PT>> closeList)
Create the path from the given close list.protected double
estimate(PT p1, PT p2)
Evaluate the distance between two points in the graph.(package private) 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.AStarCostComputer<? super ST,? super PT>
getCostComputer()
Replies the tool that permits to compute the costs of the nodes and edges.AStarHeuristic<? super PT>
getEvaluationHeuristic()
Replies the evaluation heuristic used by the A* algorithm.AStarPathFactory<GP,ST,PT>
getPathFactory()
Replies the path factory used by the A* algorithm.AStarSegmentOrientation<ST,PT>
getSegmentOrientationTool()
Replies the tool that permits to retreive the orinetation of the segments..AStarSegmentReplacer<ST>
getSegmentReplacer()
Replies the object used to replace the segments in the shortest path.protected boolean
invalidPathSegmentFound(int index, ST segment, GP path)
Invoked when a segment could not be added into the path.boolean
isClosedNodeReopeningEnabled()
Replies the flag that permits to reopen the closed A* nodes.protected AStarNode<ST,PT>
newAStarNode(PT node, double cost, double estimatedCost, ST arrival)
Create a instance ofA* node
.protected GP
newPath(PT startPoint, ST segment)
Create an empty path.void
removeAStarListener(AStarListener<ST,PT> listener)
Remove listener on A* algorithm events.protected ST
replaceSegment(int index, ST segment)
Invoked to replace a segment before adding it to the shortest path.void
setClosedNodeReopeningEnabled(boolean enableClosedNodeReopening1)
Change the flag that permits to reopen the closed A* nodes.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.AStarHeuristic<? super PT>
setEvaluationHeuristic(AStarHeuristic<? super PT> heuristic)
Set the evaluation heuristic used by the A* algorithm.AStarPathFactory<GP,ST,PT>
setPathFactory(AStarPathFactory<GP,ST,PT> factory)
Set the path factory used by the A* algorithm.AStarPathFactory<GP,ST,PT>
setPathType(Class<? extends GP> type)
Set the path factory used by the A* algorithm.AStarSegmentOrientation<ST,PT>
setSegmentOrientationTool(AStarSegmentOrientation<ST,PT> tool)
Set the tool that permits to retreive the orinetation of the segments.AStarSegmentReplacer<ST>
setSegmentReplacer(AStarSegmentReplacer<ST> replacer)
Set the object to use to replace the segments in the shortest path.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.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.protected AStarNode<ST,PT>
translateCandidate(PT endPoint, AStarNode<ST,PT> node)
Translate the A* node.
-
-
-
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
- istrue
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.
-
setPathFactory
public AStarPathFactory<GP,ST,PT> setPathFactory(AStarPathFactory<GP,ST,PT> factory)
Set the path factory used by the A* algorithm.- Parameters:
factory
- is the new factory.- Returns:
- the old factory
- See Also:
setPathType(Class)
-
setPathType
public AStarPathFactory<GP,ST,PT> setPathType(Class<? extends GP> type)
Set the path factory used by the A* algorithm.- Parameters:
type
- is the type of path to instance with a reflection-based factory.- Returns:
- the old factory
- See Also:
setPathFactory(AStarPathFactory)
-
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
andp2
.
-
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 repliesnull
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; otherwisefalse
.
-
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 ofA* 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 addedpath
- is the current state of the path.- Returns:
true
if the path building should continue,false
if the path building should stop and replies anull
path.
-
-