Package squidpony.squidai.graph

Interface Heuristic<V>

Type Parameters:
V - Type of vertex; this is usually Coord
public interface Heuristic<V>
A 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).

Author:
davebaol

  • Field Summary

    Fields 
    Modifier and Type Field 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 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.

  • Method Summary

    Modifier and Type Method Description
    double estimate​(V node, V endNode)
    Calculates an estimated cost to reach the goal node from the given node.

  • Field Details

    • MANHATTAN

      static final 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. This is a good choice for graphs where only four-way movement is used.

    • CHEBYSHEV

      static final 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. This is only suggested for graphs where eight-way movement is used, and it may produce erratic paths compared to EUCLIDEAN.

    • EUCLIDEAN

      static final 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. This does not make diagonal connections, if they are allowed, actually cost more or less, but they won't be preferred if an orthogonal route can be taken. This is recommended for graphs where eight-way movement is used.

    • DIJKSTRA

      static final 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.

    • HEURISTICS

      static final List<Heuristic<Coord>> HEURISTICS
      An unmodifiable List of all the Heuristic implementations in this class.

  • Method Details

    • estimate

      double estimate​(V node, V endNode)
      Calculates an estimated cost to reach the goal node from the given node.
      Parameters:
      node - the start node
      endNode - the end node
      Returns:
      the estimated cost