public class DijkstraMap
extends java.lang.Object
implements java.io.Serializable
setGoal(Coord)
or setGoals(Iterable)
, unlike A*,
which 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 cost; when paths are short or unobstructed, A* tends to be faster, though some convoluted map shapes can
slow down A* more than DijkstraMap.
setGoal(Coord)
, scanning the map to find distances with scan(Collection)
, 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, start is the 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).
Modifier and Type | Field and Description |
---|---|
double[][] |
costMap
This stores the entry cost multipliers for each cell; that is, a value of 1.0 is a normal, unmodified cell, but
a value of 0.5 can be entered easily (two cells of its cost can be entered for the cost of one 1.0 cell), and a
value of 2.0 can only be entered with difficulty (one cell of its cost can be entered for the cost of two 1.0
cells).
|
boolean |
cutShort |
static double |
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 999800.0 .
|
static double |
FLOOR
Floor cells, which include any walkable cell, are marked with a high number equal to 999200.0 .
|
protected IntVLA |
fresh
Goals that pathfinding will seek out.
|
static double |
GOAL
Goals are always marked with 0.
|
protected IntVLA |
goals
Goals that pathfinding will seek out.
|
double[][] |
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.
|
Measurement |
measurement
This affects how distance is measured on diagonal directions vs.
|
java.util.ArrayList<Coord> |
path
The latest path that was obtained by calling findPath().
|
double[][] |
physicalMap
Stores which parts of the map are accessible and which are not.
|
IRNG |
rng
The IRNG used to decide which one of multiple equally-short paths to take.
|
boolean |
standardCosts |
Coord[][] |
targetMap |
static double |
WALL
Walls, which are solid no-entry cells, are marked with a high number equal to 999500.0 .
|
int |
width
Width of the map.
|
Constructor and 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,
IRNG rng)
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,
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(char[][] level,
Measurement measurement,
IRNG rng)
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(double[][] level)
Used to construct a DijkstraMap from the output of another.
|
DijkstraMap(double[][] level,
Measurement measurement)
Used to construct a DijkstraMap from the output of another, specifying a distance calculation.
|
DijkstraMap(IRNG random)
Construct a DijkstraMap without a level to actually scan.
|
Modifier and Type | Method and Description |
---|---|
void |
clearGoals()
Used to remove all goals and undo any changes to gradientMap made by having a goal present.
|
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(Coord point)
Internally, DijkstraMap uses int primitives instead of Coord objects, but the specific encoding depends on
this DijkstraMap's width and height.
|
int |
encode(int x,
int y)
Internally, DijkstraMap uses int primitives instead of Coord objects, but the specific encoding depends on
this DijkstraMap's width and height.
|
java.util.ArrayList<Coord> |
findAttackPath(java.util.ArrayList<Coord> buffer,
int moveLength,
int minPreferredRange,
int maxPreferredRange,
LOS los,
java.util.Collection<Coord> impassable,
java.util.Collection<Coord> onlyPassable,
Coord start,
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.
|
java.util.ArrayList<Coord> |
findAttackPath(int moveLength,
int minPreferredRange,
int maxPreferredRange,
LOS los,
java.util.Collection<Coord> impassable,
java.util.Collection<Coord> onlyPassable,
Coord start,
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.
|
java.util.ArrayList<Coord> |
findAttackPath(int moveLength,
int preferredRange,
LOS los,
java.util.Collection<Coord> impassable,
java.util.Collection<Coord> onlyPassable,
Coord start,
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.
|
java.util.ArrayList<Coord> |
findAttackPathLarge(int size,
int moveLength,
int minPreferredRange,
int maxPreferredRange,
LOS los,
java.util.Collection<Coord> impassable,
java.util.Collection<Coord> onlyPassable,
Coord start,
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.
|
java.util.ArrayList<Coord> |
findAttackPathLarge(int size,
int moveLength,
int preferredRange,
LOS los,
java.util.Collection<Coord> impassable,
java.util.Collection<Coord> onlyPassable,
Coord start,
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.
|
java.util.ArrayList<Coord> |
findFleePath(java.util.ArrayList<Coord> buffer,
int length,
int scanLimit,
double preferLongerPaths,
java.util.Collection<Coord> impassable,
java.util.Collection<Coord> onlyPassable,
Coord start,
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.
|
java.util.ArrayList<Coord> |
findFleePath(int length,
double preferLongerPaths,
java.util.Collection<Coord> impassable,
java.util.Collection<Coord> onlyPassable,
Coord start,
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.
|
java.util.ArrayList<Coord> |
findFleePath(int length,
int scanLimit,
double preferLongerPaths,
java.util.Collection<Coord> impassable,
java.util.Collection<Coord> onlyPassable,
Coord start,
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.
|
java.util.ArrayList<Coord> |
findFleePathLarge(int size,
int length,
double preferLongerPaths,
java.util.Collection<Coord> impassable,
java.util.Collection<Coord> onlyPassable,
Coord start,
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.
|
static Measurement |
findMeasurement(Radius radius)
Gets the appropriate Measurement to pass to a constructor if you already have a Radius.
|
Coord |
findNearest(Coord start,
java.util.Collection<Coord> targets)
Recalculate the Dijkstra map until it reaches a Coord in targets, then returns the first target found.
|
Coord |
findNearest(Coord start,
Coord... targets)
Recalculate the Dijkstra map until it reaches a Coord in targets, then returns the first target found.
|
java.util.ArrayList<Coord> |
findNearestMultiple(Coord start,
int limit,
java.util.Collection<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.
|
java.util.ArrayList<Coord> |
findPath(java.util.ArrayList<Coord> buffer,
int length,
int scanLimit,
java.util.Collection<Coord> impassable,
java.util.Collection<Coord> onlyPassable,
Coord start,
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.
|
java.util.ArrayList<Coord> |
findPath(int length,
java.util.Collection<Coord> impassable,
java.util.Collection<Coord> onlyPassable,
Coord start,
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.
|
java.util.ArrayList<Coord> |
findPath(int length,
int scanLimit,
java.util.Collection<Coord> impassable,
java.util.Collection<Coord> onlyPassable,
Coord start,
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.
|
java.util.ArrayList<Coord> |
findPathLarge(int size,
int length,
java.util.Collection<Coord> impassable,
java.util.Collection<Coord> onlyPassable,
Coord start,
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.
|
java.util.ArrayList<Coord> |
findPathLarge(int size,
int length,
int scanLimit,
java.util.Collection<Coord> impassable,
java.util.Collection<Coord> onlyPassable,
Coord start,
Coord... targets) |
java.util.ArrayList<Coord> |
findPathPreScanned(java.util.ArrayList<Coord> buffer,
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.
|
java.util.ArrayList<Coord> |
findPathPreScanned(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.
|
static Radius |
findRadius(Measurement measurement)
Gets the appropriate Radius corresponding to a Measurement.
|
java.util.ArrayList<Coord> |
findShortcutPath(Coord start,
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.
|
java.util.ArrayList<Coord> |
findTechniquePath(java.util.ArrayList<Coord> buffer,
int moveLength,
Technique tech,
char[][] dungeon,
LOS los,
java.util.Collection<Coord> impassable,
java.util.Collection<Coord> allies,
Coord start,
java.util.Collection<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.
|
java.util.ArrayList<Coord> |
findTechniquePath(int moveLength,
Technique tech,
char[][] dungeon,
LOS los,
java.util.Collection<Coord> impassable,
java.util.Collection<Coord> allies,
Coord start,
java.util.Collection<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.
|
OrderedMap<Coord,java.lang.Double> |
floodFill(int radius,
Coord... starts)
A simple limited flood-fill that returns a OrderedMap of Coord keys to the Double 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(double[][] 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(double[][] costs)
Used to initialize the entry cost modifiers for games that require variable costs to enter squares.
|
void |
partialScan(Coord start,
int limit,
java.util.Collection<Coord> impassable)
Recalculate the Dijkstra map up to a limit and return it.
|
void |
partialScan(Coord start,
int limit,
java.util.Collection<Coord> impassable,
boolean nonZeroOptimum)
Recalculate the Dijkstra map up to a limit and return it.
|
double[][] |
partialScan(int limit)
Recalculate the Dijkstra map up to a limit and return it.
|
double[][] |
partialScan(int limit,
java.util.Collection<Coord> impassable)
Recalculate the Dijkstra map up to a limit and return it.
|
double[][] |
partialScan(int limit,
java.util.Collection<Coord> impassable,
int size)
Recalculate the Dijkstra map for a creature that is potentially larger than 1x1 cell and return it.
|
void |
partialScan(int limit,
Coord start,
java.util.Collection<Coord> impassable,
int size)
Recalculate the Dijkstra map for a creature that is potentially larger than 1x1 cell 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(Coord pt)
Reverts a cell to the value stored in the original state of the level as known by 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 |
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() ).
|
double[][] |
scan()
Recalculate the Dijkstra map and return it.
|
double[][] |
scan(java.util.Collection<Coord> impassable)
Recalculate the Dijkstra map and return it.
|
double[][] |
scan(java.util.Collection<Coord> impassable,
int size)
Recalculate the Dijkstra map for a creature that is potentially larger than 1x1 cell and return it.
|
void |
scan(Coord start,
java.util.Collection<Coord> impassable)
Recalculate the Dijkstra map and return it.
|
void |
scan(Coord start,
java.util.Collection<Coord> impassable,
boolean nonZeroOptimum)
Recalculate the Dijkstra map and return it.
|
void |
scan(Coord start,
java.util.Collection<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(Coord pt,
double 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(int x,
int y,
double 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(Coord pt)
Marks a cell as a goal for pathfinding, unless the cell is a wall or unreachable area (then it does nothing).
|
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 |
setGoals(Coord[] pts)
Marks many cells as goals for pathfinding, ignoring cells in walls or unreachable areas.
|
void |
setGoals(GreasedRegion pts)
Marks many cells as goals for pathfinding, ignoring cells in walls or unreachable areas.
|
void |
setGoals(java.lang.Iterable<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.
|
public Measurement measurement
public double[][] physicalMap
public double[][] gradientMap
public double[][] costMap
public boolean standardCosts
public int height
public int width
public java.util.ArrayList<Coord> path
public boolean cutShort
public static final double GOAL
public static final double FLOOR
public static final double WALL
public static final double DARK
protected IntVLA goals
protected IntVLA fresh
public IRNG rng
GWTRNG
if you may target web browsers with GWT, or a RNG
or StatefulRNG
otherwise.public Coord[][] targetMap
public DijkstraMap()
public DijkstraMap(IRNG random)
RNG
, before it is ever used in this class. If you use this constructor, you must call an initialize()
method before using any other methods in the class.public DijkstraMap(double[][] level)
level
- public DijkstraMap(double[][] level, Measurement measurement)
level
- measurement
- public DijkstraMap(char[][] level)
level
- public DijkstraMap(char[][] level, IRNG rng)
RNG
, that ensures
predictable path choices given otherwise identical inputs and circumstances.level
- rng
- The RNG to use for certain decisions; only affects find* methods like findPath, not scan.public DijkstraMap(char[][] level, char alternateWall)
level
- public DijkstraMap(char[][] level, Measurement measurement)
level
- measurement
- public DijkstraMap(char[][] level, Measurement measurement, IRNG rng)
level
- rng
- The RNG to use for certain decisions; only affects find* methods like findPath, not scan.public DijkstraMap initialize(double[][] level)
level
- a 2D double array that should be used as the physicalMap for this DijkstraMappublic DijkstraMap initialize(char[][] level)
level
- a 2D char array that this will use to establish which cells are walls ('#' as wall, others as floor)public DijkstraMap initialize(char[][] level, char alternateWall)
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 levelpublic DijkstraMap initializeCost(char[][] level)
level
- a 2D char array that uses '#' for wallspublic DijkstraMap initializeCost(char[][] level, char alternateWall)
level
- a 2D char array that uses alternateChar for walls.alternateWall
- a char to use to represent walls.public DijkstraMap initializeCost(double[][] costs)
costs
- a 2D double array that already has the desired cost valuespublic int encode(Coord point)
point
- a Coord to find an encoded int forpublic int encode(int x, int y)
x
- the x component of the point to find an encoded int fory
- the y component of the point to find an encoded int forpublic Coord decode(int encoded)
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.encoded
- an encoded int specific to this DijkstraMap's height and width; see encode(Coord)
public int decodeX(int encoded)
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 % width
, where width is a public field in this class. You probably would use this method in
conjunction with decodeY(int)
, or would instead use decode(int)
to get a Coord.encoded
- an encoded int specific to this DijkstraMap's height and width; see encode(Coord)
public int decodeY(int encoded)
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 / width
, where width is a public field in this class. You probably would use this method in
conjunction with decodeX(int)
, or would instead use decode(int)
to get a Coord.encoded
- an encoded int specific to this DijkstraMap's height and width; see encode(Coord)
public static Measurement findMeasurement(Radius radius)
radius
- the Radius to find the corresponding Measurement forpublic static Radius findRadius(Measurement measurement)
Measurement.matchingRadius()
as a method on Measurement.measurement
- the Measurement to find the corresponding Radius forpublic void resetMap()
public void resetTargetMap()
public void reset()
public void setGoal(int x, int y)
x
- y
- public void setGoal(Coord pt)
pt
- public void setGoals(GreasedRegion pts)
setGoal(Coord)
over and over, since this doesn't need to do a bounds check. The
GreasedRegion passed to this should have the same (or smaller) width and height as this DijkstraMap.pts
- a GreasedRegion containing "on" cells to treat as goals; should have the same width and height as thispublic void setGoals(java.lang.Iterable<Coord> pts)
setGoal(Coord)
on each Coord in pts.
If you have a GreasedRegion, you should use it with setGoals(GreasedRegion)
, which is faster.pts
- any Iterable of Coord, which can be a List, Set, Queue, etc. of Coords to mark as goalspublic void setGoals(Coord[] pts)
setGoal(Coord)
on each Coord in pts.pts
- an array of Coord to mark as goalspublic void setCost(Coord pt, double cost)
pt
- cost
- public void setCost(int x, int y, double cost)
x
- y
- cost
- public void setOccupied(int x, int y)
x
- y
- public void resetCell(int x, int y)
x
- y
- public void resetCell(Coord pt)
pt
- public void clearGoals()
public double[][] scan()
gradientMap
field and a copy is returned.public double[][] scan(java.util.Collection<Coord> impassable)
gradientMap
field and a copy is returned.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.public void scan(Coord start, java.util.Collection<Coord> impassable)
gradientMap
field, and nothing is returned.
If you want the data returned, you can use scan(Collection)
(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(double[][])
is a
convenient option for copying a 2D double 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 double
arrays do change FLOOR to DARK
, which is usually treated similarly to WALL
.start
- a Coord representing the location of the pathfinder; may be null, which has this scan the whole mapimpassable
- 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.public void scan(Coord start, java.util.Collection<Coord> impassable, boolean nonZeroOptimum)
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(Collection)
(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(double[][])
is a
convenient option for copying a 2D double 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 double
arrays do change FLOOR to DARK
, which is usually treated similarly to WALL
.start
- a Coord representing the location of the pathfinder; may be null, which has this scan the whole mapimpassable
- 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.nonZeroOptimum
- if the cell to pathfind toward should have a value of GOAL
(0.0), this should be
false; if it should have a different value or if you don't know, it should be truepublic double[][] partialScan(int limit)
gradientMap
field and a copy is returned.limit
- The maximum number of steps to scan outward from a goal.public double[][] partialScan(int limit, java.util.Collection<Coord> impassable)
gradientMap
field and a copy is returned.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.public void partialScan(Coord start, int limit, java.util.Collection<Coord> impassable)
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, Collection)
(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(double[][])
is a convenient option for copying a 2D double array).
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 double arrays do change FLOOR to DARK
, which is usually treated similarly to
WALL
.start
- a Coord representing the location of the pathfinder; may be null to have this scan more of the maplimit
- 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.public void partialScan(Coord start, int limit, java.util.Collection<Coord> impassable, boolean nonZeroOptimum)
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, Collection)
(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(double[][])
is a convenient option for copying a 2D double array).
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 double arrays do change FLOOR to DARK
, which is usually treated similarly to
WALL
.start
- a Coord representing the location of the pathfinder; may be null to have this scan more of the maplimit
- 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.nonZeroOptimum
- if the cell to pathfind toward should have a value of GOAL
(0.0), this should be
false; if it should have a different value or if you don't know, it should be truepublic Coord findNearest(Coord start, java.util.Collection<Coord> targets)
start
- the cell to use as the origin for finding the nearest targettargets
- the Coords that this is trying to find; it will stop once it finds onepublic Coord findNearest(Coord start, Coord... targets)
start
- the cell to use as the origin for finding the nearest targettargets
- the Coords that this is trying to find; it will stop once it finds onepublic java.util.ArrayList<Coord> findShortcutPath(Coord start, Coord... targets)
start
- your starting locationtargets
- an array or vararg of Coords to pathfind to the nearest ofpublic java.util.ArrayList<Coord> findNearestMultiple(Coord start, int limit, java.util.Collection<Coord> targets)
start
- the cell to use as the origin for finding the nearest targetslimit
- the maximum number of targets to find before returningtargets
- the Coords that this is trying to find; it will stop once it finds enough (based on limit)public double[][] scan(java.util.Collection<Coord> impassable, int size)
gradientMap
field and a copy is returned.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.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.public void scan(Coord start, java.util.Collection<Coord> impassable, int size)
gradientMap
field, and nothing is returned.
If you want the data returned, you can use scan(Collection, 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(double[][])
is a
convenient option for copying a 2D double 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 double
arrays do change FLOOR to DARK
, which is usually treated similarly to WALL
.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.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.public double[][] partialScan(int limit, java.util.Collection<Coord> impassable, int size)
gradientMap
field and a copy is returned.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.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.public void partialScan(int limit, Coord start, java.util.Collection<Coord> impassable, int size)
gradientMap
field, and nothing is returned.
If you want the data returned, you can use partialScan(int, Collection, 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(double[][])
is a
convenient option for copying a 2D double 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 double
arrays do change FLOOR to DARK
, which is usually treated similarly to WALL
.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.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.public java.util.ArrayList<Coord> findPath(int length, java.util.Collection<Coord> impassable, java.util.Collection<Coord> onlyPassable, Coord start, Coord... targets)
findPath(int, int, Collection, Collection, Coord, Coord...)
to scan a smaller area for performance reasons.
length
- the length of the path to calculateimpassable
- a Set of impassable Coord positions that may change (not constant like walls); can be nullonlyPassable
- a Set of Coord positions that this pathfinder cannot end a path occupying (typically allies); can be nullstart
- the start of the path, should correspond to the minimum-x, minimum-y position of the pathfindertargets
- a vararg or array of Coord that this will try to pathfind towardpublic java.util.ArrayList<Coord> findPath(int length, int scanLimit, java.util.Collection<Coord> impassable, java.util.Collection<Coord> onlyPassable, Coord start, Coord... targets)
length
- the length of the path to calculatescanLimit
- how many cells away from a goal to actually process; negative to process whole mapimpassable
- a Set of impassable Coord positions that may change (not constant like walls); can be nullonlyPassable
- a Set of Coord positions that this pathfinder cannot end a path occupying (typically allies); can be nullstart
- the start of the path, should correspond to the minimum-x, minimum-y position of the pathfindertargets
- a vararg or array of Coord that this will try to pathfind towardpublic java.util.ArrayList<Coord> findPath(java.util.ArrayList<Coord> buffer, int length, int scanLimit, java.util.Collection<Coord> impassable, java.util.Collection<Coord> onlyPassable, Coord start, Coord... targets)
buffer
- an existing ArrayList of Coord that will have the result appended to it (in-place); if null, this will make a new ArrayListlength
- the length of the path to calculatescanLimit
- how many cells away from a goal to actually process; negative to process whole mapimpassable
- a Set of impassable Coord positions that may change (not constant like walls); can be nullonlyPassable
- a Set of Coord positions that this pathfinder cannot end a path occupying (typically allies); can be nullstart
- the start of the path, should correspond to the minimum-x, minimum-y position of the pathfindertargets
- a vararg or array of Coord that this will try to pathfind towardpublic java.util.ArrayList<Coord> findAttackPath(int moveLength, int preferredRange, LOS los, java.util.Collection<Coord> impassable, java.util.Collection<Coord> onlyPassable, Coord start, Coord... targets)
moveLength
- the length of the path to calculatepreferredRange
- the distance this unit will try to keep from a targetlos
- a squidgrid.LOS object 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 nullonlyPassable
- a Set of Coord positions that this pathfinder cannot end a path occupying (typically allies); can be nullstart
- the start of the path, should correspond to the minimum-x, minimum-y position of the pathfindertargets
- a vararg or array of Coord that this will try to pathfind towardpublic java.util.ArrayList<Coord> findAttackPath(int moveLength, int minPreferredRange, int maxPreferredRange, LOS los, java.util.Collection<Coord> impassable, java.util.Collection<Coord> onlyPassable, Coord start, Coord... targets)
moveLength
- the length of the path to calculateminPreferredRange
- the (inclusive) lower bound of the distance this unit will try to keep from a targetmaxPreferredRange
- the (inclusive) upper bound of the distance this unit will try to keep from a targetlos
- a squidgrid.LOS object 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 nullonlyPassable
- a Set of Coord positions that this pathfinder cannot end a path occupying (typically allies); can be nullstart
- the start of the path, should correspond to the minimum-x, minimum-y position of the pathfindertargets
- a vararg or array of Coord that this will try to pathfind towardpublic java.util.ArrayList<Coord> findAttackPath(java.util.ArrayList<Coord> buffer, int moveLength, int minPreferredRange, int maxPreferredRange, LOS los, java.util.Collection<Coord> impassable, java.util.Collection<Coord> onlyPassable, Coord start, Coord... targets)
buffer
- an existing ArrayList of Coord that will have the result appended to it (in-place); if null, this will make a new ArrayListmoveLength
- the length of the path to calculate; almost always, the pathfinder will try to use this length in full to obtain the best rangeminPreferredRange
- the (inclusive) lower bound of the distance this unit will try to keep from a targetmaxPreferredRange
- the (inclusive) upper bound of the distance this unit will try to keep from a targetlos
- a squidgrid.LOS object 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 nullonlyPassable
- a Set of Coord positions that this pathfinder cannot end a path occupying (typically allies); can be nullstart
- the start of the path, should correspond to the minimum-x, minimum-y position of the pathfindertargets
- a vararg or array of Coord that this will try to pathfind towardpublic java.util.ArrayList<Coord> findTechniquePath(int moveLength, Technique tech, char[][] dungeon, LOS los, java.util.Collection<Coord> impassable, java.util.Collection<Coord> allies, Coord start, java.util.Collection<Coord> targets)
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 squidgrid.LOS object 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 wallsallies
- called onlyPassable in other methods, here it also represents allies for Technique thingsstart
- the Coord the pathfinder starts at.targets
- a Set of Coord, not an array of Coord or variable argument list as in other methods.public java.util.ArrayList<Coord> findTechniquePath(java.util.ArrayList<Coord> buffer, int moveLength, Technique tech, char[][] dungeon, LOS los, java.util.Collection<Coord> impassable, java.util.Collection<Coord> allies, Coord start, java.util.Collection<Coord> targets)
buffer
- an existing ArrayList of Coord that will have the result appended to it (in-place); if null, this will make a new ArrayListmoveLength
- 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 squidgrid.LOS object 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 wallsallies
- called onlyPassable in other methods, here it also represents allies for Technique thingsstart
- the Coord the pathfinder starts at.targets
- a Set of Coord, not an array of Coord or variable argument list as in other methods.public java.util.ArrayList<Coord> findFleePath(int length, double preferLongerPaths, java.util.Collection<Coord> impassable, java.util.Collection<Coord> onlyPassable, Coord start, Coord... fearSources)
length
- the length of the path to calculatepreferLongerPaths
- Set this to 1.2 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 nullonlyPassable
- a Set of Coord positions that this pathfinder cannot end a path occupying (typically allies); can be nullstart
- the start of the path, should correspond to the minimum-x, minimum-y position of the pathfinderfearSources
- a vararg or array of Coord positions to run away frompublic java.util.ArrayList<Coord> findFleePath(int length, int scanLimit, double preferLongerPaths, java.util.Collection<Coord> impassable, java.util.Collection<Coord> onlyPassable, Coord start, Coord... fearSources)
length
- the length of the path to calculatescanLimit
- how many steps away from a fear source to calculate; negative scans the whole mappreferLongerPaths
- Set this to 1.2 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 nullonlyPassable
- a Set of Coord positions that this pathfinder cannot end a path occupying (typically allies); can be nullstart
- the start of the path, should correspond to the minimum-x, minimum-y position of the pathfinderfearSources
- a vararg or array of Coord positions to run away frompublic java.util.ArrayList<Coord> findFleePath(java.util.ArrayList<Coord> buffer, int length, int scanLimit, double preferLongerPaths, java.util.Collection<Coord> impassable, java.util.Collection<Coord> onlyPassable, Coord start, Coord... fearSources)
buffer
- an existing ArrayList of Coord that will have the result appended to it (in-place); if null, this will make a new ArrayListlength
- the length of the path to calculatescanLimit
- how many steps away from a fear source to calculate; negative scans the whole mappreferLongerPaths
- Set this to 1.2 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 nullonlyPassable
- a Set of Coord positions that this pathfinder cannot end a path occupying (typically allies); can be nullstart
- the start of the path, should correspond to the minimum-x, minimum-y position of the pathfinderfearSources
- a vararg or array of Coord positions to run away frompublic java.util.ArrayList<Coord> findPathLarge(int size, int length, java.util.Collection<Coord> impassable, java.util.Collection<Coord> onlyPassable, Coord start, Coord... targets)
size
- the side length of the creature trying to find a pathlength
- the length of the path to calculateimpassable
- a Set of impassable Coord positions that may change (not constant like walls); can be nullonlyPassable
- a Set of Coord positions that this pathfinder cannot end a path occupying (typically allies); can be nullstart
- the start of the path, should correspond to the minimum-x, minimum-y position of the pathfindertargets
- a vararg or array of Coord that this will try to pathfind towardpublic java.util.ArrayList<Coord> findPathLarge(int size, int length, int scanLimit, java.util.Collection<Coord> impassable, java.util.Collection<Coord> onlyPassable, Coord start, Coord... targets)
public java.util.ArrayList<Coord> findAttackPathLarge(int size, int moveLength, int preferredRange, LOS los, java.util.Collection<Coord> impassable, java.util.Collection<Coord> onlyPassable, Coord start, Coord... targets)
size
- the side length of the creature trying to find a pathmoveLength
- the length of the path to calculatepreferredRange
- the distance this unit will try to keep from a targetlos
- a squidgrid.LOS object 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 nullonlyPassable
- a Set of Coord positions that this pathfinder cannot end a path occupying (typically allies); can be nullstart
- the start of the path, should correspond to the minimum-x, minimum-y position of the pathfindertargets
- a vararg or array of Coord that this will try to pathfind towardpublic java.util.ArrayList<Coord> findAttackPathLarge(int size, int moveLength, int minPreferredRange, int maxPreferredRange, LOS los, java.util.Collection<Coord> impassable, java.util.Collection<Coord> onlyPassable, Coord start, Coord... targets)
size
- the side length of the creature trying to find a pathmoveLength
- the length of the path to calculateminPreferredRange
- the (inclusive) lower bound of the distance this unit will try to keep from a targetmaxPreferredRange
- the (inclusive) upper bound of the distance this unit will try to keep from a targetlos
- a squidgrid.LOS object 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 nullonlyPassable
- a Set of Coord positions that this pathfinder cannot end a path occupying (typically allies); can be nullstart
- the start of the path, should correspond to the minimum-x, minimum-y position of the pathfindertargets
- a vararg or array of Coord that this will try to pathfind towardpublic java.util.ArrayList<Coord> findFleePathLarge(int size, int length, double preferLongerPaths, java.util.Collection<Coord> impassable, java.util.Collection<Coord> onlyPassable, Coord start, Coord... fearSources)
size
- the side length of the creature trying the find a pathlength
- the length of the path to calculatepreferLongerPaths
- Set this to 1.2 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 nullonlyPassable
- a Set of Coord positions that this pathfinder cannot end a path occupying (typically allies); can be nullstart
- the start of the path, should correspond to the minimum-x, minimum-y position of the pathfinderfearSources
- a vararg or array of Coord positions to run away frompublic java.util.ArrayList<Coord> findPathPreScanned(Coord target)
target
- the target cellpublic java.util.ArrayList<Coord> findPathPreScanned(java.util.ArrayList<Coord> buffer, Coord target)
buffer
- an existing ArrayList of Coord that will have the result appended to it (in-place); if null, this will make a new ArrayListtarget
- the target cellpublic OrderedMap<Coord,java.lang.Double> floodFill(int radius, Coord... starts)
radius
- the number of steps to take outward from each starting position.starts
- a vararg group of Points to step outward from; this often will only need to be one Coord.public int getMappedCount()
public int getBlockingRequirement()
public void setBlockingRequirement(int blockingRequirement)
blockingRequirement
- the desired level of blocking required to stop a diagonal moveCopyright © Eben Howard 2012–2022. All rights reserved.