Class DijkstraMap

java.lang.Object

com.github.tommyettinger.gand.GradientGrid<com.github.yellowstonegames.grid.Coord>

com.github.yellowstonegames.seek.DijkstraMap

public class DijkstraMap
extends com.github.tommyettinger.gand.GradientGrid<com.github.yellowstonegames.grid.Coord>

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 GradientGrid.setGoal(Point2) or GradientGrid.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 here 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 GradientGrid.setGoal(Point2), scanning the map to find distances with GradientGrid.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 GradientGrid.findPathPreScanned(Point2) and giving it the mouse position as a Point2. 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 GradientGrid.findPath(int, Collection, Collection, Point2, Collection). 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 a Collection of Point2 that the NPC should pathfind toward (it could be just one Point2, with or without explicitly putting it in an array, or it could be more and the NPC will pick the closest).
This is similar to GradientGridI2, and both extend GradientGrid, though this uses Coord where GradientGridI2 uses PointI2.
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.
You shouldn't use DijkstraMap for all purposes; it can't handle terrains with a cost to enter, and can't handle directional costs like a one-way ledge. For those tasks, Int2UndirectedGraph or Int2DirectedGraph will be better fits. Int2DirectedGraph and similar versions of DirectedGraph can handle even very complicated kinds of map.

Field Summary

Fields inherited from class com.github.tommyettinger.gand.GradientGrid

blocked, blockingRequirement, cachedFearSources, cachedFleeMap, cachedImpassable, cachedLongerPaths, cutShort, DARK, dirs, FLOOR, fresh, frustration, GOAL, goals, gradientMap, height, initialized, mappedCount, measurement, path, physicalMap, rng, WALL, width, workRay

Constructor Summary

Constructors

Constructor	Description
DijkstraMap()	Construct a DijkstraMap without a level to actually scan.
DijkstraMap(char[][] level)	Constructor meant to take a char[][] in a simple, classic-roguelike-ish format, where '#' means a wall and anything else (often '.' or ' ') is a walkable tile.
DijkstraMap(char[][] level, char alternateWall)	Constructor meant to take a char[][] in a simple, classic-roguelike-ish format, where '#' means a wall and anything else (often '.' or ' ') is a walkable tile.
DijkstraMap(char[][] level, char alternateWall, com.github.tommyettinger.gand.utils.GridMetric measurement)	Constructor meant to take a char[][] in a simple, classic-roguelike-ish format, where '#' means a wall and anything else (often '.' or ' ') is a walkable tile.
DijkstraMap(char[][] level, com.github.tommyettinger.gand.utils.GridMetric measurement)	Constructor meant to take a char[][] in a simple, classic-roguelike-ish format, where '#' means a wall and anything else (often '.' or ' ') is a walkable tile.
DijkstraMap(float[][] level)	Used to construct a DijkstraMap from the output of another.
DijkstraMap(float[][] level, com.github.tommyettinger.gand.utils.GridMetric measurement)	Used to construct a DijkstraMap from the output of another, specifying a distance calculation.

Method Summary

Modifier and Type	Method	Description
protected com.github.yellowstonegames.grid.Coord	acquire(int x, int y)

Methods inherited from class com.github.tommyettinger.gand.GradientGrid

acquire, clearGoals, copy, decode, decode, decodeX, decodeY, encode, encode, equals, findAttackPath, findAttackPath, findAttackPath, findFleePath, findFleePath, findFleePath, findPath, findPath, findPath, findPathPreScanned, findPathPreScanned, floodFill, floodFill, getBlockingRequirement, getGoals, getHeight, getMappedCount, getMeasurement, getWidth, hashCode, initialize, initialize, initialize, isWithin, isWithin, partialScan, partialScan, partialScan, partialScan, partialScan, partialScan, reset, resetCell, resetCell, resetMap, scan, scan, scan, scan, scan, scan, setBlockingRequirement, setFresh, setFresh, setGoal, setGoal, setGoal, setGoals, setGoals, setMeasurement, setOccupied, show, show, shuffleDirs, wallQuery, workingEdit, workingEdit

Methods inherited from class Object

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

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. Uses GridMetric.EUCLIDEAN.

Parameters:

level - a 2D float array that was produced by GradientGrid.scan()

DijkstraMap

public DijkstraMap(float[][] level,
 com.github.tommyettinger.gand.utils.GridMetric measurement)

Used to construct a DijkstraMap from the output of another, specifying a distance calculation.

Parameters:

level - a 2D float array that was produced by GradientGrid.scan()

measurement - the distance calculation to use

DijkstraMap

public DijkstraMap(char[][] level)

Constructor meant to take a char[][] in a simple, classic-roguelike-ish format, where '#' means a wall and anything else (often '.' or ' ') is a walkable tile. This uses GridMetric.EUCLIDEAN, allowing 8-way movement but preferring orthogonal directions in case of a tie.

Parameters:

level - a 2D char array where '#' indicates a wall and any other char is walkable

DijkstraMap

public DijkstraMap(char[][] level,
 char alternateWall)

Constructor meant to take a char[][] in a simple, classic-roguelike-ish format, where '#' means a wall and anything else (often '.' or ' ') is a walkable tile. This uses GridMetric.EUCLIDEAN, allowing 8-way movement but preferring orthogonal directions in case of a tie. You can specify the character used for walls.

Parameters:

level - a 2D char array where alternateWall indicates a wall and any other char is walkable

alternateWall - the char that indicates a wall in level

DijkstraMap

public DijkstraMap(char[][] level,
 com.github.tommyettinger.gand.utils.GridMetric measurement)

Constructor meant to take a char[][] in a simple, classic-roguelike-ish format, where '#' means a wall and anything else (often '.' or ' ') is a walkable tile. Also takes a distance measurement, which you may want to set to GridMetric.MANHATTAN for 4-way movement only, GridMetric.CHEBYSHEV for unpredictable 8-way movement or GridMetric.EUCLIDEAN for more reasonable 8-way movement that prefers straight lines. EUCLIDEAN usually looks the most natural.

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 GridMetric.MANHATTAN for 4-way only movement

DijkstraMap

public DijkstraMap(char[][] level,
 char alternateWall,
 com.github.tommyettinger.gand.utils.GridMetric measurement)

Constructor meant to take a char[][] in a simple, classic-roguelike-ish format, where '#' means a wall and anything else (often '.' or ' ') is a walkable tile. Also takes a distance measurement, which you may want to set to GridMetric.MANHATTAN for 4-way movement only, GridMetric.CHEBYSHEV for unpredictable 8-way movement or GridMetric.EUCLIDEAN for more reasonable 8-way movement that prefers straight lines. EUCLIDEAN usually looks the most natural. You can specify the character used for walls.

Parameters:

level - a char[x][y] map where alternateWall is a wall, and anything else is walkable

alternateWall - the char that indicates a wall in level

measurement - how this should measure orthogonal vs. diagonal measurement, such as GridMetric.MANHATTAN for 4-way only movement

Method Details

acquire

protected com.github.yellowstonegames.grid.Coord acquire(int x,
 int y)

Specified by:

acquire in class com.github.tommyettinger.gand.GradientGrid<com.github.yellowstonegames.grid.Coord>