T
- the type of all nodes in the Graph
public class AStar<T> extends java.lang.Object implements GraphPath<T>
Graph
instances.
Finds the best path to move a GraphAgent
from one specified Graph
node
to another. The "best path" is the one whose total cost is minimal compared to all
other connecting paths, where the total cost of a path is defined as the sum of all
GraphAgent.getStepCost(T, T)
results for each step between two adjacent path nodes.
This implementation of the A* algorithm is based on the CAStar class created by James Matthews. The original source code supplemented his article "Basic A* Pathfinding Made Simple", pages 105-113 in "AI Game Programming Wisdom", Charles River Media, 2002.
Caution: Multi-step movements are problematic when the GraphAgent
uses
a non-trivial GraphAgent.canOccupy(T)
condition. After a successful path search,
bestNode()
is always valid and optimal for a single-step movement. However,
calling getLastNode(double)
with less than the maximum path cost may yield a
suboptimal intermediate node, or none at all. Since the algorithm does not know whether
a given intermediate path node will be occupied permanently or merely traversed, the final
path may contain many intermediate nodes for which GraphAgent.canOccupy(T)
fails.
Modifier and Type | Field and Description |
---|---|
Graph<T> |
graph
The
Graph on which all searches are performed. |
boolean |
useWorldDistance
Determines whether
AStar should prefer path nodes with a minimal target distance. |
Modifier and Type | Method and Description |
---|---|
double |
absoluteLimit()
Gets the absolute limit on the search radius for the last path search.
|
GraphAgent<T> |
agent()
Gets the
GraphAgent for the last search. |
PathNode<T> |
bestNode()
Gets the final node found by the last successful path search.
|
boolean |
findBestPath(GraphAgent<T> agent,
T source,
T target)
Finds the best path to move the specified
GraphAgent
from one specified graph node to another. |
T |
getLastNode(double maxCost)
Gets the last
graph node in the best path whose
total path cost does not exceed the specified maximum cost. |
PathNode<T> |
getLastPathNode(double maxCost)
Gets the last
PathNode in the best path whose
total path cost does not exceed the specified maximum cost. |
java.util.List<T> |
nodes()
Gets all
graph nodes in the best path found by the last successful path search. |
double |
relativeLimit()
Gets the limit on the search radius, relative to the distance between source and target node.
|
void |
setRelativeLimit(double value)
Sets the limit on the search radius, relative to the distance between source and target node.
|
double |
totalCost()
Gets the total cost of the best path found by the last successful path search.
|
public boolean useWorldDistance
AStar
should prefer path nodes with a minimal target distance.
true
to prefer path nodes with a minimal distance from the target node,
in world coordinates, else false
. The default is false
.
When true
, candidate path nodes whose path costs are identical are also
compared for their distances from the target node, using the world coordinates
returned by Graph.getWorldLocation(T)
.
This eliminates zero-cost oscillations in the final path, creating a smoother and
more "natural" course. However, the additional calculations and comparisons may slow
down pathfinding. useWorldDistance
has no effect if Graph.getDistance(T, T)
already uses world coordinates.
public boolean findBestPath(GraphAgent<T> agent, T source, T target)
GraphAgent
from one specified graph
node to another.
Returns false
if graph
does not contain both source
and target
, or if no connecting path could be found. Otherwise,
returns true
and sets bestNode()
, nodes()
, and
totalCost()
to the results of the path search.
findBestPath
calls GraphAgent.canOccupy(T)
and GraphAgent.isNearTarget(T, T, double)
on the specified agent
to determine whether a
given bestNode()
candidate is acceptable. Depending on the implementation
of isNearTarget
, the PathNode.node
of the final bestNode()
may differ from the specified target
, and possibly equal the specified
source
. canOccupy
is never called on the source
node.
findBestPath
operates with a restricted search radius if relativeLimit()
is greater than zero. In this case, absoluteLimit()
is set
to the product (rounded up) of relativeLimit()
and the distance between
source
and target
. Whenever a node is considered for inclusion in
the search path, its distances from source
and target
are calculated,
and the node is ignored if the sum exceeds absoluteLimit()
.
agent
- the GraphAgent
that performs the movementsource
- the source node within graph
target
- the source node within graph
true
if a best path between source
and target
could be found, else false
java.lang.NullPointerException
- if any argument is null
public double absoluteLimit()
absoluteLimit()
are not added to the search path.
Set by findBestPath(org.kynosarges.tektosyne.graph.GraphAgent<T>, T, T)
depending on the current relativeLimit()
.
See there for further details.
Graph.getDistance(T, T)
, between
any one graph
node in the search path and the source and target nodespublic GraphAgent<T> agent()
GraphAgent
for the last search.GraphAgent
that was supplied to the last findBestPath(org.kynosarges.tektosyne.graph.GraphAgent<T>, T, T)
call, or null
if the method has not yet been calledpublic PathNode<T> bestNode()
null
if the last findBestPath(org.kynosarges.tektosyne.graph.GraphAgent<T>, T, T)
call returned
false
, or if the method has not yet been called.
Otherwise, the best path ended by bestNode()
is stored in nodes()
by backtracking through the PathNode.parent()
links of all connected
PathNode
instances.
PathNode
that represents the target node of the last successful
findBestPath(org.kynosarges.tektosyne.graph.GraphAgent<T>, T, T)
call, ending the best pathpublic T getLastNode(double maxCost)
graph
node in the best path whose
total path cost does not exceed the specified maximum cost.
Returns the PathNode.node
associated with the PathNode
found by getLastPathNode
for maxCost
. See there for details.getLastNode
in interface GraphPath<T>
maxCost
- the maximum total path cost of the graph
nodePathNode.node
of the last nodes()
element
whose total path cost does not exceed maxCost
java.lang.IllegalArgumentException
- if maxCost
is equal to or less than zerojava.lang.IllegalStateException
- if bestNode()
is null
public PathNode<T> getLastPathNode(double maxCost)
PathNode
in the best path whose
total path cost does not exceed the specified maximum cost.
Always returns a PathNode
whose PathNode.node
is an element
of nodes()
. The exact element depends on the specified maxCost
.
getLastPathNode
searches for the PathNode
that is the last
PathNode.parent()
of bestNode()
whose PathNode.g()
value
does not exceed the specified maxCost
, and for which GraphAgent.canOccupy(T)
succeeds with the moving agent()
.
If GraphAgent.relaxedRange()
is true
for the moving agent()
,
the PathNode.g()
value of the returned PathNode
may exceed
maxCost
if the PathNode.g()
value of its PathNode.parent()
node is strictly less than maxCost
.
If the specified maxCost
exceeds the cost of all nodes, or if GraphAgent.canOccupy(T)
fails for all affordable nodes, getLastPathNode
returns the PathNode
that corresponds to the first nodes()
element,
i.e. the source node of the path search.
maxCost
- the maximum total path cost of the PathNode
PathNode
that is the last parent of bestNode()
whose total path cost does not exceed maxCost
java.lang.IllegalArgumentException
- if maxCost
is equal to or less than zerojava.lang.IllegalStateException
- if bestNode()
is null
public java.util.List<T> nodes()
graph
nodes in the best path found by the last successful path search.
Returns an empty collection if the last findBestPath(org.kynosarges.tektosyne.graph.GraphAgent<T>, T, T)
call returned
false
, or if the method has not yet been called.
Otherwise, first element is always the source node, and the last element is
always the PathNode.node
represented by bestNode()
.
nodes
in interface GraphPath<T>
List
containing all graph
nodes that constitute
the best movement path found by the last successful findBestPath(org.kynosarges.tektosyne.graph.GraphAgent<T>, T, T)
call,
including source and target nodepublic double relativeLimit()
relativeLimit()
is always equal to or greater than one.
See absoluteLimit()
, findBestPath(org.kynosarges.tektosyne.graph.GraphAgent<T>, T, T)
, and setRelativeLimit(double)
for further details.
Graph.getDistance(T, T)
, to obtain the absoluteLimit
on the search radiuspublic void setRelativeLimit(double value)
relativeLimit()
defines its inverse eccentricity.
See absoluteLimit()
and findBestPath(org.kynosarges.tektosyne.graph.GraphAgent<T>, T, T)
for further details.
value
- the factor to multiply with the distance between source and target node, according to
Graph.getDistance(T, T)
, to obtain the absoluteLimit
on the search radiusjava.lang.IllegalArgumentException
- if value
is less than zero,
or greater than zero but smaller than onepublic double totalCost()
bestNode()
is null
. This is the case if the last findBestPath(org.kynosarges.tektosyne.graph.GraphAgent<T>, T, T)
call returned false
, or if the method has not yet been called.totalCost
in interface GraphPath<T>
PathNode.g()
value of bestNode()
, which is the sum
of the GraphAgent.getStepCost(T, T)
results for all nodes()