Class AStarSearch

java.lang.Object
com.github.yellowstonegames.path.AStarSearch
public class AStarSearch extends Object
Performs A* search to find the shortest path between two Coord points.
A* is a best-first search algorithm for pathfinding. It uses a heuristic value to reduce the total search space. If the heuristic is too large then the optimal path is not guaranteed to be returned.
This implementation is a thin wrapper around CostlyGraph and the other code in the com.github.yellowstonegames.path package; it is based on code from simple-graphs by earlygrey. The current version is quite fast, typically outpacing gdx-ai's more-complex IndexedAStarPathfinder by a high margin. Typical usage of this class involves either the simpler technique of only using '#' for walls or obstructions and calling AStarSearch(char[][], Heuristic), or the more complex technique that allows variable costs for different types of terrain, using CostlyGraph.generateAStarCostMap(char[][], IntFloatMap, float) to generate a cost map.
See Also:

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    protected CostlyGraph
    graph
     
    protected int
    height
     
    protected com.github.tommyettinger.ds.ObjectDeque<com.github.yellowstonegames.grid.Coord>
    path
     
    protected com.github.yellowstonegames.grid.Coord
    start
     
    protected com.github.yellowstonegames.grid.Coord
    target
     
    protected Heuristic<com.github.yellowstonegames.grid.Coord>
    type
     
    protected int
    width
     

  • Constructor Summary

    Constructors
    Modifier
    Constructor
    Description
    protected
    AStarSearch()
     
     
    AStarSearch(char[][] map, Heuristic<com.github.yellowstonegames.grid.Coord> type)
    Builds a pathing object to run searches on.
     
    AStarSearch(float[][] map, Heuristic<com.github.yellowstonegames.grid.Coord> type)
    Builds a pathing object to run searches on.

  • Method Summary

    Modifier and Type
    Method
    Description
    int
    getHeight()
     
    int
    getWidth()
     
    com.github.tommyettinger.ds.ObjectDeque<com.github.yellowstonegames.grid.Coord>
    path(int startx, int starty, int targetx, int targety)
    Finds an A* path to the target from the start.
    com.github.tommyettinger.ds.ObjectDeque<com.github.yellowstonegames.grid.Coord>
    path(com.github.yellowstonegames.grid.Coord start, com.github.yellowstonegames.grid.Coord target)
    Finds an A* path to the target from the start.
    AStarSearch
    reinitialize(char[][] map, Heuristic<com.github.yellowstonegames.grid.Coord> type)
    Resets this pathing object to use a different map and optionally a different Heuristic.
    AStarSearch
    reinitialize(float[][] map, Heuristic<com.github.yellowstonegames.grid.Coord> type)
    Resets this pathing object to use a different map and optionally a different Heuristic.
    String
    toString()
     

    Methods inherited from class Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

  • Field Details

    • width

      protected int width

    • height

      protected int height

    • start

      protected com.github.yellowstonegames.grid.Coord start

    • target

      protected com.github.yellowstonegames.grid.Coord target

    • type

      protected Heuristic<com.github.yellowstonegames.grid.Coord> type

    • graph

      protected CostlyGraph graph

    • path

      protected com.github.tommyettinger.ds.ObjectDeque<com.github.yellowstonegames.grid.Coord> path

  • Constructor Details

    • AStarSearch

      protected AStarSearch()

    • AStarSearch

      public AStarSearch(float[][] map, Heuristic<com.github.yellowstonegames.grid.Coord> type)
      Builds a pathing object to run searches on.
      Values in the map are treated as positive values being legal weights, with higher values being harder to pass through. Any negative value is treated as being an impassible space. A weight of 0 can be moved through at no cost, but this should be used very carefully, if at all. Cost maps are commonly built using the CostlyGraph.generateAStarCostMap(char[][], IntFloatMap, float) and CostlyGraph.generateAStarCostMap(char[][]) methods from a 2D char array.
      If the type is Manhattan, only the cardinal directions will be used. All other search types will return a result based on diagonal and cardinal pathing (8-way).
      Parameters:
      map - the search map, as produced by CostlyGraph.generateAStarCostMap(char[][])
      type - a Heuristic constant; one of the four from from Heuristic.HEURISTICS

    • AStarSearch

      public AStarSearch(char[][] map, Heuristic<com.github.yellowstonegames.grid.Coord> type)
      Builds a pathing object to run searches on.
      Values in the map are all considered equally passable unless the char is '#', in which case it is considered an impassable wall. The getBareDungeon() method in squidplace's DungeonProcessor class is a common way to get a map where only '#' is used to mean a wall.
      If the type is Manhattan, only the cardinal directions will be used. All other search types will return a result based on diagonal and cardinal pathing (8-way).
      Parameters:
      map - a 2D char array where only '#' represents a wall, and anything else is equally passable
      type - the manner of search

  • Method Details

    • reinitialize

      public AStarSearch reinitialize(float[][] map, Heuristic<com.github.yellowstonegames.grid.Coord> type)
      Resets this pathing object to use a different map and optionally a different Heuristic.
      Values in the map are treated as positive values being legal weights, with higher values being harder to pass through. Any negative value is treated as being an impassible space. A weight of 0 can be moved through at no cost, but this should be used very carefully, if at all. Cost maps are commonly built using the CostlyGraph.generateAStarCostMap(char[][], IntFloatMap, float) and CostlyGraph.generateAStarCostMap(char[][]) methods from a 2D char array.
      If the type is Manhattan, only the cardinal directions will be used. All other search types will return a result based on diagonal and cardinal pathing (8-way).
      Parameters:
      map - the search map, as produced by CostlyGraph.generateAStarCostMap(char[][])
      type - the manner of search

    • reinitialize

      public AStarSearch reinitialize(char[][] map, Heuristic<com.github.yellowstonegames.grid.Coord> type)
      Resets this pathing object to use a different map and optionally a different Heuristic.
      Values in the map are all considered equally passable unless the char is '#', '+', or any box drawing character, in which case it is considered an impassable wall. The getBareDungeon() method in squidplace's DungeonProcessor class is a common way to get a map where only '#' is used to mean a wall.
      If the type is Manhattan, only the cardinal directions will be used. All other search types will return a result based on diagonal and cardinal pathing (8-way).
      Parameters:
      map - a 2D char array where only '#' represents a wall, and anything else is equally passable
      type - the manner of search

    • path

      public com.github.tommyettinger.ds.ObjectDeque<com.github.yellowstonegames.grid.Coord> path(int startx, int starty, int targetx, int targety)
      Finds an A* path to the target from the start. If no path is possible, returns null. Reuses the returned path instead of allocating a new ObjectDeque, so if you call this again, then the previously-returned List could change.
      Parameters:
      startx - the x coordinate of the start location
      starty - the y coordinate of the start location
      targetx - the x coordinate of the target location
      targety - the y coordinate of the target location
      Returns:
      the shortest path, or null if no path is possible

    • path

      public com.github.tommyettinger.ds.ObjectDeque<com.github.yellowstonegames.grid.Coord> path(com.github.yellowstonegames.grid.Coord start, com.github.yellowstonegames.grid.Coord target)
      Finds an A* path to the target from the start. If no path is possible, returns null. Reuses the returned path instead of allocating a new ObjectDeque, so if you call this again, then the previously-returned List could change.
      Parameters:
      start - the start location
      target - the target location
      Returns:
      the shortest path, or null if no path is possible

    • getWidth

      public int getWidth()

    • getHeight

      public int getHeight()

    • toString

      public String toString()
      Overrides:
      toString in class Object