Class DijkstraMap

java.lang.Object
com.github.yellowstonegames.path.DijkstraMap
public class DijkstraMap extends Object
A group of pathfinding algorithms that explore in all directions equally, and are commonly used when there is more than one valid goal, or when you want a gradient floodfill to mark each cell in an area with its distance from a goal. This type of pathfinding is called a Dijkstra Map because it produces the same type of grid of distances from the nearest goal as Dijkstra's Pathfinding Algorithm can, but the actual algorithm used here is simpler than Dijkstra's Algorithm, and is more comparable to an optimized breadth-first search that doesn't consider edge costs. You can set more than one goal with setGoal(Coord) or setGoals(Iterable), unlike A*; having multiple goals enables such features as pathfinding for creatures that can attack targets between a specified minimum and maximum distance, and the standard uses of Dijkstra Maps such as finding ideal paths to run away. All these features have some price; when paths are short or unobstructed, A* tends to be faster, though some convoluted map shapes can slow down A* more than DijkstraMap.
One unique optimization made possible by Dijkstra Maps is for when only one endpoint of a path can change in some section of a game, such as when you want to draw a path from the (stationary) player's current cell to the cell the mouse is over, and the mouse can move quickly. This can be done very efficiently by setting the player as a goal with setGoal(Coord), scanning the map to find distances with scan(Iterable), and then as long as the player's position is unchanged (and no obstacles are added/moved), you can get the path by calling findPathPreScanned(Coord) and giving it the mouse position as a Coord. If various parts of the path can change instead of just one (such as other NPCs moving around), then you should set a goal or goals and call findPath(int, Collection, Collection, Coord, Coord...). The parameters for this are used in various methods in this class with only slight differences: length is the length of path that can be moved "in one go," so 1 for most roguelikes and more for most strategy games, impassable used for enemies and solid moving obstacles, onlyPassable can be null in most roguelikes but in strategy games should contain ally positions that can be moved through as long as no one stops in them (it can also contain terrain that must be jumped over without falling in, like lava), start is the pathfinding NPC's starting position, and targets is an array or vararg of Coord that the NPC should pathfind toward (it could be just one Coord, with or without explicitly putting it in an array, or it could be more and the NPC will pick the closest).
As a bit of introduction, this article on RogueBasin can provide some useful information on how these work and how to visualize the information they can produce, while the original article that introduced Dijkstra Maps is an inspiring list of the various features Dijkstra Maps can enable.
If you can't remember how to spell this, just remember: Does It Just Know Stuff? That's Really Awesome!
You shouldn't use DijkstraMap for all purposes; it isn't very good at handling terrains with a cost to enter, and can't handle directional costs like a one-way ledge. For those tasks, DefaultGraph or CostlyGraph will be better fits. CostlyGraph and similar versions of DirectedGraph can handle even very complicated kinds of map, including the types of pathfinding that were handled by CustomDijkstraMap in earlier versions of SquidLib.

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    float[][]
    costMap
    This stores the entry cost multipliers for each cell; that is, a value of 1f is a normal, unmodified cell, but a value of 0.5f can be entered easily (two cells of its cost can be entered for the cost of one 1f cell), and a value of 2f can only be entered with difficulty (one cell of its cost can be entered for the cost of two 1f cells).
    boolean
    cutShort
     
    static final float
    DARK
    This is used to mark cells that the scan couldn't reach, and these dark cells are marked with a high number equal to 999800f .
    static final float
    FLOOR
    Floor cells, which include any walkable cell, are marked with a high number equal to 999200f .
    protected com.github.tommyettinger.ds.IntDeque
    fresh
    Working data used during scanning, this tracks the perimeter of the scanned area so far.
    static final float
    GOAL
    Goals are by default marked with 0f.
    protected com.github.tommyettinger.ds.IntList
    goals
    Goals that pathfinding will seek out.
    float[][]
    gradientMap
    The frequently-changing values that are often the point of using this class; goals will have a value of 0, and any cells that can have a character reach a goal in n steps will have a value of n.
    int
    height
    Height of the map.
    com.github.yellowstonegames.grid.Measurement
    measurement
    This affects how distance is measured on diagonal directions vs.
    com.github.tommyettinger.ds.ObjectDeque<com.github.yellowstonegames.grid.Coord>
    path
    The latest path that was obtained by calling findPath().
    float[][]
    physicalMap
    Stores which parts of the map are accessible and which are not.
    protected com.github.tommyettinger.random.FlowRandom
    rng
    The FlowRandom used to decide which one of multiple equally-short paths to take; this has its state set deterministically before any usage.
    boolean
    standardCosts
     
    com.github.yellowstonegames.grid.Coord[][]
    targetMap
     
    static final float
    WALL
    Walls, which are solid no-entry cells, are marked with a high number equal to 999500f .
    int
    width
    Width of the map.

  • Constructor Summary

    Constructors
    Constructor
    Description
    DijkstraMap()
    Construct a DijkstraMap without a level to actually scan.
    DijkstraMap(char[][] level)
    Constructor meant to take a char[][] returned by DungeonBoneGen.generate(), or any other char[][] where '#' means a wall and anything else is a walkable tile.
    DijkstraMap(char[][] level, char alternateWall)
    Constructor meant to take a char[][] returned by DungeonBoneGen.generate(), or any other char[][] where one char means a wall and anything else is a walkable tile.
    DijkstraMap(char[][] level, com.github.yellowstonegames.grid.Measurement measurement)
    Constructor meant to take a char[][] returned by DungeonBoneGen.generate(), or any other char[][] where '#' means a wall and anything else is a walkable tile.
    DijkstraMap(float[][] level)
    Used to construct a DijkstraMap from the output of another.
    DijkstraMap(float[][] level, com.github.yellowstonegames.grid.Measurement measurement)
    Used to construct a DijkstraMap from the output of another, specifying a distance calculation.
    DijkstraMap(float[][] level, com.github.yellowstonegames.grid.Measurement measurement, boolean levelIsResistanceMap)
    Used to construct a DijkstraMap from either the output of another DijkstraMap, or from a resistance map of the type used by FOV.

  • Method Summary

    Modifier and Type
    Method
    Description
    void
    clearGoals()
    Used to remove all goals and undo any changes to gradientMap made by having a goal present.
    com.github.yellowstonegames.grid.Coord
    decode(int encoded)
    If you for some reason have one of the internally-used ints produced by encode(Coord), this will convert it back to a Coord if you need it as such.
    int
    decodeX(int encoded)
    If you for some reason have one of the internally-used ints produced by encode(Coord), this will decode the x component of the point encoded in that int.
    int
    decodeY(int encoded)
    If you for some reason have one of the internally-used ints produced by encode(Coord), this will decode the y component of the point encoded in that int.
    int
    encode(int x, int y)
    Internally, DijkstraMap uses int primitives instead of Coord objects.
    int
    encode(com.github.yellowstonegames.grid.Coord point)
    Internally, DijkstraMap uses int primitives instead of Coord objects.
    com.github.tommyettinger.ds.ObjectDeque<com.github.yellowstonegames.grid.Coord>
    findAttackPath(int moveLength, int minPreferredRange, int maxPreferredRange, com.github.yellowstonegames.grid.LineDrawer los, Collection<com.github.yellowstonegames.grid.Coord> impassable, Collection<com.github.yellowstonegames.grid.Coord> onlyPassable, com.github.yellowstonegames.grid.Coord start, com.github.yellowstonegames.grid.Coord... targets)
    Scans the dungeon using DijkstraMap.scan with the listed goals and start point, and returns a list of Coord positions (using the current measurement) needed to get closer to a goal, until a cell is reached with a distance from a goal that is at least equal to minPreferredRange and no more than maxPreferredRange, which may go further from a goal if the minPreferredRange has not been met at the current distance.
    com.github.tommyettinger.ds.ObjectDeque<com.github.yellowstonegames.grid.Coord>
    findAttackPath(int moveLength, int preferredRange, com.github.yellowstonegames.grid.LineDrawer los, Collection<com.github.yellowstonegames.grid.Coord> impassable, Collection<com.github.yellowstonegames.grid.Coord> onlyPassable, com.github.yellowstonegames.grid.Coord start, com.github.yellowstonegames.grid.Coord... targets)
    Scans the dungeon using DijkstraMap.scan with the listed goals and start point, and returns a list of Coord positions (using the current measurement) needed to get closer to a goal, until preferredRange is reached, or further from a goal if the preferredRange has not been met at the current distance.
    com.github.tommyettinger.ds.ObjectDeque<com.github.yellowstonegames.grid.Coord>
    findAttackPath(com.github.tommyettinger.ds.ObjectDeque<com.github.yellowstonegames.grid.Coord> buffer, int moveLength, int minPreferredRange, int maxPreferredRange, com.github.yellowstonegames.grid.LineDrawer los, Collection<com.github.yellowstonegames.grid.Coord> impassable, Collection<com.github.yellowstonegames.grid.Coord> onlyPassable, com.github.yellowstonegames.grid.Coord start, com.github.yellowstonegames.grid.Coord... targets)
    Scans the dungeon using DijkstraMap.scan with the listed goals and start point, and returns a list of Coord positions (using the current measurement) needed to get closer to a goal, until a cell is reached with a distance from a goal that is at least equal to minPreferredRange and no more than maxPreferredRange, which may go further from a goal if the minPreferredRange has not been met at the current distance.
    com.github.tommyettinger.ds.ObjectDeque<com.github.yellowstonegames.grid.Coord>
    findAttackPathLarge(int size, int moveLength, int minPreferredRange, int maxPreferredRange, com.github.yellowstonegames.grid.LineDrawer los, Collection<com.github.yellowstonegames.grid.Coord> impassable, Collection<com.github.yellowstonegames.grid.Coord> onlyPassable, com.github.yellowstonegames.grid.Coord start, com.github.yellowstonegames.grid.Coord... targets)
    Scans the dungeon using DijkstraMap.scan with the listed goals and start point, and returns a list of Coord positions (using the current measurement) needed to get closer to a goal, until a cell is reached with a distance from a goal that is at least equal to minPreferredRange and no more than maxPreferredRange, which may go further from a goal if the minPreferredRange has not been met at the current distance.
    com.github.tommyettinger.ds.ObjectDeque<com.github.yellowstonegames.grid.Coord>
    findAttackPathLarge(int size, int moveLength, int preferredRange, com.github.yellowstonegames.grid.LineDrawer los, Collection<com.github.yellowstonegames.grid.Coord> impassable, Collection<com.github.yellowstonegames.grid.Coord> onlyPassable, com.github.yellowstonegames.grid.Coord start, com.github.yellowstonegames.grid.Coord... targets)
    For pathfinding creatures larger than 1x1 cell; scans the dungeon using DijkstraMap.scan with the listed goals and start point, and returns a list of Coord positions (using the current measurement) needed to get closer to a goal, until preferredRange is reached, or further from a goal if the preferredRange has not been met at the current distance.
    com.github.tommyettinger.ds.ObjectDeque<com.github.yellowstonegames.grid.Coord>
    findFleePath(int length, float preferLongerPaths, Collection<com.github.yellowstonegames.grid.Coord> impassable, Collection<com.github.yellowstonegames.grid.Coord> onlyPassable, com.github.yellowstonegames.grid.Coord start, com.github.yellowstonegames.grid.Coord... fearSources)
    Scans the dungeon using DijkstraMap.scan() with the listed fearSources and start point, and returns a list of Coord positions (using Manhattan distance) needed to get further from the closest fearSources, meant for running away.
    com.github.tommyettinger.ds.ObjectDeque<com.github.yellowstonegames.grid.Coord>
    findFleePath(int length, int scanLimit, float preferLongerPaths, Collection<com.github.yellowstonegames.grid.Coord> impassable, Collection<com.github.yellowstonegames.grid.Coord> onlyPassable, com.github.yellowstonegames.grid.Coord start, com.github.yellowstonegames.grid.Coord... fearSources)
    Scans the dungeon using DijkstraMap.scan or DijkstraMap.partialScan with the listed fearSources and start point, and returns a list of Coord positions (using this DijkstraMap's metric) needed to get further from the closest fearSources, meant for running away.
    com.github.tommyettinger.ds.ObjectDeque<com.github.yellowstonegames.grid.Coord>
    findFleePath(com.github.tommyettinger.ds.ObjectDeque<com.github.yellowstonegames.grid.Coord> buffer, int length, int scanLimit, float preferLongerPaths, Collection<com.github.yellowstonegames.grid.Coord> impassable, Collection<com.github.yellowstonegames.grid.Coord> onlyPassable, com.github.yellowstonegames.grid.Coord start, com.github.yellowstonegames.grid.Coord... fearSources)
    Scans the dungeon using DijkstraMap.scan or DijkstraMap.partialScan with the listed fearSources and start point, and returns a list of Coord positions (using this DijkstraMap's metric) needed to get further from the closest fearSources, meant for running away.
    com.github.tommyettinger.ds.ObjectDeque<com.github.yellowstonegames.grid.Coord>
    findFleePathLarge(int size, int length, float preferLongerPaths, Collection<com.github.yellowstonegames.grid.Coord> impassable, Collection<com.github.yellowstonegames.grid.Coord> onlyPassable, com.github.yellowstonegames.grid.Coord start, com.github.yellowstonegames.grid.Coord... fearSources)
    Scans the dungeon using DijkstraMap.scan with the listed fearSources and start point, and returns a list of Coord positions (using Manhattan distance) needed to get further from the closest fearSources, meant for running away.
    com.github.yellowstonegames.grid.Coord
    findNearest(com.github.yellowstonegames.grid.Coord start, com.github.yellowstonegames.grid.Coord... targets)
    Recalculate the Dijkstra map until it reaches a Coord in targets, then returns the first target found.
    com.github.yellowstonegames.grid.Coord
    findNearest(com.github.yellowstonegames.grid.Coord start, Collection<com.github.yellowstonegames.grid.Coord> targets)
    Recalculate the Dijkstra map until it reaches a Coord in targets, then returns the first target found.
    com.github.tommyettinger.ds.ObjectDeque<com.github.yellowstonegames.grid.Coord>
    findNearestMultiple(com.github.yellowstonegames.grid.Coord start, int limit, Collection<com.github.yellowstonegames.grid.Coord> targets)
    Recalculate the Dijkstra map until it reaches a Coord in targets, then returns the first several targets found, up to limit or less if the map is fully searched without finding enough.
    com.github.tommyettinger.ds.ObjectDeque<com.github.yellowstonegames.grid.Coord>
    findPath(int length, int scanLimit, Collection<com.github.yellowstonegames.grid.Coord> impassable, Collection<com.github.yellowstonegames.grid.Coord> onlyPassable, com.github.yellowstonegames.grid.Coord start, com.github.yellowstonegames.grid.Coord... targets)
    Scans the dungeon using DijkstraMap.scan or DijkstraMap.partialScan with the listed goals and start point, and returns a list of Coord positions (using the current measurement) needed to get closer to the closest reachable goal.
    com.github.tommyettinger.ds.ObjectDeque<com.github.yellowstonegames.grid.Coord>
    findPath(int length, Collection<com.github.yellowstonegames.grid.Coord> impassable, Collection<com.github.yellowstonegames.grid.Coord> onlyPassable, com.github.yellowstonegames.grid.Coord start, com.github.yellowstonegames.grid.Coord... targets)
    Scans the dungeon using DijkstraMap.scan with the listed goals and start point, and returns a list of Coord positions (using the current measurement) needed to get closer to the closest reachable goal.
    com.github.tommyettinger.ds.ObjectDeque<com.github.yellowstonegames.grid.Coord>
    findPath(com.github.tommyettinger.ds.ObjectDeque<com.github.yellowstonegames.grid.Coord> buffer, int length, int scanLimit, Collection<com.github.yellowstonegames.grid.Coord> impassable, Collection<com.github.yellowstonegames.grid.Coord> onlyPassable, com.github.yellowstonegames.grid.Coord start, com.github.yellowstonegames.grid.Coord... targets)
    Scans the dungeon using DijkstraMap.scan or DijkstraMap.partialScan with the listed goals and start point, and returns a list of Coord positions (using the current measurement) needed to get closer to the closest reachable goal.
    com.github.tommyettinger.ds.ObjectDeque<com.github.yellowstonegames.grid.Coord>
    findPathLarge(int size, int length, int scanLimit, Collection<com.github.yellowstonegames.grid.Coord> impassable, Collection<com.github.yellowstonegames.grid.Coord> onlyPassable, com.github.yellowstonegames.grid.Coord start, com.github.yellowstonegames.grid.Coord... targets)
     
    com.github.tommyettinger.ds.ObjectDeque<com.github.yellowstonegames.grid.Coord>
    findPathLarge(int size, int length, Collection<com.github.yellowstonegames.grid.Coord> impassable, Collection<com.github.yellowstonegames.grid.Coord> onlyPassable, com.github.yellowstonegames.grid.Coord start, com.github.yellowstonegames.grid.Coord... targets)
    For pathfinding creatures larger than 1x1 cell; scans the dungeon using DijkstraMap.scan with the listed goals and start point, and returns a list of Coord positions (using the current measurement) needed to get closer to the closest reachable goal.
    com.github.tommyettinger.ds.ObjectDeque<com.github.yellowstonegames.grid.Coord>
    findPathPreScanned(com.github.tommyettinger.ds.ObjectDeque<com.github.yellowstonegames.grid.Coord> buffer, com.github.yellowstonegames.grid.Coord target)
    When you can control how often the (relatively time-intensive) scan() method is called, but may need simple paths very frequently (such as for a path that follows the mouse), you can use this method to reduce the amount of work needed to find paths.
    com.github.tommyettinger.ds.ObjectDeque<com.github.yellowstonegames.grid.Coord>
    findPathPreScanned(com.github.yellowstonegames.grid.Coord target)
    When you can control how often the (relatively time-intensive) scan() method is called, but may need simple paths very frequently (such as for a path that follows the mouse), you can use this method to reduce the amount of work needed to find paths.
    com.github.tommyettinger.ds.ObjectDeque<com.github.yellowstonegames.grid.Coord>
    findShortcutPath(com.github.yellowstonegames.grid.Coord start, com.github.yellowstonegames.grid.Coord... targets)
    If you have a target or group of targets you want to pathfind to without scanning the full map, this can be good.
    com.github.tommyettinger.ds.ObjectDeque<com.github.yellowstonegames.grid.Coord>
    findTechniquePath(int moveLength, Technique tech, float[][] dungeon, com.github.yellowstonegames.grid.LineDrawer los, Collection<com.github.yellowstonegames.grid.Coord> impassable, Collection<com.github.yellowstonegames.grid.Coord> allies, com.github.yellowstonegames.grid.Coord start, Collection<com.github.yellowstonegames.grid.Coord> targets)
    Scans the dungeon using DijkstraMap.scan with the listed goals and start point, and returns a list of Coord positions (using the current measurement) needed to get closer to a goal, where goals are considered valid if they are at a valid range for the given Technique to hit at least one target and ideal if that Technique can affect as many targets as possible from a cell that can be moved to with at most movelength steps.
    com.github.tommyettinger.ds.ObjectDeque<com.github.yellowstonegames.grid.Coord>
    findTechniquePath(com.github.tommyettinger.ds.ObjectDeque<com.github.yellowstonegames.grid.Coord> buffer, int moveLength, Technique tech, float[][] dungeon, com.github.yellowstonegames.grid.LineDrawer los, Collection<com.github.yellowstonegames.grid.Coord> impassable, Collection<com.github.yellowstonegames.grid.Coord> allies, com.github.yellowstonegames.grid.Coord start, Collection<com.github.yellowstonegames.grid.Coord> targets)
    Scans the dungeon using DijkstraMap.scan with the listed goals and start point, and returns a list of Coord positions (using the current measurement) needed to get closer to a goal, where goals are considered valid if they are at a valid range for the given Technique to hit at least one target and ideal if that Technique can affect as many targets as possible from a cell that can be moved to with at most movelength steps.
    com.github.yellowstonegames.grid.CoordFloatOrderedMap
    floodFill(int radius, com.github.yellowstonegames.grid.Coord... starts)
    A simple limited flood-fill that returns a OrderedMap of Coord keys to the float values in the DijkstraMap, only calculating out to a number of steps determined by limit.
    com.github.yellowstonegames.grid.CoordFloatOrderedMap
    floodFill(int radius, Iterable<com.github.yellowstonegames.grid.Coord> starts)
    A simple limited flood-fill that returns a OrderedMap of Coord keys to the float values in the DijkstraMap, only calculating out to a number of steps determined by limit.
    int
    getBlockingRequirement()
    If you want obstacles present in orthogonal cells to prevent pathfinding along the diagonal between them, this can be used to make thin diagonal walls non-viable to move through, or even to prevent diagonal movement if any one obstacle is orthogonally adjacent to both the start and target cell of a diagonal move.
    int
    getMappedCount()
     
    DijkstraMap
    initialize(char[][] level)
    Used to initialize or re-initialize a DijkstraMap that needs a new physicalMap because it either wasn't given one when it was constructed, or because the contents of the terrain have changed permanently (not if a creature moved; for that you pass the positions of creatures that block paths to scan() or findPath() ).
    DijkstraMap
    initialize(char[][] level, char alternateWall)
    Used to initialize or re-initialize a DijkstraMap that needs a new PhysicalMap because it either wasn't given one when it was constructed, or because the contents of the terrain have changed permanently (not if a creature moved; for that you pass the positions of creatures that block paths to scan() or findPath() ).
    DijkstraMap
    initialize(float[][] level)
    Used to initialize or re-initialize a DijkstraMap that needs a new physicalMap because it either wasn't given one when it was constructed, or because the contents of the terrain have changed permanently (not if a creature moved; for that you pass the positions of creatures that block paths to scan() or findPath() ).
    DijkstraMap
    initializeByResistance(float[][] level)
    Used to initialize or re-initialize a DijkstraMap that needs a new physicalMap because it either wasn't given one when it was constructed, or because the contents of the terrain have changed permanently (not if a creature moved; for that you pass the positions of creatures that block paths to scan() or findPath() ).
    DijkstraMap
    initializeCost(char[][] level)
    Used to initialize the entry cost modifiers for games that require variable costs to enter squares.
    DijkstraMap
    initializeCost(char[][] level, char alternateWall)
    Used to initialize the entry cost modifiers for games that require variable costs to enter squares.
    DijkstraMap
    initializeCost(float[][] costs)
    Used to initialize the entry cost modifiers for games that require variable costs to enter squares.
    float[][]
    partialScan(int limit)
    Recalculate the Dijkstra map up to a limit and return it.
    void
    partialScan(int limit, com.github.yellowstonegames.grid.Coord start, Iterable<com.github.yellowstonegames.grid.Coord> impassable, int size)
    Recalculate the Dijkstra map for a creature that is potentially larger than 1x1 cell and return it.
    float[][]
    partialScan(int limit, Iterable<com.github.yellowstonegames.grid.Coord> impassable)
    Recalculate the Dijkstra map up to a limit and return it.
    float[][]
    partialScan(int limit, Iterable<com.github.yellowstonegames.grid.Coord> impassable, int size)
    Recalculate the Dijkstra map for a creature that is potentially larger than 1x1 cell and return it.
    void
    partialScan(com.github.yellowstonegames.grid.Coord start, int limit, Iterable<com.github.yellowstonegames.grid.Coord> impassable)
    Recalculate the Dijkstra map up to a limit and return it.
    void
    partialScan(com.github.yellowstonegames.grid.Coord start, int limit, Iterable<com.github.yellowstonegames.grid.Coord> impassable, boolean nonZeroOptimum)
    Recalculate the Dijkstra map up to a limit and return it.
    void
    reset()
    Resets this DijkstraMap to a state with no goals, no discovered path, and no changes made to gradientMap relative to physicalMap.
    void
    resetCell(int x, int y)
    Reverts a cell to the value stored in the original state of the level as known by physicalMap.
    void
    resetCell(com.github.yellowstonegames.grid.Coord pt)
    Reverts a cell to the value stored in the original state of the level as known by physicalMap.
    void
    resetMap()
    Resets the gradientMap to its original value from physicalMap.
    void
    resetTargetMap()
    Resets the targetMap (which is only assigned in the first place if you use findTechniquePath() ).
    float[][]
    scan()
    Recalculate the Dijkstra map and return it.
    void
    scan(com.github.yellowstonegames.grid.Coord start, Iterable<com.github.yellowstonegames.grid.Coord> impassable)
    Recalculate the Dijkstra map and return it.
    void
    scan(com.github.yellowstonegames.grid.Coord start, Iterable<com.github.yellowstonegames.grid.Coord> impassable, boolean nonZeroOptimum)
    Recalculate the Dijkstra map and return it.
    void
    scan(com.github.yellowstonegames.grid.Coord start, Iterable<com.github.yellowstonegames.grid.Coord> impassable, int size)
    Recalculate the Dijkstra map for a creature that is potentially larger than 1x1 cell and return it.
    float[][]
    scan(Iterable<com.github.yellowstonegames.grid.Coord> impassable)
    Recalculate the Dijkstra map and return it.
    float[][]
    scan(Iterable<com.github.yellowstonegames.grid.Coord> impassable, int size)
    Recalculate the Dijkstra map for a creature that is potentially larger than 1x1 cell and return it.
    void
    setBlockingRequirement(int blockingRequirement)
    If you want obstacles present in orthogonal cells to prevent pathfinding along the diagonal between them, this can be used to make thin diagonal walls non-viable to move through, or even to prevent diagonal movement if any one obstacle is orthogonally adjacent to both the start and target cell of a diagonal move.
    void
    setCost(int x, int y, float cost)
    Marks a cell's cost for pathfinding as cost, unless the cell is a wall or unreachable area (then it always sets the cost to the value of the WALL field).
    void
    setCost(com.github.yellowstonegames.grid.Coord pt, float cost)
    Marks a cell's cost for pathfinding as cost, unless the cell is a wall or unreachable area (then it always sets the cost to the value of the WALL field).
    void
    setGoal(int x, int y)
    Marks a cell as a goal for pathfinding, unless the cell is a wall or unreachable area (then it does nothing).
    void
    setGoal(com.github.yellowstonegames.grid.Coord pt)
    Marks a cell as a goal for pathfinding, unless the cell is a wall or unreachable area (then it does nothing).
    void
    setGoals(com.github.yellowstonegames.grid.Coord[] pts)
    Marks many cells as goals for pathfinding, ignoring cells in walls or unreachable areas.
    void
    setGoals(com.github.yellowstonegames.grid.Region pts)
    Marks many cells as goals for pathfinding, ignoring cells in walls or unreachable areas.
    void
    setGoals(Iterable<com.github.yellowstonegames.grid.Coord> pts)
    Marks many cells as goals for pathfinding, ignoring cells in walls or unreachable areas.
    void
    setOccupied(int x, int y)
    Marks a specific cell in gradientMap as completely impossible to enter.

    Methods inherited from class Object

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

  • Field Details

    • GOAL

      public static final float GOAL
      Goals are by default marked with 0f. Some situations may have positions with lower values that are especially urgent to move towards.
      See Also:

    • FLOOR

      public static final float FLOOR
      Floor cells, which include any walkable cell, are marked with a high number equal to 999200f .
      See Also:

    • WALL

      public static final float WALL
      Walls, which are solid no-entry cells, are marked with a high number equal to 999500f .
      See Also:

    • DARK

      public static final float DARK
      This is used to mark cells that the scan couldn't reach, and these dark cells are marked with a high number equal to 999800f .
      See Also:

    • measurement

      public com.github.yellowstonegames.grid.Measurement measurement
      This affects how distance is measured on diagonal directions vs. orthogonal directions. MANHATTAN should form a diamond shape on a featureless map, while CHEBYSHEV and EUCLIDEAN will form a square. EUCLIDEAN does not affect the length of paths, though it will change the DijkstraMap's gradientMap to have many non-integer values, and that in turn will make paths this finds much more realistic and smooth (favoring orthogonal directions unless a diagonal one is a better option).

    • physicalMap

      public float[][] physicalMap
      Stores which parts of the map are accessible and which are not. Should not be changed unless the actual physical terrain has changed. You should call initialize() with a new map instead of changing this directly.

    • gradientMap

      public float[][] gradientMap
      The frequently-changing values that are often the point of using this class; goals will have a value of 0, and any cells that can have a character reach a goal in n steps will have a value of n. Cells that cannot be entered because they are solid will have a very high value equal to the WALL constant in this class, and cells that cannot be entered because they cannot reach a goal will have a different very high value equal to the DARK constant in this class.

    • costMap

      public float[][] costMap
      This stores the entry cost multipliers for each cell; that is, a value of 1f is a normal, unmodified cell, but a value of 0.5f can be entered easily (two cells of its cost can be entered for the cost of one 1f cell), and a value of 2f can only be entered with difficulty (one cell of its cost can be entered for the cost of two 1f cells). Unlike the measurement field, this does affect the length of paths, as well as the numbers assigned to gradientMap during a scan. The values for walls are identical to the value used by gradientMap, that is, this class' WALL static final field. Floors, however, are never given FLOOR as a value, and default to 1f .

    • standardCosts

      public boolean standardCosts

    • height

      public int height
      Height of the map. Exciting stuff. Don't change this, instead call initialize().

    • width

      public int width
      Width of the map. Exciting stuff. Don't change this, instead call initialize().

    • path

      public com.github.tommyettinger.ds.ObjectDeque<com.github.yellowstonegames.grid.Coord> path
      The latest path that was obtained by calling findPath(). It will not contain the value passed as a starting cell; only steps that require movement will be included, and so if the path has not been found or a valid path toward a goal is impossible, this ObjectDeque will be empty.

    • cutShort

      public boolean cutShort

    • goals

      protected com.github.tommyettinger.ds.IntList goals
      Goals that pathfinding will seek out. Each item is an encoded point, as done by encode(int, int).

    • fresh

      protected com.github.tommyettinger.ds.IntDeque fresh
      Working data used during scanning, this tracks the perimeter of the scanned area so far. This is a member variable and not a local one to avoid reallocating the data structure. Each item is an encoded point, as done by encode(int, int).

    • rng

      protected com.github.tommyettinger.random.FlowRandom rng
      The FlowRandom used to decide which one of multiple equally-short paths to take; this has its state set deterministically before any usage. There will only be one path produced for a given set of parameters, and it will be returned again and again if the same parameters are requested.

    • targetMap

      public com.github.yellowstonegames.grid.Coord[][] targetMap

  • Constructor Details

    • DijkstraMap

      public DijkstraMap()
      Construct a DijkstraMap without a level to actually scan. If you use this constructor, you must call an initialize() method before using this class.

    • DijkstraMap

      public DijkstraMap(float[][] level)
      Used to construct a DijkstraMap from the output of another.
      Parameters:
      level -

    • DijkstraMap

      public DijkstraMap(float[][] level, com.github.yellowstonegames.grid.Measurement measurement)
      Used to construct a DijkstraMap from the output of another, specifying a distance calculation.
      Parameters:
      level -
      measurement -

    • DijkstraMap

      public DijkstraMap(float[][] level, com.github.yellowstonegames.grid.Measurement measurement, boolean levelIsResistanceMap)
      Used to construct a DijkstraMap from either the output of another DijkstraMap, or from a resistance map of the type used by FOV. ALso specifies a distance calculation.
      Parameters:
      level - a 2D float array that either was produced by scan() or is a resistance map, depending on the last parameter
      measurement - the distance calculation to use
      levelIsResistanceMap - if true, level will be treated as a resistance map; if false, the output of another DijkstraMap

    • DijkstraMap

      public DijkstraMap(char[][] level)
      Constructor meant to take a char[][] returned by DungeonBoneGen.generate(), or any other char[][] where '#' means a wall and anything else is a walkable tile. If you only have a map that uses box-drawing characters, use DungeonUtility.linesToHashes() to get a map that can be used here. This uses Measurement.MANHATTAN, allowing only 4-way movement.
      Parameters:
      level -

    • DijkstraMap

      public DijkstraMap(char[][] level, char alternateWall)
      Constructor meant to take a char[][] returned by DungeonBoneGen.generate(), or any other char[][] where one char means a wall and anything else is a walkable tile. If you only have a map that uses box-drawing characters, use DungeonUtility.linesToHashes() to get a map that can be used here. You can specify the character used for walls. This uses Measurement.MANHATTAN, allowing only 4-way movement.
      Parameters:
      level -

    • DijkstraMap

      public DijkstraMap(char[][] level, com.github.yellowstonegames.grid.Measurement measurement)
      Constructor meant to take a char[][] returned by DungeonBoneGen.generate(), or any other char[][] where '#' means a wall and anything else is a walkable tile. If you only have a map that uses box-drawing characters, use DungeonUtility.linesToHashes() to get a map that can be used here. Also takes a distance measurement, which you may want to set to Measurement.CHEBYSHEV for unpredictable 8-way movement or Measurement.EUCLIDEAN for more reasonable 8-way movement that prefers straight lines.
      Parameters:
      level - a char[x][y] map where '#' is a wall, and anything else is walkable
      measurement - how this should measure orthogonal vs. diagonal measurement, such as Measurement.MANHATTAN for 4-way only movement

  • Method Details

    • initialize

      public DijkstraMap initialize(float[][] level)
      Used to initialize or re-initialize a DijkstraMap that needs a new physicalMap because it either wasn't given one when it was constructed, or because the contents of the terrain have changed permanently (not if a creature moved; for that you pass the positions of creatures that block paths to scan() or findPath() ).
      Parameters:
      level - a 2D float array that should be used as the physicalMap for this DijkstraMap
      Returns:
      this for chaining

    • initialize

      public DijkstraMap initialize(char[][] level)
      Used to initialize or re-initialize a DijkstraMap that needs a new physicalMap because it either wasn't given one when it was constructed, or because the contents of the terrain have changed permanently (not if a creature moved; for that you pass the positions of creatures that block paths to scan() or findPath() ).
      Parameters:
      level - a 2D char array that this will use to establish which cells are walls ('#' as wall, others as floor)
      Returns:
      this for chaining

    • initialize

      public DijkstraMap initialize(char[][] level, char alternateWall)
      Used to initialize or re-initialize a DijkstraMap that needs a new PhysicalMap because it either wasn't given one when it was constructed, or because the contents of the terrain have changed permanently (not if a creature moved; for that you pass the positions of creatures that block paths to scan() or findPath() ). This initialize() method allows you to specify an alternate wall char other than the default character, '#' .
      Parameters:
      level - a 2D char array that this will use to establish which cells are walls (alternateWall defines the wall char, everything else is floor)
      alternateWall - the char to consider a wall when it appears in level
      Returns:
      this for chaining

    • initializeByResistance

      public DijkstraMap initializeByResistance(float[][] level)
      Used to initialize or re-initialize a DijkstraMap that needs a new physicalMap because it either wasn't given one when it was constructed, or because the contents of the terrain have changed permanently (not if a creature moved; for that you pass the positions of creatures that block paths to scan() or findPath() ). This version takes a 2D float array that represents a resistance map, as is used by FOV and BresenhamLine. A resistance map has walls and other impassable cells use 1.0 or higher for their value, and fully passable cells use 0.0 for their value.
      Parameters:
      level - a 2D float array that should be used as the physicalMap for this DijkstraMap
      Returns:
      this for chaining

    • initializeCost

      public DijkstraMap initializeCost(char[][] level)
      Used to initialize the entry cost modifiers for games that require variable costs to enter squares. This expects a char[][] of the same exact dimensions as the 2D array that was used to previously initialize() this DijkstraMap, treating the '#' char as a wall (impassable) and anything else as having a normal cost to enter. The costs can be accessed later by using costMap directly (which will have a valid value when this does not throw an exception), or by calling setCost().
      Parameters:
      level - a 2D char array that uses '#' for walls
      Returns:
      this DijkstraMap for chaining.

    • initializeCost

      public DijkstraMap initializeCost(char[][] level, char alternateWall)
      Used to initialize the entry cost modifiers for games that require variable costs to enter squares. This expects a char[][] of the same exact dimensions as the 2D array that was used to previously initialize() this DijkstraMap, treating the '#' char as a wall (impassable) and anything else as having a normal cost to enter. The costs can be accessed later by using costMap directly (which will have a valid value when this does not throw an exception), or by calling setCost().

      This method allows you to specify an alternate wall char other than the default character, '#' .

      Parameters:
      level - a 2D char array that uses alternateChar for walls.
      alternateWall - a char to use to represent walls.
      Returns:
      this DijkstraMap for chaining.

    • initializeCost

      public DijkstraMap initializeCost(float[][] costs)
      Used to initialize the entry cost modifiers for games that require variable costs to enter squares. This expects a float[][] of the same exact dimensions as the 2D array that was used to previously initialize() this DijkstraMap, using the exact values given in costs as the values to enter cells, even if they aren't what this class would assign normally -- walls and other impassable values should be given WALL as a value, however. The costs can be accessed later by using costMap directly (which will have a valid value when this does not throw an exception), or by calling setCost(). Causes findPath() to always explore the full map instead of stopping as soon as it finds any path, since unequal costs could make some paths cost less but be discovered later in the pathfinding process.

      This method should be slightly more efficient than the other initializeCost methods.

      Parameters:
      costs - a 2D float array that already has the desired cost values
      Returns:
      this DijkstraMap for chaining.

    • encode

      public int encode(com.github.yellowstonegames.grid.Coord point)
      Internally, DijkstraMap uses int primitives instead of Coord objects. This method converts from a Coord to an encoded int that stores the same information, but is somewhat more efficient to work with.
      Parameters:
      point - a Coord to find an encoded int for
      Returns:
      an int that encodes the given Coord

    • encode

      public int encode(int x, int y)
      Internally, DijkstraMap uses int primitives instead of Coord objects. This method converts from an x,y point to an encoded int that stores the same information, but is somewhat more efficient to work with.
      Parameters:
      x - the x component of the point to find an encoded int for
      y - the y component of the point to find an encoded int for
      Returns:
      an int that encodes the given x,y point

    • decode

      public com.github.yellowstonegames.grid.Coord decode(int encoded)
      If you for some reason have one of the internally-used ints produced by encode(Coord), this will convert it back to a Coord if you need it as such. You may prefer using decodeX(int) and decodeY(int) to get the x and y components independently and without involving objects.
      Parameters:
      encoded - an encoded int specific to this DijkstraMap's height and width; see encode(Coord)
      Returns:
      the Coord that represents the same x,y position that the given encoded int stores

    • decodeX

      public int decodeX(int encoded)
      If you for some reason have one of the internally-used ints produced by encode(Coord), this will decode the x component of the point encoded in that int. This is an extremely simple method that is equivalent to the code encoded & 0xFFFF. You probably would use this method in conjunction with decodeY(int), or would instead use decode(int) to get a Coord.
      Parameters:
      encoded - an encoded int; see encode(Coord)
      Returns:
      the x component of the position that the given encoded int stores

    • decodeY

      public int decodeY(int encoded)
      If you for some reason have one of the internally-used ints produced by encode(Coord), this will decode the y component of the point encoded in that int. This is an extremely simple method that is equivalent to the code encoded >>> 16. You probably would use this method in conjunction with decodeX(int), or would instead use decode(int) to get a Coord.
      Parameters:
      encoded - an encoded int; see encode(Coord)
      Returns:
      the y component of the position that the given encoded int stores

    • resetMap

      public void resetMap()
      Resets the gradientMap to its original value from physicalMap.

    • resetTargetMap

      public void resetTargetMap()
      Resets the targetMap (which is only assigned in the first place if you use findTechniquePath() ).

    • reset

      public void reset()
      Resets this DijkstraMap to a state with no goals, no discovered path, and no changes made to gradientMap relative to physicalMap.

    • setGoal

      public void setGoal(int x, int y)
      Marks a cell as a goal for pathfinding, unless the cell is a wall or unreachable area (then it does nothing).
      Parameters:
      x -
      y -

    • setGoal

      public void setGoal(com.github.yellowstonegames.grid.Coord pt)
      Marks a cell as a goal for pathfinding, unless the cell is a wall or unreachable area (then it does nothing).
      Parameters:
      pt -

    • setGoals

      public void setGoals(com.github.yellowstonegames.grid.Region pts)
      Marks many cells as goals for pathfinding, ignoring cells in walls or unreachable areas. Possibly more efficient than a loop that calls setGoal(Coord) over and over, since this doesn't need to do a bounds check. The Region passed to this should have the same (or smaller) width and height as this DijkstraMap.
      Parameters:
      pts - a Region containing "on" cells to treat as goals; should have the same width and height as this

    • setGoals

      public void setGoals(Iterable<com.github.yellowstonegames.grid.Coord> pts)
      Marks many cells as goals for pathfinding, ignoring cells in walls or unreachable areas. Simply loops through pts and calls setGoal(Coord) on each Coord in pts. If you have a Region, you should use it with setGoals(Region), which is faster.
      Parameters:
      pts - any Iterable of Coord, which can be a List, Set, Queue, etc. of Coords to mark as goals

    • setGoals

      public void setGoals(com.github.yellowstonegames.grid.Coord[] pts)
      Marks many cells as goals for pathfinding, ignoring cells in walls or unreachable areas. Simply loops through pts and calls setGoal(Coord) on each Coord in pts.
      Parameters:
      pts - an array of Coord to mark as goals

    • setCost

      public void setCost(com.github.yellowstonegames.grid.Coord pt, float cost)
      Marks a cell's cost for pathfinding as cost, unless the cell is a wall or unreachable area (then it always sets the cost to the value of the WALL field).
      Parameters:
      pt -
      cost -

    • setCost

      public void setCost(int x, int y, float cost)
      Marks a cell's cost for pathfinding as cost, unless the cell is a wall or unreachable area (then it always sets the cost to the value of the WALL field).
      Parameters:
      x -
      y -
      cost -

    • setOccupied

      public void setOccupied(int x, int y)
      Marks a specific cell in gradientMap as completely impossible to enter.
      Parameters:
      x -
      y -

    • resetCell

      public void resetCell(int x, int y)
      Reverts a cell to the value stored in the original state of the level as known by physicalMap.
      Parameters:
      x -
      y -

    • resetCell

      public void resetCell(com.github.yellowstonegames.grid.Coord pt)
      Reverts a cell to the value stored in the original state of the level as known by physicalMap.
      Parameters:
      pt -

    • clearGoals

      public void clearGoals()
      Used to remove all goals and undo any changes to gradientMap made by having a goal present.

    • scan

      public float[][] scan()
      Recalculate the Dijkstra map and return it. Cells that were marked as goals with setGoal will have a value of 0, the cells adjacent to goals will have a value of 1, and cells progressively further from goals will have a value equal to the distance from the nearest goal. The exceptions are walls, which will have a value defined by the WALL constant in this class, and areas that the scan was unable to reach, which will have a value defined by the DARK constant in this class (typically, these areas should not be used to place NPCs or items and should be filled with walls). This uses the current measurement. The result is stored in the gradientMap field and a copy is returned.
      Returns:
      A 2D float[width][height] using the width and height of what this knows about the physical map.

    • scan

      public float[][] scan(Iterable<com.github.yellowstonegames.grid.Coord> impassable)
      Recalculate the Dijkstra map and return it. Cells that were marked as goals with setGoal will have a value of 0, the cells adjacent to goals will have a value of 1, and cells progressively further from goals will have a value equal to the distance from the nearest goal. The exceptions are walls, which will have a value defined by the WALL constant in this class, and areas that the scan was unable to reach, which will have a value defined by the DARK constant in this class (typically, these areas should not be used to place NPCs or items and should be filled with walls). This uses the current measurement. The result is stored in the gradientMap field and a copy is returned.
      Parameters:
      impassable - An Iterable of Coord keys representing the locations of enemies or other moving obstacles to a path that cannot be moved through; this can be null if there are no such obstacles.
      Returns:
      A 2D float[width][height] using the width and height of what this knows about the physical map.

    • scan

      public void scan(com.github.yellowstonegames.grid.Coord start, Iterable<com.github.yellowstonegames.grid.Coord> impassable)
      Recalculate the Dijkstra map and return it. Cells that were marked as goals with setGoal will have a value of 0, the cells adjacent to goals will have a value of 1, and cells progressively further from goals will have a value equal to the distance from the nearest goal. The exceptions are walls, which will have a value defined by the WALL constant in this class, and areas that the scan was unable to reach, which will have a value defined by the DARK constant in this class (typically, these areas should not be used to place NPCs or items and should be filled with walls). This uses the current measurement. The result is stored in the gradientMap field, and nothing is returned. If you want the data returned, you can use scan(Iterable) (which calls this method with null for the start parameter, then modifies the gradientMap field and returns a copy), or you can just retrieve the gradientMap (maybe copying it; ArrayTools.copy(float[][]) is a convenient option for copying a 2D float array). If start is non-null, which is usually used when finding a single path, then cells that didn't need to be explored (because they were further than the path needed to go from start to goal) will have the value FLOOR. You may wish to assign a different value to these cells in some cases (especially if start is null, which means any cells that are still FLOOR could not be reached from any goal), and the overloads of scan that return 2D float arrays do change FLOOR to DARK, which is usually treated similarly to WALL.
      Parameters:
      start - a Coord representing the location of the pathfinder; may be null, which has this scan the whole map
      impassable - An Iterable of Coord keys representing the locations of enemies or other moving obstacles to a path that cannot be moved through; this can be null if there are no such obstacles.

    • scan

      public void scan(com.github.yellowstonegames.grid.Coord start, Iterable<com.github.yellowstonegames.grid.Coord> impassable, boolean nonZeroOptimum)
      Recalculate the Dijkstra map and return it. Cells in gradientMap that had the lowest value will be treated as goals if nonZeroOptimum is true; otherwise, only cells marked as goals with setGoal(Coord) will be considered goals and some overhead will be saved. The cells adjacent to goals will have a value of 1, and cells progressively further from goals will have a value equal to the distance from the nearest goal. The exceptions are walls, which will have a value defined by the WALL constant in this class, and areas that the scan was unable to reach, which will have a value defined by the DARK constant in this class (typically, these areas should not be used to place NPCs or items and should be filled with walls). This uses the current measurement. The result is stored in the gradientMap field, and nothing is returned. If you want the data returned, you can use scan(Iterable) (which calls this method with null for the start parameter, then modifies the gradientMap field and returns a copy), or you can just retrieve the gradientMap (maybe copying it; ArrayTools.copy(float[][]) is a convenient option for copying a 2D float array). If start is non-null, which is usually used when finding a single path, then cells that didn't need to be explored (because they were further than the path needed to go from start to goal) will have the value FLOOR. You may wish to assign a different value to these cells in some cases (especially if start is null, which means any cells that are still FLOOR could not be reached from any goal), and the overloads of scan that return 2D float arrays do change FLOOR to DARK, which is usually treated similarly to WALL.
      Parameters:
      start - a Coord representing the location of the pathfinder; may be null, which has this scan the whole map
      impassable - An Iterable of Coord keys representing the locations of enemies or other moving obstacles to a path that cannot be moved through; this can be null if there are no such obstacles.
      nonZeroOptimum - if the cell to pathfind toward should have a value of GOAL (0f), this should be false; if it should have a different value or if you don't know, it should be true

    • partialScan

      public float[][] partialScan(int limit)
      Recalculate the Dijkstra map up to a limit and return it. Cells that were marked as goals with setGoal will have a value of 0, the cells adjacent to goals will have a value of 1, and cells progressively further from goals will have a value equal to the distance from the nearest goal. If a cell would take more steps to reach than the given limit, it will have a value of DARK if it was passable instead of the distance. The exceptions are walls, which will have a value defined by the WALL constant in this class, and areas that the scan was unable to reach, which will have a value defined by the DARK constant in this class. This uses the current measurement. The result is stored in the gradientMap field and a copy is returned.
      Parameters:
      limit - The maximum number of steps to scan outward from a goal.
      Returns:
      A 2D float[width][height] using the width and height of what this knows about the physical map.

    • partialScan

      public float[][] partialScan(int limit, Iterable<com.github.yellowstonegames.grid.Coord> impassable)
      Recalculate the Dijkstra map up to a limit and return it. Cells that were marked as goals with setGoal will have a value of 0, the cells adjacent to goals will have a value of 1, and cells progressively further from goals will have a value equal to the distance from the nearest goal. If a cell would take more steps to reach than the given limit, it will have a value of DARK if it was passable instead of the distance. The exceptions are walls, which will have a value defined by the WALL constant in this class, and areas that the scan was unable to reach, which will have a value defined by the DARK constant in this class. This uses the current measurement. The result is stored in the gradientMap field and a copy is returned.
      Parameters:
      limit - The maximum number of steps to scan outward from a goal.
      impassable - A Collection of Coord keys representing the locations of enemies or other moving obstacles to a path that cannot be moved through; this can be null if there are no such obstacles.
      Returns:
      A 2D float[width][height] using the width and height of what this knows about the physical map.

    • partialScan

      public void partialScan(com.github.yellowstonegames.grid.Coord start, int limit, Iterable<com.github.yellowstonegames.grid.Coord> impassable)
      Recalculate the Dijkstra map up to a limit and return it. Cells that were marked as goals with setGoal will have a value of 0, the cells adjacent to goals will have a value of 1, and cells progressively further from goals will have a value equal to the distance from the nearest goal. If a cell would take more steps to reach than the given limit, or if it was otherwise unreachable, it will have a value of FLOOR or greater if it was passable instead of the distance. The exceptions are walls, which will have a value defined by the WALL constant in this class. This uses the current measurement. The result is stored in the gradientMap field, and nothing is returned.If you want the data returned, you can use partialScan(int, Iterable) (which calls this method with null for the start parameter, then modifies the gradientMap field and returns a copy), or you can just retrieve the gradientMap (maybe copying it; ArrayTools.copy(float[][]) is a convenient option for copying a 2D float array).
      If start is non-null, which is usually used when finding a single path, then cells that didn't need to be explored (because they were further than the path needed to go from start to goal) will have the value FLOOR. You may wish to assign a different value to these cells in some cases (especially if start is null, which means any cells that are still FLOOR could not be reached from any goal), and the overloads of partialScan that return 2D float arrays do change FLOOR to DARK, which is usually treated similarly to WALL.
      Parameters:
      start - a Coord representing the location of the pathfinder; may be null to have this scan more of the map
      limit - The maximum number of steps to scan outward from a goal.
      impassable - An Iterable of Coord keys representing the locations of enemies or other moving obstacles to a path that cannot be moved through; this can be null if there are no such obstacles.

    • partialScan

      public void partialScan(com.github.yellowstonegames.grid.Coord start, int limit, Iterable<com.github.yellowstonegames.grid.Coord> impassable, boolean nonZeroOptimum)
      Recalculate the Dijkstra map up to a limit and return it. Cells in gradientMap that had the lowest value will be treated as goals if nonZeroOptimum is true; otherwise, only cells marked as goals with setGoal(Coord) will be considered goals and some overhead will be saved. If a cell would take more steps to reach than the given limit, or if it was otherwise unreachable, it will have a value of FLOOR or greater if it was passable instead of the distance. The exceptions are walls, which will have a value defined by the WALL constant in this class. This uses the current measurement. The result is stored in the gradientMap field, and nothing is returned.If you want the data returned, you can use partialScan(int, Iterable) (which calls this method with null for the start parameter, then modifies the gradientMap field and returns a copy), or you can just retrieve the gradientMap (maybe copying it; ArrayTools.copy(float[][]) is a convenient option for copying a 2D float array).
      If start is non-null, which is usually used when finding a single path, then cells that didn't need to be explored (because they were further than the path needed to go from start to goal) will have the value FLOOR. You may wish to assign a different value to these cells in some cases (especially if start is null, which means any cells that are still FLOOR could not be reached from any goal), and the overloads of partialScan that return 2D float arrays do change FLOOR to DARK, which is usually treated similarly to WALL.
      Parameters:
      start - a Coord representing the location of the pathfinder; may be null to have this scan more of the map
      limit - The maximum number of steps to scan outward from a goal.
      impassable - An Iterable of Coord keys representing the locations of enemies or other moving obstacles to a path that cannot be moved through; this can be null if there are no such obstacles.
      nonZeroOptimum - if the cell to pathfind toward should have a value of GOAL (0f), this should be false; if it should have a different value or if you don't know, it should be true

    • findNearest

      public com.github.yellowstonegames.grid.Coord findNearest(com.github.yellowstonegames.grid.Coord start, Collection<com.github.yellowstonegames.grid.Coord> targets)
      Recalculate the Dijkstra map until it reaches a Coord in targets, then returns the first target found. This uses the current measurement.
      Parameters:
      start - the cell to use as the origin for finding the nearest target
      targets - the Coords that this is trying to find; it will stop once it finds one
      Returns:
      the Coord that it found first.

    • findNearest

      public com.github.yellowstonegames.grid.Coord findNearest(com.github.yellowstonegames.grid.Coord start, com.github.yellowstonegames.grid.Coord... targets)
      Recalculate the Dijkstra map until it reaches a Coord in targets, then returns the first target found. This uses the current measurement.
      Parameters:
      start - the cell to use as the origin for finding the nearest target
      targets - the Coords that this is trying to find; it will stop once it finds one
      Returns:
      the Coord that it found first.

    • findShortcutPath

      public com.github.tommyettinger.ds.ObjectDeque<com.github.yellowstonegames.grid.Coord> findShortcutPath(com.github.yellowstonegames.grid.Coord start, com.github.yellowstonegames.grid.Coord... targets)
      If you have a target or group of targets you want to pathfind to without scanning the full map, this can be good. It may find sub-optimal paths in the presence of costs to move into cells. It is useful when you want to move in a straight line to a known nearby goal.
      Parameters:
      start - your starting location
      targets - an array or vararg of Coords to pathfind to the nearest of
      Returns:
      an ObjectDeque of Coord that goes from a cell adjacent to start and goes to one of the targets. Copy of path.

    • findNearestMultiple

      public com.github.tommyettinger.ds.ObjectDeque<com.github.yellowstonegames.grid.Coord> findNearestMultiple(com.github.yellowstonegames.grid.Coord start, int limit, Collection<com.github.yellowstonegames.grid.Coord> targets)
      Recalculate the Dijkstra map until it reaches a Coord in targets, then returns the first several targets found, up to limit or less if the map is fully searched without finding enough. This uses the current measurement.
      Parameters:
      start - the cell to use as the origin for finding the nearest targets
      limit - the maximum number of targets to find before returning
      targets - the Coords that this is trying to find; it will stop once it finds enough (based on limit)
      Returns:
      the Coords that it found first.

    • scan

      public float[][] scan(Iterable<com.github.yellowstonegames.grid.Coord> impassable, int size)
      Recalculate the Dijkstra map for a creature that is potentially larger than 1x1 cell and return it. The value of a cell in the returned Dijkstra map assumes that a creature is square, with a side length equal to the passed size, that its minimum-x, minimum-y cell is the starting cell, and that any cell with a distance number represents the distance for the creature's minimum-x, minimum-y cell to reach it. Cells that cannot be entered by the minimum-x, minimum-y cell because of sizing (such as a floor cell next to a maximum-x and/or maximum-y wall if size is > 1) will be marked as DARK. Cells that were marked as goals with setGoal will have a value of 0, the cells adjacent to goals will have a value of 1, and cells progressively further from goals will have a value equal to the distance from the nearest goal. The exceptions are walls, which will have a value defined by the WALL constant in this class, and areas that the scan was unable to reach, which will have a value defined by the DARK constant in this class. (typically, these areas should not be used to place NPCs or items and should be filled with walls). This uses the current measurement. The result is stored in the gradientMap field and a copy is returned.
      Parameters:
      impassable - An Iterable of Coord keys representing the locations of enemies or other moving obstacles to a path that cannot be moved through; this can be null if there are no such obstacles.
      size - The length of one side of a square creature using this to find a path, i.e. 2 for a 2x2 cell creature. Non-square creatures are not supported because turning is really hard.
      Returns:
      A 2D float[width][height] using the width and height of what this knows about the physical map.

    • scan

      public void scan(com.github.yellowstonegames.grid.Coord start, Iterable<com.github.yellowstonegames.grid.Coord> impassable, int size)
      Recalculate the Dijkstra map for a creature that is potentially larger than 1x1 cell and return it. The value of a cell in the returned Dijkstra map assumes that a creature is square, with a side length equal to the passed size, that its minimum-x, minimum-y cell is the starting cell, and that any cell with a distance number represents the distance for the creature's minimum-x, minimum-y cell to reach it. Cells that cannot be entered by the minimum-x, minimum-y cell because of sizing (such as a floor cell next to a maximum-x and/or maximum-y wall if size is > 1) will be marked as DARK. Cells that were marked as goals with setGoal will have a value of 0, the cells adjacent to goals will have a value of 1, and cells progressively further from goals will have a value equal to the distance from the nearest goal. The exceptions are walls, which will have a value defined by the WALL constant in this class, and areas that the scan was unable to reach, which will have a value defined by the DARK constant in this class. (typically, these areas should not be used to place NPCs or items and should be filled with walls). This uses the current measurement. The result is stored in the gradientMap field, and nothing is returned. If you want the data returned, you can use scan(Iterable, int) (which calls this method with null for the start parameter, then modifies the gradientMap field and returns a copy), or you can just retrieve the gradientMap (maybe copying it; ArrayTools.copy(float[][]) is a convenient option for copying a 2D float array). If start is non-null, which is usually used when finding a single path, then cells that didn't need to be explored (because they were further than the path needed to go from start to goal) will have the value FLOOR. You may wish to assign a different value to these cells in some cases (especially if start is null, which means any cells that are still FLOOR could not be reached from any goal), and the overloads of scan that return 2D float arrays do change FLOOR to DARK, which is usually treated similarly to WALL.
      Parameters:
      impassable - An Iterable of Coord keys representing the locations of enemies or other moving obstacles to a path that cannot be moved through; this can be null if there are no such obstacles.
      size - The length of one side of a square creature using this to find a path, i.e. 2 for a 2x2 cell creature. Non-square creatures are not supported because turning is really hard.

    • partialScan

      public float[][] partialScan(int limit, Iterable<com.github.yellowstonegames.grid.Coord> impassable, int size)
      Recalculate the Dijkstra map for a creature that is potentially larger than 1x1 cell and return it. The value of a cell in the returned Dijkstra map assumes that a creature is square, with a side length equal to the passed size, that its minimum-x, minimum-y cell is the starting cell, and that any cell with a distance number represents the distance for the creature's minimum-x, minimum-y cell to reach it. Cells that cannot be entered by the minimum-x, minimum-y cell because of sizing (such as a floor cell next to a maximum-x and/or maximum-y wall if size is > 1) will be marked as DARK. Cells that were marked as goals with setGoal will have a value of 0, the cells adjacent to goals will have a value of 1, and cells progressively further from goals will have a value equal to the distance from the nearest goal. The exceptions are walls, which will have a value defined by the WALL constant in this class, and areas that the scan was unable to reach, which will have a value defined by the DARK constant in this class. (typically, these areas should not be used to place NPCs or items and should be filled with walls). This uses the current measurement. The result is stored in the gradientMap field and a copy is returned.
      Parameters:
      impassable - An Iterable of Coord keys representing the locations of enemies or other moving obstacles to a path that cannot be moved through; this can be null if there are no such obstacles.
      size - The length of one side of a square creature using this to find a path, i.e. 2 for a 2x2 cell creature. Non-square creatures are not supported because turning is really hard.
      Returns:
      A 2D float[width][height] using the width and height of what this knows about the physical map.

    • partialScan

      public void partialScan(int limit, com.github.yellowstonegames.grid.Coord start, Iterable<com.github.yellowstonegames.grid.Coord> impassable, int size)
      Recalculate the Dijkstra map for a creature that is potentially larger than 1x1 cell and return it. The value of a cell in the returned Dijkstra map assumes that a creature is square, with a side length equal to the passed size, that its minimum-x, minimum-y cell is the starting cell, and that any cell with a distance number represents the distance for the creature's minimum-x, minimum-y cell to reach it. Cells that cannot be entered by the minimum-x, minimum-y cell because of sizing (such as a floor cell next to a maximum-x and/or maximum-y wall if size is > 1) will be marked as DARK. Cells that were marked as goals with setGoal will have a value of 0, the cells adjacent to goals will have a value of 1, and cells progressively further from goals will have a value equal to the distance from the nearest goal. The exceptions are walls, which will have a value defined by the WALL constant in this class, and areas that the scan was unable to reach, which will have a value defined by the DARK constant in this class. (typically, these areas should not be used to place NPCs or items and should be filled with walls). This uses the current measurement. The result is stored in the gradientMap field, and nothing is returned. If you want the data returned, you can use partialScan(int, Iterable, int) (which calls this method with null for the start parameter, then modifies the gradientMap field and returns a copy), or you can just retrieve the gradientMap (maybe copying it; ArrayTools.copy(float[][]) is a convenient option for copying a 2D float array). If start is non-null, which is usually used when finding a single path, then cells that didn't need to be explored (because they were further than the path needed to go from start to goal) will have the value FLOOR. You may wish to assign a different value to these cells in some cases (especially if start is null, which means any cells that are still FLOOR could not be reached from any goal), and the overloads of partialScan that return 2D float arrays do change FLOOR to DARK, which is usually treated similarly to WALL.
      Parameters:
      impassable - An Iterable of Coord keys representing the locations of enemies or other moving obstacles to a path that cannot be moved through; this can be null if there are no such obstacles.
      size - The length of one side of a square creature using this to find a path, i.e. 2 for a 2x2 cell creature. Non-square creatures are not supported because turning is really hard.

    • findPath

      public com.github.tommyettinger.ds.ObjectDeque<com.github.yellowstonegames.grid.Coord> findPath(int length, Collection<com.github.yellowstonegames.grid.Coord> impassable, Collection<com.github.yellowstonegames.grid.Coord> onlyPassable, com.github.yellowstonegames.grid.Coord start, com.github.yellowstonegames.grid.Coord... targets)
      Scans the dungeon using DijkstraMap.scan with the listed goals and start point, and returns a list of Coord positions (using the current measurement) needed to get closer to the closest reachable goal. The maximum length of the returned list is given by length, which represents movement in a system where a single move can be multiple cells if length is greater than 1 and should usually be 1 in standard roguelikes; if moving the full length of the list would place the mover in a position shared by one of the positions in onlyPassable (which is typically filled with friendly units that can be passed through in multi-cell-movement scenarios), it will recalculate a move so that it does not pass into that cell. The keys in impassable should be the positions of enemies and obstacles that cannot be moved through, and will be ignored if there is a goal overlapping one. This overload always scans the whole map; use findPath(int, int, Collection, Collection, Coord, Coord...) to scan a smaller area for performance reasons.
      This caches its result in a member field, path, which can be fetched after finding a path and will change with each call to a pathfinding method.
      Parameters:
      length - the length of the path to calculate
      impassable - a Set of impassable Coord positions that may change (not constant like walls); can be null
      onlyPassable - a Set of Coord positions that this pathfinder cannot end a path occupying (typically allies); can be null
      start - the start of the path, should correspond to the minimum-x, minimum-y position of the pathfinder
      targets - a vararg or array of Coord that this will try to pathfind toward
      Returns:
      an ObjectDeque of Coord that will contain the locations of this creature as it goes toward a target. Copy of path.

    • findPath

      public com.github.tommyettinger.ds.ObjectDeque<com.github.yellowstonegames.grid.Coord> findPath(int length, int scanLimit, Collection<com.github.yellowstonegames.grid.Coord> impassable, Collection<com.github.yellowstonegames.grid.Coord> onlyPassable, com.github.yellowstonegames.grid.Coord start, com.github.yellowstonegames.grid.Coord... targets)
      Scans the dungeon using DijkstraMap.scan or DijkstraMap.partialScan with the listed goals and start point, and returns a list of Coord positions (using the current measurement) needed to get closer to the closest reachable goal. The maximum length of the returned list is given by length, which represents movement in a system where a single move can be multiple cells if length is greater than 1 and should usually be 1 in standard roguelikes; if moving the full length of the list would place the mover in a position shared by one of the positions in onlyPassable (which is typically filled with friendly units that can be passed through in multi-cell-movement scenarios), it will recalculate a move so that it does not pass into that cell. The keys in impassable should be the positions of enemies and obstacles that cannot be moved through, and will be ignored if there is a goal overlapping one. The full map will only be scanned if scanLimit is 0 or less; for positive scanLimit values this will scan only that distance out from each goal, which can save processing time on maps where only a small part matters. Generally, scanLimit should be significantly greater than length.
      This caches its result in a member field, path, which can be fetched after finding a path and will change with each call to a pathfinding method.
      Parameters:
      length - the length of the path to calculate
      scanLimit - how many cells away from a goal to actually process; negative to process whole map
      impassable - a Set of impassable Coord positions that may change (not constant like walls); can be null
      onlyPassable - a Set of Coord positions that this pathfinder cannot end a path occupying (typically allies); can be null
      start - the start of the path, should correspond to the minimum-x, minimum-y position of the pathfinder
      targets - a vararg or array of Coord that this will try to pathfind toward
      Returns:
      an ObjectDeque of Coord that will contain the locations of this creature as it goes toward a target. Copy of path.

    • findPath

      public com.github.tommyettinger.ds.ObjectDeque<com.github.yellowstonegames.grid.Coord> findPath(com.github.tommyettinger.ds.ObjectDeque<com.github.yellowstonegames.grid.Coord> buffer, int length, int scanLimit, Collection<com.github.yellowstonegames.grid.Coord> impassable, Collection<com.github.yellowstonegames.grid.Coord> onlyPassable, com.github.yellowstonegames.grid.Coord start, com.github.yellowstonegames.grid.Coord... targets)
      Scans the dungeon using DijkstraMap.scan or DijkstraMap.partialScan with the listed goals and start point, and returns a list of Coord positions (using the current measurement) needed to get closer to the closest reachable goal. The maximum length of the returned list is given by length, which represents movement in a system where a single move can be multiple cells if length is greater than 1 and should usually be 1 in standard roguelikes; if moving the full length of the list would place the mover in a position shared by one of the positions in onlyPassable (which is typically filled with friendly units that can be passed through in multi-cell-movement scenarios), it will recalculate a move so that it does not pass into that cell. The keys in impassable should be the positions of enemies and obstacles that cannot be moved through, and will be ignored if there is a goal overlapping one. The full map will only be scanned if scanLimit is 0 or less; for positive scanLimit values this will scan only that distance out from each goal, which can save processing time on maps where only a small part matters. Generally, scanLimit should be significantly greater than length.
      This overload takes a buffer parameter, an ObjectDeque of Coord, that the results will be appended to. If the buffer is null, a new ObjectDeque will be made and appended to. This caches its result in a member field, path, which can be fetched after finding a path and will change with each call to a pathfinding method. Any existing contents of buffer will not affect the path field of this DijkstraMap.
      Parameters:
      buffer - an existing ObjectDeque of Coord that will have the result appended to it (in-place); if null, this will make a new ObjectDeque
      length - the length of the path to calculate
      scanLimit - how many cells away from a goal to actually process; negative to process whole map
      impassable - a Set of impassable Coord positions that may change (not constant like walls); can be null
      onlyPassable - a Set of Coord positions that this pathfinder cannot end a path occupying (typically allies); can be null
      start - the start of the path, should correspond to the minimum-x, minimum-y position of the pathfinder
      targets - a vararg or array of Coord that this will try to pathfind toward
      Returns:
      an ObjectDeque of Coord that will contain the locations of this creature as it goes toward a target. Copy of path.

    • findAttackPath

      public com.github.tommyettinger.ds.ObjectDeque<com.github.yellowstonegames.grid.Coord> findAttackPath(int moveLength, int preferredRange, com.github.yellowstonegames.grid.LineDrawer los, Collection<com.github.yellowstonegames.grid.Coord> impassable, Collection<com.github.yellowstonegames.grid.Coord> onlyPassable, com.github.yellowstonegames.grid.Coord start, com.github.yellowstonegames.grid.Coord... targets)
      Scans the dungeon using DijkstraMap.scan with the listed goals and start point, and returns a list of Coord positions (using the current measurement) needed to get closer to a goal, until preferredRange is reached, or further from a goal if the preferredRange has not been met at the current distance. The maximum length of the returned list is given by moveLength; if moving the full length of the list would place the mover in a position shared by one of the positions in onlyPassable (which is typically filled with friendly units that can be passed through in multi-tile- movement scenarios), it will recalculate a move so that it does not pass into that cell. The keys in impassable should be the positions of enemies and obstacles that cannot be moved through, and will be ignored if there is a goal overlapping one.
      This caches its result in a member field, path, which can be fetched after finding a path and will change with each call to a pathfinding method.
      Parameters:
      moveLength - the length of the path to calculate
      preferredRange - the distance this unit will try to keep from a target
      los - a BresenhamLine, OrthoLine, or other LineDrawer if the preferredRange should try to stay in line of sight, or null if LoS should be disregarded.
      impassable - a Set of impassable Coord positions that may change (not constant like walls); can be null
      onlyPassable - a Set of Coord positions that this pathfinder cannot end a path occupying (typically allies); can be null
      start - the start of the path, should correspond to the minimum-x, minimum-y position of the pathfinder
      targets - a vararg or array of Coord that this will try to pathfind toward
      Returns:
      an ObjectDeque of Coord that will contain the locations of this creature as it goes toward a target. Copy of path.

    • findAttackPath

      public com.github.tommyettinger.ds.ObjectDeque<com.github.yellowstonegames.grid.Coord> findAttackPath(int moveLength, int minPreferredRange, int maxPreferredRange, com.github.yellowstonegames.grid.LineDrawer los, Collection<com.github.yellowstonegames.grid.Coord> impassable, Collection<com.github.yellowstonegames.grid.Coord> onlyPassable, com.github.yellowstonegames.grid.Coord start, com.github.yellowstonegames.grid.Coord... targets)
      Scans the dungeon using DijkstraMap.scan with the listed goals and start point, and returns a list of Coord positions (using the current measurement) needed to get closer to a goal, until a cell is reached with a distance from a goal that is at least equal to minPreferredRange and no more than maxPreferredRange, which may go further from a goal if the minPreferredRange has not been met at the current distance. The maximum length of the returned list is given by moveLength; if moving the full length of the list would place the mover in a position shared by one of the positions in onlyPassable (which is typically filled with friendly units that can be passed through in multi-tile- movement scenarios), it will recalculate a move so that it does not pass into that cell. The keys in impassable should be the positions of enemies and obstacles that cannot be moved through, and will be ignored if there is a goal overlapping one.
      This caches its result in a member field, path, which can be fetched after finding a path and will change with each call to a pathfinding method.
      Parameters:
      moveLength - the length of the path to calculate
      minPreferredRange - the (inclusive) lower bound of the distance this unit will try to keep from a target
      maxPreferredRange - the (inclusive) upper bound of the distance this unit will try to keep from a target
      los - a BresenhamLine, OrthoLine, or other LineDrawer if the preferredRange should try to stay in line of sight, or null if LoS should be disregarded.
      impassable - a Set of impassable Coord positions that may change (not constant like walls); can be null
      onlyPassable - a Set of Coord positions that this pathfinder cannot end a path occupying (typically allies); can be null
      start - the start of the path, should correspond to the minimum-x, minimum-y position of the pathfinder
      targets - a vararg or array of Coord that this will try to pathfind toward
      Returns:
      an ObjectDeque of Coord that will contain the locations of this creature as it goes toward a target. Copy of path.

    • findAttackPath

      public com.github.tommyettinger.ds.ObjectDeque<com.github.yellowstonegames.grid.Coord> findAttackPath(com.github.tommyettinger.ds.ObjectDeque<com.github.yellowstonegames.grid.Coord> buffer, int moveLength, int minPreferredRange, int maxPreferredRange, com.github.yellowstonegames.grid.LineDrawer los, Collection<com.github.yellowstonegames.grid.Coord> impassable, Collection<com.github.yellowstonegames.grid.Coord> onlyPassable, com.github.yellowstonegames.grid.Coord start, com.github.yellowstonegames.grid.Coord... targets)
      Scans the dungeon using DijkstraMap.scan with the listed goals and start point, and returns a list of Coord positions (using the current measurement) needed to get closer to a goal, until a cell is reached with a distance from a goal that is at least equal to minPreferredRange and no more than maxPreferredRange, which may go further from a goal if the minPreferredRange has not been met at the current distance. The maximum length of the returned list is given by moveLength; if moving the full length of the list would place the mover in a position shared by one of the positions in onlyPassable (which is typically filled with friendly units that can be passed through in multi-tile- movement scenarios), it will recalculate a move so that it does not pass into that cell. In most roguelikes where movement happens one cell at a time, moveLength should be 1; if it is higher then the path will prefer getting further away from the target (using up most or all of moveLength) while minPreferredRange and maxPreferredRange can be satisfied. This does ensure a pathfinder with a ranged weapon stays far from melee range, but it may not be the expected behavior because it will try to find the best path rather than the shortest it can attack from. The keys in impassable should be the positions of enemies and obstacles that cannot be moved through, and will be ignored if there is a goal overlapping one.
      This overload takes a buffer parameter, an ObjectDeque of Coord, that the results will be appended to. If the buffer is null, a new ObjectDeque will be made and appended to. This caches its result in a member field, path, which can be fetched after finding a path and will change with each call to a pathfinding method. Any existing contents of buffer will not affect the path field of this DijkstraMap.
      Parameters:
      buffer - an existing ObjectDeque of Coord that will have the result appended to it (in-place); if null, this will make a new ObjectDeque
      moveLength - the length of the path to calculate; almost always, the pathfinder will try to use this length in full to obtain the best range
      minPreferredRange - the (inclusive) lower bound of the distance this unit will try to keep from a target
      maxPreferredRange - the (inclusive) upper bound of the distance this unit will try to keep from a target
      los - a BresenhamLine, OrthoLine, or other LineDrawer if the preferredRange should try to stay in line of sight, or null if LoS should be disregarded.
      impassable - a Set of impassable Coord positions that may change (not constant like walls); can be null
      onlyPassable - a Set of Coord positions that this pathfinder cannot end a path occupying (typically allies); can be null
      start - the start of the path, should correspond to the minimum-x, minimum-y position of the pathfinder
      targets - a vararg or array of Coord that this will try to pathfind toward
      Returns:
      an ObjectDeque of Coord that will contain the locations of this creature as it goes toward a target. Copy of path.

    • findTechniquePath

      public com.github.tommyettinger.ds.ObjectDeque<com.github.yellowstonegames.grid.Coord> findTechniquePath(int moveLength, Technique tech, float[][] dungeon, com.github.yellowstonegames.grid.LineDrawer los, Collection<com.github.yellowstonegames.grid.Coord> impassable, Collection<com.github.yellowstonegames.grid.Coord> allies, com.github.yellowstonegames.grid.Coord start, Collection<com.github.yellowstonegames.grid.Coord> targets)
      Scans the dungeon using DijkstraMap.scan with the listed goals and start point, and returns a list of Coord positions (using the current measurement) needed to get closer to a goal, where goals are considered valid if they are at a valid range for the given Technique to hit at least one target and ideal if that Technique can affect as many targets as possible from a cell that can be moved to with at most movelength steps.
      The return value of this method is the path to get to a location to attack, but on its own it does not tell the user how to perform the attack. It does set the targetMap 2D Coord array field so that if your position at the end of the returned path is non-null in targetMap, it will be a Coord that can be used as a target position for Technique.apply() . If your position at the end of the returned path is null, then an ideal attack position was not reachable by the path.
      This needs a char[][] dungeon as an argument because DijkstraMap does not always have a char[][] version of the map available to it, and certain AOE implementations that a Technique uses may need a char[][] specifically to determine what they affect.
      The maximum length of the returned list is given by moveLength; if moving the full length of the list would place the mover in a position shared by one of the positions in allies (which is typically filled with friendly units that can be passed through in multi-tile- movement scenarios, and is also used considered an undesirable thing to affect for the Technique), it will recalculate a move so that it does not pass into that cell.
      The keys in impassable should be the positions of enemies and obstacles that cannot be moved through, and will be ignored if there is a target overlapping one.
      This caches its result in a member field, path, which can be fetched after finding a path and will change with each call to a pathfinding method.
      Parameters:
      moveLength - the maximum distance to try to pathfind out to; if a spot to use a Technique can be found while moving no more than this distance, then the targetMap field in this object will have a target Coord that is ideal for the given Technique at the x, y indices corresponding to the last Coord in the returned path.
      tech - a Technique that we will try to find an ideal place to use, and/or a path toward that place.
      dungeon - a char 2D array with '#' for walls.
      los - a BresenhamLine, OrthoLine, or other LineDrawer if the preferred range should try to stay in line of sight, or null if LoS should be disregarded.
      impassable - locations of enemies or mobile hazards/obstacles that aren't in the map as walls
      allies - called onlyPassable in other methods, here it also represents allies for Technique things
      start - the Coord the pathfinder starts at.
      targets - a Set of Coord, not an array of Coord or variable argument list as in other methods.
      Returns:
      an ObjectDeque of Coord that represents a path to travel to get to an ideal place to use tech. Copy of path.

    • findTechniquePath

      public com.github.tommyettinger.ds.ObjectDeque<com.github.yellowstonegames.grid.Coord> findTechniquePath(com.github.tommyettinger.ds.ObjectDeque<com.github.yellowstonegames.grid.Coord> buffer, int moveLength, Technique tech, float[][] dungeon, com.github.yellowstonegames.grid.LineDrawer los, Collection<com.github.yellowstonegames.grid.Coord> impassable, Collection<com.github.yellowstonegames.grid.Coord> allies, com.github.yellowstonegames.grid.Coord start, Collection<com.github.yellowstonegames.grid.Coord> targets)
      Scans the dungeon using DijkstraMap.scan with the listed goals and start point, and returns a list of Coord positions (using the current measurement) needed to get closer to a goal, where goals are considered valid if they are at a valid range for the given Technique to hit at least one target and ideal if that Technique can affect as many targets as possible from a cell that can be moved to with at most movelength steps.
      The return value of this method is the path to get to a location to attack, but on its own it does not tell the user how to perform the attack. It does set the targetMap 2D Coord array field so that if your position at the end of the returned path is non-null in targetMap, it will be a Coord that can be used as a target position for Technique.apply() . If your position at the end of the returned path is null, then an ideal attack position was not reachable by the path.
      This needs a char[][] dungeon as an argument because DijkstraMap does not always have a char[][] version of the map available to it, and certain AOE implementations that a Technique uses may need a char[][] specifically to determine what they affect.
      The maximum length of the returned list is given by moveLength; if moving the full length of the list would place the mover in a position shared by one of the positions in allies (which is typically filled with friendly units that can be passed through in multi-tile- movement scenarios, and is also used considered an undesirable thing to affect for the Technique), it will recalculate a move so that it does not pass into that cell.
      The keys in impassable should be the positions of enemies and obstacles that cannot be moved through, and will be ignored if there is a target overlapping one.
      This overload takes a buffer parameter, an ObjectDeque of Coord, that the results will be appended to. If the buffer is null, a new ObjectDeque will be made and appended to. This caches its result in a member field, path, which can be fetched after finding a path and will change with each call to a pathfinding method. Any existing contents of buffer will not affect the path field of this DijkstraMap.
      Parameters:
      buffer - an existing ObjectDeque of Coord that will have the result appended to it (in-place); if null, this will make a new ObjectDeque
      moveLength - the maximum distance to try to pathfind out to; if a spot to use a Technique can be found while moving no more than this distance, then the targetMap field in this object will have a target Coord that is ideal for the given Technique at the x, y indices corresponding to the last Coord in the returned path.
      tech - a Technique that we will try to find an ideal place to use, and/or a path toward that place.
      dungeon - a char 2D array with '#' for walls.
      los - a BresenhamLine, OrthoLine, or other LineDrawer if the preferred range should try to stay in line of sight, or null if LoS should be disregarded.
      impassable - locations of enemies or mobile hazards/obstacles that aren't in the map as walls
      allies - called onlyPassable in other methods, here it also represents allies for Technique things
      start - the Coord the pathfinder starts at.
      targets - a Collection of Coord, not an array of Coord or variable argument list as in other methods.
      Returns:
      an ObjectDeque of Coord that represents a path to travel to get to an ideal place to use tech. Copy of path.

    • findFleePath

      public com.github.tommyettinger.ds.ObjectDeque<com.github.yellowstonegames.grid.Coord> findFleePath(int length, float preferLongerPaths, Collection<com.github.yellowstonegames.grid.Coord> impassable, Collection<com.github.yellowstonegames.grid.Coord> onlyPassable, com.github.yellowstonegames.grid.Coord start, com.github.yellowstonegames.grid.Coord... fearSources)
      Scans the dungeon using DijkstraMap.scan() with the listed fearSources and start point, and returns a list of Coord positions (using Manhattan distance) needed to get further from the closest fearSources, meant for running away. The maximum length of the returned list is given by length; if moving the full length of the list would place the mover in a position shared by one of the positions in onlyPassable (which is typically filled with friendly units that can be passed through in multi-tile- movement scenarios), it will recalculate a move so that it does not pass into that cell. The keys in impassable should be the positions of enemies and obstacles that cannot be moved through, and will be ignored if there is a fearSource overlapping one. The preferLongerPaths parameter is meant to be tweaked and adjusted; higher values should make creatures prefer to escape out of doorways instead of hiding in the closest corner, and a value of 1.2f should be typical for many maps. The parameters preferLongerPaths, impassable, and the varargs used for fearSources will be cached, and any subsequent calls that use the same values as the last values passed will avoid recalculating unnecessary scans.
      This caches its result in a member field, path, which can be fetched after finding a path and will change with each call to a pathfinding method.
      Parameters:
      length - the length of the path to calculate
      preferLongerPaths - Set this to 1.2f if you aren't sure; it will probably need tweaking for different maps.
      impassable - a Set of impassable Coord positions that may change (not constant like walls); can be null
      onlyPassable - a Set of Coord positions that this pathfinder cannot end a path occupying (typically allies); can be null
      start - the start of the path, should correspond to the minimum-x, minimum-y position of the pathfinder
      fearSources - a vararg or array of Coord positions to run away from
      Returns:
      an ObjectDeque of Coord that will contain the locations of this creature as it goes away from fear sources. Copy of path.

    • findFleePath

      public com.github.tommyettinger.ds.ObjectDeque<com.github.yellowstonegames.grid.Coord> findFleePath(int length, int scanLimit, float preferLongerPaths, Collection<com.github.yellowstonegames.grid.Coord> impassable, Collection<com.github.yellowstonegames.grid.Coord> onlyPassable, com.github.yellowstonegames.grid.Coord start, com.github.yellowstonegames.grid.Coord... fearSources)
      Scans the dungeon using DijkstraMap.scan or DijkstraMap.partialScan with the listed fearSources and start point, and returns a list of Coord positions (using this DijkstraMap's metric) needed to get further from the closest fearSources, meant for running away. The maximum length of the returned list is given by length, which represents movement in a system where a single move can be multiple cells if length is greater than 1 and should usually be 1 in standard roguelikes; if moving the full length of the list would place the mover in a position shared by one of the positions in onlyPassable (which is typically filled with friendly units that can be passed through in multi-cell-movement scenarios), it will recalculate a move so that it does not pass into that cell. The keys in impassable should be the positions of enemies and obstacles that cannot be moved through, and will be ignored if there is a fearSource overlapping one. The preferLongerPaths parameter is meant to be tweaked and adjusted; higher values should make creatures prefer to escape out of doorways instead of hiding in the closest corner, and a value of 1.2f should be typical for many maps. The parameters preferLongerPaths, impassable, and the varargs used for fearSources will be cached, and any subsequent calls that use the same values as the last values passed will avoid recalculating unnecessary scans. However, scanLimit is not cached; if you use scanLimit then it is assumed you are using some value for it that shouldn't change relative to the other parameters (like twice the length). The full map will only be scanned if scanLimit is 0 or less; for positive scanLimit values this will scan only that distance out from each goal, which can save processing time on maps where only a small part matters. Generally, scanLimit should be significantly greater than length.
      This caches its result in a member field, path, which can be fetched after finding a path and will change with each call to a pathfinding method.
      Parameters:
      length - the length of the path to calculate
      scanLimit - how many steps away from a fear source to calculate; negative scans the whole map
      preferLongerPaths - Set this to 1.2f if you aren't sure; it will probably need tweaking for different maps.
      impassable - a Set of impassable Coord positions that may change (not constant like walls); can be null
      onlyPassable - a Set of Coord positions that this pathfinder cannot end a path occupying (typically allies); can be null
      start - the start of the path, should correspond to the minimum-x, minimum-y position of the pathfinder
      fearSources - a vararg or array of Coord positions to run away from
      Returns:
      an ObjectDeque of Coord that will contain the locations of this creature as it goes away from fear sources. Copy of path.

    • findFleePath

      public com.github.tommyettinger.ds.ObjectDeque<com.github.yellowstonegames.grid.Coord> findFleePath(com.github.tommyettinger.ds.ObjectDeque<com.github.yellowstonegames.grid.Coord> buffer, int length, int scanLimit, float preferLongerPaths, Collection<com.github.yellowstonegames.grid.Coord> impassable, Collection<com.github.yellowstonegames.grid.Coord> onlyPassable, com.github.yellowstonegames.grid.Coord start, com.github.yellowstonegames.grid.Coord... fearSources)
      Scans the dungeon using DijkstraMap.scan or DijkstraMap.partialScan with the listed fearSources and start point, and returns a list of Coord positions (using this DijkstraMap's metric) needed to get further from the closest fearSources, meant for running away. The maximum length of the returned list is given by length, which represents movement in a system where a single move can be multiple cells if length is greater than 1 and should usually be 1 in standard roguelikes; if moving the full length of the list would place the mover in a position shared by one of the positions in onlyPassable (which is typically filled with friendly units that can be passed through in multi-cell-movement scenarios), it will recalculate a move so that it does not pass into that cell. The keys in impassable should be the positions of enemies and obstacles that cannot be moved through, and will be ignored if there is a fearSource overlapping one. The preferLongerPaths parameter is meant to be tweaked and adjusted; higher values should make creatures prefer to escape out of doorways instead of hiding in the closest corner, and a value of 1.2f should be typical for many maps. The parameters preferLongerPaths, impassable, and the varargs used for fearSources will be cached, and any subsequent calls that use the same values as the last values passed will avoid recalculating unnecessary scans. However, scanLimit is not cached; if you use scanLimit then it is assumed you are using some value for it that shouldn't change relative to the other parameters (like twice the length). The full map will only be scanned if scanLimit is 0 or less; for positive scanLimit values this will scan only that distance out from each goal, which can save processing time on maps where only a small part matters. Generally, scanLimit should be significantly greater than length.
      This overload takes a buffer parameter, an ObjectDeque of Coord, that the results will be appended to. If the buffer is null, a new ObjectDeque will be made and appended to. This caches its result in a member field, path, which can be fetched after finding a path and will change with each call to a pathfinding method. Any existing contents of buffer will not affect the path field of this DijkstraMap.
      Parameters:
      buffer - an existing ObjectDeque of Coord that will have the result appended to it (in-place); if null, this will make a new ObjectDeque
      length - the length of the path to calculate
      scanLimit - how many steps away from a fear source to calculate; negative scans the whole map
      preferLongerPaths - Set this to 1.2f if you aren't sure; it will probably need tweaking for different maps.
      impassable - a Set of impassable Coord positions that may change (not constant like walls); can be null
      onlyPassable - a Set of Coord positions that this pathfinder cannot end a path occupying (typically allies); can be null
      start - the start of the path, should correspond to the minimum-x, minimum-y position of the pathfinder
      fearSources - a vararg or array of Coord positions to run away from
      Returns:
      an ObjectDeque of Coord that will contain the locations of this creature as it goes away from fear sources. Copy of path.

    • findPathLarge

      public com.github.tommyettinger.ds.ObjectDeque<com.github.yellowstonegames.grid.Coord> findPathLarge(int size, int length, Collection<com.github.yellowstonegames.grid.Coord> impassable, Collection<com.github.yellowstonegames.grid.Coord> onlyPassable, com.github.yellowstonegames.grid.Coord start, com.github.yellowstonegames.grid.Coord... targets)
      For pathfinding creatures larger than 1x1 cell; scans the dungeon using DijkstraMap.scan with the listed goals and start point, and returns a list of Coord positions (using the current measurement) needed to get closer to the closest reachable goal. The maximum length of the returned list is given by length; if moving the full length of the list would place the mover in a position shared by one of the positions in onlyPassable (which is typically filled with friendly units that can be passed through in multi-tile- movement scenarios), it will recalculate a move so that it does not pass into that cell. The keys in impassable should be the positions of enemies and obstacles that cannot be moved through, and will be ignored if there is a goal overlapping one. The parameter size refers to the side length of a square unit, such as 2 for a 2x2 unit. The parameter start must refer to the minimum-x, minimum-y cell of that unit if size is > 1, and all positions in the returned path will refer to movement of the minimum-x, minimum-y cell.
      This caches its result in a member field, path, which can be fetched after finding a path and will change with each call to a pathfinding method.
      Parameters:
      size - the side length of the creature trying to find a path
      length - the length of the path to calculate
      impassable - a Set of impassable Coord positions that may change (not constant like walls); can be null
      onlyPassable - a Set of Coord positions that this pathfinder cannot end a path occupying (typically allies); can be null
      start - the start of the path, should correspond to the minimum-x, minimum-y position of the pathfinder
      targets - a vararg or array of Coord that this will try to pathfind toward
      Returns:
      an ObjectDeque of Coord that will contain the min-x, min-y locations of this creature as it goes toward a target. Copy of path.

    • findPathLarge

      public com.github.tommyettinger.ds.ObjectDeque<com.github.yellowstonegames.grid.Coord> findPathLarge(int size, int length, int scanLimit, Collection<com.github.yellowstonegames.grid.Coord> impassable, Collection<com.github.yellowstonegames.grid.Coord> onlyPassable, com.github.yellowstonegames.grid.Coord start, com.github.yellowstonegames.grid.Coord... targets)

    • findAttackPathLarge

      public com.github.tommyettinger.ds.ObjectDeque<com.github.yellowstonegames.grid.Coord> findAttackPathLarge(int size, int moveLength, int preferredRange, com.github.yellowstonegames.grid.LineDrawer los, Collection<com.github.yellowstonegames.grid.Coord> impassable, Collection<com.github.yellowstonegames.grid.Coord> onlyPassable, com.github.yellowstonegames.grid.Coord start, com.github.yellowstonegames.grid.Coord... targets)
      For pathfinding creatures larger than 1x1 cell; scans the dungeon using DijkstraMap.scan with the listed goals and start point, and returns a list of Coord positions (using the current measurement) needed to get closer to a goal, until preferredRange is reached, or further from a goal if the preferredRange has not been met at the current distance. The maximum length of the returned list is given by moveLength; if moving the full length of the list would place the mover in a position shared by one of the positions in onlyPassable (which is typically filled with friendly units that can be passed through in multi-tile- movement scenarios), it will recalculate a move so that it does not pass into that cell. The keys in impassable should be the positions of enemies and obstacles that cannot be moved through, and will be ignored if there is a goal overlapping one. The parameter size refers to the side length of a square unit, such as 2 for a 2x2 unit. The parameter start must refer to the minimum-x, minimum-y cell of that unit if size is > 1, and all positions in the returned path will refer to movement of the minimum-x, minimum-y cell.
      This caches its result in a member field, path, which can be fetched after finding a path and will change with each call to a pathfinding method.
      Parameters:
      size - the side length of the creature trying to find a path
      moveLength - the length of the path to calculate
      preferredRange - the distance this unit will try to keep from a target
      los - a BresenhamLine, OrthoLine, or other LineDrawer if the preferredRange should try to stay in line of sight, or null if LoS should be disregarded.
      impassable - a Set of impassable Coord positions that may change (not constant like walls); can be null
      onlyPassable - a Set of Coord positions that this pathfinder cannot end a path occupying (typically allies); can be null
      start - the start of the path, should correspond to the minimum-x, minimum-y position of the pathfinder
      targets - a vararg or array of Coord that this will try to pathfind toward
      Returns:
      an ObjectDeque of Coord that will contain the min-x, min-y locations of this creature as it goes toward a target. Copy of path.

    • findAttackPathLarge

      public com.github.tommyettinger.ds.ObjectDeque<com.github.yellowstonegames.grid.Coord> findAttackPathLarge(int size, int moveLength, int minPreferredRange, int maxPreferredRange, com.github.yellowstonegames.grid.LineDrawer los, Collection<com.github.yellowstonegames.grid.Coord> impassable, Collection<com.github.yellowstonegames.grid.Coord> onlyPassable, com.github.yellowstonegames.grid.Coord start, com.github.yellowstonegames.grid.Coord... targets)
      Scans the dungeon using DijkstraMap.scan with the listed goals and start point, and returns a list of Coord positions (using the current measurement) needed to get closer to a goal, until a cell is reached with a distance from a goal that is at least equal to minPreferredRange and no more than maxPreferredRange, which may go further from a goal if the minPreferredRange has not been met at the current distance. The maximum length of the returned list is given by moveLength; if moving the full length of the list would place the mover in a position shared by one of the positions in onlyPassable (which is typically filled with friendly units that can be passed through in multi-tile- movement scenarios), it will recalculate a move so that it does not pass into that cell. The keys in impassable should be the positions of enemies and obstacles that cannot be moved through, and will be ignored if there is a goal overlapping one. The parameter size refers to the side length of a square unit, such as 2 for a 2x2 unit. The parameter start must refer to the minimum-x, minimum-y cell of that unit if size is > 1, and all positions in the returned path will refer to movement of the minimum-x, minimum-y cell.
      This caches its result in a member field, path, which can be fetched after finding a path and will change with each call to a pathfinding method.
      Parameters:
      size - the side length of the creature trying to find a path
      moveLength - the length of the path to calculate
      minPreferredRange - the (inclusive) lower bound of the distance this unit will try to keep from a target
      maxPreferredRange - the (inclusive) upper bound of the distance this unit will try to keep from a target
      los - a BresenhamLine, OrthoLine, or other LineDrawer if the preferredRange should try to stay in line of sight, or null if LoS should be disregarded.
      impassable - a Set of impassable Coord positions that may change (not constant like walls); can be null
      onlyPassable - a Set of Coord positions that this pathfinder cannot end a path occupying (typically allies); can be null
      start - the start of the path, should correspond to the minimum-x, minimum-y position of the pathfinder
      targets - a vararg or array of Coord that this will try to pathfind toward
      Returns:
      an ObjectDeque of Coord that will contain the min-x, min-y locations of this creature as it goes toward a target. Copy of path.

    • findFleePathLarge

      public com.github.tommyettinger.ds.ObjectDeque<com.github.yellowstonegames.grid.Coord> findFleePathLarge(int size, int length, float preferLongerPaths, Collection<com.github.yellowstonegames.grid.Coord> impassable, Collection<com.github.yellowstonegames.grid.Coord> onlyPassable, com.github.yellowstonegames.grid.Coord start, com.github.yellowstonegames.grid.Coord... fearSources)
      Scans the dungeon using DijkstraMap.scan with the listed fearSources and start point, and returns a list of Coord positions (using Manhattan distance) needed to get further from the closest fearSources, meant for running away. The maximum length of the returned list is given by length; if moving the full length of the list would place the mover in a position shared by one of the positions in onlyPassable (which is typically filled with friendly units that can be passed through in multi-tile- movement scenarios), it will recalculate a move so that it does not pass into that cell. The keys in impassable should be the positions of enemies and obstacles that cannot be moved through, and will be ignored if there is a fearSource overlapping one. The preferLongerPaths parameter is meant to be tweaked and adjusted; higher values should make creatures prefer to escape out of doorways instead of hiding in the closest corner, and a value of 1.2f should be typical for many maps. The parameters size, preferLongerPaths, impassable, and the varargs used for fearSources will be cached, and any subsequent calls that use the same values as the last values passed will avoid recalculating unnecessary scans. Calls to findFleePath will cache as if size is 1, and may share a cache with this function. The parameter size refers to the side length of a square unit, such as 2 for a 2x2 unit. The parameter start must refer to the minimum-x, minimum-y cell of that unit if size is > 1, and all positions in the returned path will refer to movement of the minimum-x, minimum-y cell.
      This caches its result in a member field, path, which can be fetched after finding a path and will change with each call to a pathfinding method.
      Parameters:
      size - the side length of the creature trying the find a path
      length - the length of the path to calculate
      preferLongerPaths - Set this to 1.2f if you aren't sure; it will probably need tweaking for different maps.
      impassable - a Set of impassable Coord positions that may change (not constant like walls); can be null
      onlyPassable - a Set of Coord positions that this pathfinder cannot end a path occupying (typically allies); can be null
      start - the start of the path, should correspond to the minimum-x, minimum-y position of the pathfinder
      fearSources - a vararg or array of Coord positions to run away from
      Returns:
      an ObjectDeque of Coord that will contain the locations of this creature as it goes away from fear sources. Copy of path.

    • findPathPreScanned

      public com.github.tommyettinger.ds.ObjectDeque<com.github.yellowstonegames.grid.Coord> findPathPreScanned(com.github.yellowstonegames.grid.Coord target)
      When you can control how often the (relatively time-intensive) scan() method is called, but may need simple paths very frequently (such as for a path that follows the mouse), you can use this method to reduce the amount of work needed to find paths. Needs scan() or partialScan() to already be called and at least one goal to already be set, and does not restrict the length of the path or behave as if the pathfinder has allies or enemies.
      This caches its result in a member field, path, which can be fetched after finding a path and will change with each call to a pathfinding method.
      Parameters:
      target - the target cell
      Returns:
      an ObjectDeque of Coord that make up the best path. Copy of path.

    • findPathPreScanned

      public com.github.tommyettinger.ds.ObjectDeque<com.github.yellowstonegames.grid.Coord> findPathPreScanned(com.github.tommyettinger.ds.ObjectDeque<com.github.yellowstonegames.grid.Coord> buffer, com.github.yellowstonegames.grid.Coord target)
      When you can control how often the (relatively time-intensive) scan() method is called, but may need simple paths very frequently (such as for a path that follows the mouse), you can use this method to reduce the amount of work needed to find paths. Needs scan() or partialScan() to already be called and at least one goal to already be set, and does not restrict the length of the path or behave as if the pathfinder has allies or enemies.
      This overload takes a buffer parameter, an ObjectDeque of Coord, that the results will be appended to. If the buffer is null, a new ObjectDeque will be made and appended to. This caches its result in a member field, path, which can be fetched after finding a path and will change with each call to a pathfinding method. Any existing contents of buffer will not affect the path field of this DijkstraMap.
      Parameters:
      buffer - an existing ObjectDeque of Coord that will have the result appended to it (in-place); if null, this will make a new ObjectDeque
      target - the target cell
      Returns:
      an ObjectDeque of Coord that make up the best path, appended to buffer (if non-null)

    • floodFill

      public com.github.yellowstonegames.grid.CoordFloatOrderedMap floodFill(int radius, com.github.yellowstonegames.grid.Coord... starts)
      A simple limited flood-fill that returns a OrderedMap of Coord keys to the float values in the DijkstraMap, only calculating out to a number of steps determined by limit. This can be useful if you need many flood-fills and don't need a large area for each, or if you want to have an effect spread to a certain number of cells away.
      Parameters:
      radius - the number of steps to take outward from each starting position.
      starts - a vararg group of Coords to step outward from; this often will only need to be one Coord.
      Returns:
      a CoordFloatOrderedMap, with float values; the starts are included in this with the value 0f .

    • floodFill

      public com.github.yellowstonegames.grid.CoordFloatOrderedMap floodFill(int radius, Iterable<com.github.yellowstonegames.grid.Coord> starts)
      A simple limited flood-fill that returns a OrderedMap of Coord keys to the float values in the DijkstraMap, only calculating out to a number of steps determined by limit. This can be useful if you need many flood-fills and don't need a large area for each, or if you want to have an effect spread to a certain number of cells away.
      Parameters:
      radius - the number of steps to take outward from each starting position.
      starts - any Iterable of Coords to step outward from; Collections.singletonList(Object) may be useful if you have only one start
      Returns:
      a new CoordFloatOrderedMap; the starts are included in this with the value 0f .

    • getMappedCount

      public int getMappedCount()

    • getBlockingRequirement

      public int getBlockingRequirement()
      If you want obstacles present in orthogonal cells to prevent pathfinding along the diagonal between them, this can be used to make thin diagonal walls non-viable to move through, or even to prevent diagonal movement if any one obstacle is orthogonally adjacent to both the start and target cell of a diagonal move. If you haven't set this yet, then the default is 2.
      If this is 0, as a special case no orthogonal obstacles will block diagonal moves.
      If this is 1, having one orthogonal obstacle adjacent to both the current cell and the cell the pathfinder is trying to diagonally enter will block diagonal moves. This generally blocks movement around corners, the "hard corner" rule used in some games.
      If this is 2 (the default), having two orthogonal obstacles adjacent to both the current cell and the cell the pathfinder is trying to diagonally enter will block diagonal moves. As an example, if there is a wall to the north and a wall to the east, then the pathfinder won't be able to move northeast even if there is a floor there.
      Returns:
      the current level of blocking required to stop a diagonal move

    • setBlockingRequirement

      public void setBlockingRequirement(int blockingRequirement)
      If you want obstacles present in orthogonal cells to prevent pathfinding along the diagonal between them, this can be used to make thin diagonal walls non-viable to move through, or even to prevent diagonal movement if any one obstacle is orthogonally adjacent to both the start and target cell of a diagonal move. If you haven't set this yet, then the default is 2.
      If this is 0, as a special case no orthogonal obstacles will block diagonal moves.
      If this is 1, having one orthogonal obstacle adjacent to both the current cell and the cell the pathfinder is trying to diagonally enter will block diagonal moves. This generally blocks movement around corners, the "hard corner" rule used in some games.
      If this is 2 (the default), having two orthogonal obstacles adjacent to both the current cell and the cell the pathfinder is trying to diagonally enter will block diagonal moves. As an example, if there is a wall to the north and a wall to the east, then the pathfinder won't be able to move northeast even if there is a floor there.
      Parameters:
      blockingRequirement - the desired level of blocking required to stop a diagonal move