Package squidpony.squidai

Class WaypointPathfinder

java.lang.Object
squidpony.squidai.WaypointPathfinder
public class WaypointPathfinder
extends Object
Pathfind to known connections between rooms or other "chokepoints" without needing full-map Dijkstra scans. Pre-calculates a path either from or to any given chokepoint to each other chokepoint. Created by Tommy Ettinger on 10/25/2015.

  • Field Summary

    Fields 
    Modifier and Type Field Description
    StatefulRNG rng  

  • Constructor Summary

    Constructors 
    Constructor Description
    WaypointPathfinder​(char[][] map, DijkstraMap dijkstra, IRNG rng)
    Calculates and stores the doors and doors-like connections ("chokepoints") on the given map as waypoints.
    WaypointPathfinder​(char[][] map, Radius radius, IRNG rng)
    Calculates and stores the doors and doors-like connections ("chokepoints") on the given map as waypoints.
    WaypointPathfinder​(char[][] map, Radius radius, IRNG rng, boolean thickCorridors)
    Calculates and stores the doors and doors-like connections ("chokepoints") on the given map as waypoints.
    WaypointPathfinder​(char[][] map, Radius radius, IRNG rng, int fraction)
    Calculates and stores the specified fraction of walkable points from map as waypoints.

  • Method Summary

    Modifier and Type Method Description
    ArrayList<Coord> getKnownPath​(Coord self, Coord approximateTarget)
    Finds the appropriate one of the already-calculated, possibly-long paths this class stores to get from a waypoint to another waypoint, then quickly finds a path to get on the long path, and returns the total path.
    OrderedSet<Coord> getWaypoints()  
    ArrayList<Coord> goBackToPath​(Coord currentPosition, ArrayList<Coord> path)
    If a creature is interrupted or obstructed on a "highway" path, it may need to travel off the path to its goal.

    Methods inherited from class java.lang.Object

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

  • Field Details

  • Constructor Details

    • WaypointPathfinder

      public WaypointPathfinder​(char[][] map, Radius radius, IRNG rng)
      Calculates and stores the doors and doors-like connections ("chokepoints") on the given map as waypoints. Will use the given Radius enum to determine how to handle DijkstraMap measurement in future pathfinding. Uses a new RNG for all random choices, which will be seeded with rng.nextLong(), or unseeded if the parameter is null.
      Parameters:
      map - a char[][] that stores a "complete" dungeon map, with any chars as features that pathfinding needs.
      radius - a Radius that should correspond to how you want path distance calculated.
      rng - an RNG object or null (this will always use a new RNG, but it may be seeded by a given RNG's next result)

    • WaypointPathfinder

      public WaypointPathfinder​(char[][] map, Radius radius, IRNG rng, boolean thickCorridors)
      Calculates and stores the doors and doors-like connections ("chokepoints") on the given map as waypoints. Will use the given Radius enum to determine how to handle DijkstraMap measurement in future pathfinding. Uses a new RNG for all random choices, which will be seeded with rng.nextLong(), or unseeded if the parameter is null.
      Parameters:
      map - a char[][] that stores a "complete" dungeon map, with any chars as features that pathfinding needs.
      radius - a Radius that should correspond to how you want path distance calculated.
      rng - an RNG object or null (this will always use a new RNG, but it may be seeded by a given RNG's next result)
      thickCorridors - true if most chokepoints on the map are 2 cells wide instead of 1

    • WaypointPathfinder

      public WaypointPathfinder​(char[][] map, Radius radius, IRNG rng, int fraction)
      Calculates and stores the specified fraction of walkable points from map as waypoints. Does not perform any analysis of chokepoints and acts as a more brute-force solution when maps may be unpredictable. The lack of an analysis step may mean this could have drastically less of a penalty to startup time than the other constructors, and with the right fraction parameter (29 seems ideal), may perform better as well. Will use the given Radius enum to determine how to handle DijkstraMap measurement in future pathfinding. Uses a new RNG for all random choices, which will be seeded with rng.nextLong(), or unseeded if the parameter is null.
      Remember, a fraction value of 29 works well!
      Parameters:
      map - a char[][] that stores a "complete" dungeon map, with any chars as features that pathfinding needs.
      radius - a Radius that should correspond to how you want path distance calculated.
      rng - an RNG object or null (this will always use a new RNG, but it may be seeded by a given RNG's next result)
      fraction - the fractional denominator of passable cells to assign as waypoints; use 29 if you aren't sure

    • WaypointPathfinder

      public WaypointPathfinder​(char[][] map, DijkstraMap dijkstra, IRNG rng)
      Calculates and stores the doors and doors-like connections ("chokepoints") on the given map as waypoints. Will use the given DijkstraMap for pathfinding after construction (and during some initial calculations). The dijkstra parameter will be mutated by this class, so it should not be reused elsewhere. Uses a new RNG for all random choices, which will be seeded with rng.nextLong(), or unseeded if the parameter is null.
      Parameters:
      map - a char[][] that stores a "complete" dungeon map, with any chars as features that pathfinding needs
      dijkstra - a DijkstraMap that will be used to find paths; may have costs but they will not be used
      rng - an RNG object or null (this will always use a new RNG, but it may be seeded by a given RNG's next result)

  • Method Details

    • getKnownPath

      public ArrayList<Coord> getKnownPath​(Coord self, Coord approximateTarget)
      Finds the appropriate one of the already-calculated, possibly-long paths this class stores to get from a waypoint to another waypoint, then quickly finds a path to get on the long path, and returns the total path. This does not need to perform any full-map scans with DijkstraMap.
      Parameters:
      self - the pathfinder's position
      approximateTarget - the Coord that represents the approximate area to pathfind to; will be randomized if it is not walkable.
      Returns:
      an ArrayList of Coord that will go from a cell adjacent to self to a waypoint near approximateTarget

    • goBackToPath

      public ArrayList<Coord> goBackToPath​(Coord currentPosition, ArrayList<Coord> path)
      If a creature is interrupted or obstructed on a "highway" path, it may need to travel off the path to its goal. This method gets a straight-line path back to the path to goal. It does not contain the "highway" path, only the "on-ramp" to enter the ideal path.
      Parameters:
      currentPosition - the current position of the pathfinder, which is probably not on the ideal path
      path - the ideal path, probably returned by getKnownPath
      Returns:
      an ArrayList of Coord that go from a cell adjacent to currentPosition to a Coord on or adjacent to path.

    • getWaypoints

      public OrderedSet<Coord> getWaypoints()