Package squidpony.squidmath

Class AStarSearch

java.lang.Object
squidpony.squidmath.AStarSearch
All Implemented Interfaces:
Serializable
public class AStarSearch
extends Object
implements Serializable
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 squidpony.squidai.graph package; it replaces an older, much-less-efficient A* implementation with one 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. The only major change in the API is that this version returns an ArrayList of Coord instead of a Queue of Coord. Typical usage of this class involves either the simpler technique of only using '#' for walls or obstructions and calling AStarSearch(char[][], SearchType), or the more complex technique that allows variable costs for different types of terrain, using DungeonUtility.generateAStarCostMap(char[][], Map, double) to generate a cost map; if you used the old AStarSearch, then be advised that the default cost is now 1.0 instead of 0.0.
Author:
Eben Howard - http://squidpony.com - howard@squidpony.com, Tommy Ettinger - optimized code, earlygrey - wrote and really optimized simple-graphs, which this uses heavily
See Also:
the pathfinding class this is based on; CostlyGraph can be used independently, a sometimes-faster pathfinding algorithm that can pathfind to multiple goals, an alternative to DijkstraMap; faster and supports complex adjacency rules, Serialized Form

  • Field Details

  • Constructor Details

    • AStarSearch

      protected AStarSearch()

    • AStarSearch

      public AStarSearch​(double[][] map, AStarSearch.SearchType 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 DungeonUtility.generateAStarCostMap(char[][], Map, double) and DungeonUtility.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 DungeonUtility.generateAStarCostMap(char[][])
      type - the manner of search

    • AStarSearch

      public AStarSearch​(char[][] map, AStarSearch.SearchType 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 DungeonGenerator.getBareDungeon() method 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​(double[][] map, AStarSearch.SearchType type)
      Resets this pathing object to use a different map and optionally a different SearchType.
      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 DungeonUtility.generateAStarCostMap(char[][], Map, double) and DungeonUtility.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 DungeonUtility.generateAStarCostMap(char[][])
      type - the manner of search

    • reinitialize

      public AStarSearch reinitialize​(char[][] map, AStarSearch.SearchType type)
      Resets this pathing object to use a different map and optionally a different SearchType.
      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. DungeonGenerator.getBareDungeon() 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 ArrayList<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.
      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 ArrayList<Coord> path​(Coord start, Coord target)
      Finds an A* path to the target from the start. If no path is possible, returns null.
      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