V
- Type of vertex; this is usually Coord
public interface Heuristic<V>
Heuristic
generates estimates of the cost to move from a given node to the goal.
With a heuristic function pathfinding algorithms can choose the node that is most likely to lead to the optimal path.
The notion of "most likely" is controlled by a heuristic. If the heuristic is accurate, then the algorithm will be
efficient. If the heuristic is terrible, then it can perform even worse than other algorithms that don't use any
heuristic function such as Dijkstra. SquidLib's DijkstraMap
is specialized for some cases
that A* isn't, so there are reasons to prefer DijkstraMap when, for instance, you have multiple goals, or the goal is
unchanging for some section of usage but the start point changes often (this is useful for mouse tracking when the
path is reversed). The astar package should be significantly faster when paths are short and always have one goal,
unless you compare it to DijkstraMap when it can reuse a scan and call
DijkstraMap.findPathPreScanned(ArrayList, Coord)
.
Modifier and Type | Field and Description |
---|---|
static Heuristic<Coord> |
CHEBYSHEV
A predefined Heuristic for Coord nodes in a 2D plane where diagonal movement is estimated as costing the same as
orthogonal movement.
|
static Heuristic<Coord> |
DIJKSTRA
A predefined Heuristic for Coord nodes in a 2D plane where the heuristic is not used, and all cells are
considered equivalent regardless of actual distance.
|
static Heuristic<Coord> |
EUCLIDEAN
A predefined Heuristic for Coord nodes in a 2D plane where all movement is calculated "as-the-crow-flies," using
the standard Pythagorean formula for distance as in the real world.
|
static java.util.List<Heuristic<Coord>> |
HEURISTICS
An unmodifiable List of all the Heuristic implementations in this class.
|
static Heuristic<Coord> |
MANHATTAN
A predefined Heuristic for Coord nodes in a 2D plane where diagonal movement is estimated as costing twice as
much as orthogonal movement.
|
Modifier and Type | Method and Description |
---|---|
double |
estimate(V node,
V endNode)
Calculates an estimated cost to reach the goal node from the given node.
|
static final Heuristic<Coord> MANHATTAN
static final Heuristic<Coord> CHEBYSHEV
EUCLIDEAN
.static final Heuristic<Coord> EUCLIDEAN
static final Heuristic<Coord> DIJKSTRA
Copyright © Eben Howard 2012–2022. All rights reserved.