tcod.path - Pathfinding¶
This module provides a fast configurable pathfinding implementation.
To get started create a 2D NumPy array of integers where a value of zero is a
blocked node and any higher value is the cost to move to that node.
You then pass this array to SimpleGraph
, and then pass that graph to
Pathfinder
.
Once you have a Pathfinder
you call Pathfinder.add_root
to set
the root node. You can then get a path towards or away from the root with
Pathfinder.path_from
and Pathfinder.path_to
respectively.
SimpleGraph
includes a code example of the above process.
Changed in version 5.0: All path-finding functions now respect the NumPy array shape (if a NumPy array is used.)
- class tcod.path.AStar(cost: Any, diagonal: float = 1.41)[source]¶
- Parameters
cost (Union[tcod.map.Map, numpy.ndarray, Any]) –
diagonal (float) – Multiplier for diagonal movement. A value of 0 will disable diagonal movement entirely.
- class tcod.path.CustomGraph(shape: Tuple[int, ...], *, order: str = 'C')[source]¶
A customizable graph defining how a pathfinder traverses the world.
If you only need to path over a 2D array with typical edge rules then you should use
SimpleGraph
. This is an advanced interface for defining custom edge rules which would allow things such as 3D movement.The graph is created with a shape defining the size and number of dimensions of the graph. The shape can only be 4 dimensions or lower.
order determines what style of indexing the interface expects. This is inherited by the pathfinder and will affect the ij/xy indexing order of all methods in the graph and pathfinder objects. The default order of “C” is for ij indexing. The order can be set to “F” for xy indexing.
After this graph is created you’ll need to add edges which define the rules of the pathfinder. These rules usually define movement in the cardinal and diagonal directions, but can also include stairway type edges.
set_heuristic
should also be called so that the pathfinder will use A*.After all edge rules are added the graph can be used to make one or more
Pathfinder
instances.Example:
>>> import numpy as np >>> import tcod >>> graph = tcod.path.CustomGraph((5, 5)) >>> cost = np.ones((5, 5), dtype=np.int8) >>> CARDINAL = [ ... [0, 1, 0], ... [1, 0, 1], ... [0, 1, 0], ... ] >>> graph.add_edges(edge_map=CARDINAL, cost=cost) >>> pf = tcod.path.Pathfinder(graph) >>> pf.add_root((0, 0)) >>> pf.resolve() >>> pf.distance array([[0, 1, 2, 3, 4], [1, 2, 3, 4, 5], [2, 3, 4, 5, 6], [3, 4, 5, 6, 7], [4, 5, 6, 7, 8]]...) >>> pf.path_to((3, 3)) array([[0, 0], [0, 1], [1, 1], [2, 1], [2, 2], [2, 3], [3, 3]]...)
New in version 11.13.
Changed in version 11.15: Added the order parameter.
- add_edge(edge_dir: Tuple[int, ...], edge_cost: int = 1, *, cost: NDArray[Any], condition: Optional[ArrayLike] = None) None [source]¶
Add a single edge rule.
edge_dir is a tuple with the same length as the graphs dimensions. The edge is relative to any node.
edge_cost is the cost multiplier of the edge. Its multiplied with the cost array to the edges actual cost.
cost is a NumPy array where each node has the cost for movement into that node. Zero or negative values are used to mark blocked areas.
condition is an optional array to mark which nodes have this edge. If the node in condition is zero then the edge will be skipped. This is useful to mark portals or stairs for some edges.
The expected indexing for edge_dir, cost, and condition depend on the graphs order.
Example:
>>> import numpy as np >>> import tcod >>> graph3d = tcod.path.CustomGraph((2, 5, 5)) >>> cost = np.ones((2, 5, 5), dtype=np.int8) >>> up_stairs = np.zeros((2, 5, 5), dtype=np.int8) >>> down_stairs = np.zeros((2, 5, 5), dtype=np.int8) >>> up_stairs[0, 0, 4] = 1 >>> down_stairs[1, 0, 4] = 1 >>> CARDINAL = [[0, 1, 0], [1, 0, 1], [0, 1, 0]] >>> graph3d.add_edges(edge_map=CARDINAL, cost=cost) >>> graph3d.add_edge((1, 0, 0), 1, cost=cost, condition=up_stairs) >>> graph3d.add_edge((-1, 0, 0), 1, cost=cost, condition=down_stairs) >>> pf3d = tcod.path.Pathfinder(graph3d) >>> pf3d.add_root((0, 1, 1)) >>> pf3d.path_to((1, 2, 2)) array([[0, 1, 1], [0, 1, 2], [0, 1, 3], [0, 0, 3], [0, 0, 4], [1, 0, 4], [1, 1, 4], [1, 1, 3], [1, 2, 3], [1, 2, 2]]...)
Note in the above example that both sets of up/down stairs were added, but bidirectional edges are not a requirement for the graph. One directional edges such as pits can be added which will only allow movement outwards from the root nodes of the pathfinder.
- add_edges(*, edge_map: ArrayLike, cost: NDArray[Any], condition: Optional[ArrayLike] = None) None [source]¶
Add a rule with multiple edges.
edge_map is a NumPy array mapping the edges and their costs. This is easier to understand by looking at the examples below. Edges are relative to center of the array. The center most value is always ignored. If edge_map has fewer dimensions than the graph then it will apply to the right-most axes of the graph.
cost is a NumPy array where each node has the cost for movement into that node. Zero or negative values are used to mark blocked areas.
condition is an optional array to mark which nodes have this edge. See
add_edge
. If condition is the same array as cost then the pathfinder will not move into open area from a non-open ones.The expected indexing for edge_map, cost, and condition depend on the graphs order. You may need to transpose the examples below if you’re using xy indexing.
Example:
# 2D edge maps: CARDINAL = [ # Simple arrow-key moves. Manhattan distance. [0, 1, 0], [1, 0, 1], [0, 1, 0], ] CHEBYSHEV = [ # Chess king moves. Chebyshev distance. [1, 1, 1], [1, 0, 1], [1, 1, 1], ] EUCLIDEAN = [ # Approximate euclidean distance. [99, 70, 99], [70, 0, 70], [99, 70, 99], ] EUCLIDEAN_SIMPLE = [ # Very approximate euclidean distance. [3, 2, 3], [2, 0, 2], [3, 2, 3], ] KNIGHT_MOVE = [ # Chess knight L-moves. [0, 1, 0, 1, 0], [1, 0, 0, 0, 1], [0, 0, 0, 0, 0], [1, 0, 0, 0, 1], [0, 1, 0, 1, 0], ] AXIAL = [ # https://www.redblobgames.com/grids/hexagons/ [0, 1, 1], [1, 0, 1], [1, 1, 0], ] # 3D edge maps: CARDINAL_PLUS_Z = [ # Cardinal movement with Z up/down edges. [ [0, 0, 0], [0, 1, 0], [0, 0, 0], ], [ [0, 1, 0], [1, 0, 1], [0, 1, 0], ], [ [0, 0, 0], [0, 1, 0], [0, 0, 0], ], ] CHEBYSHEV_3D = [ # Chebyshev distance, but in 3D. [ [1, 1, 1], [1, 1, 1], [1, 1, 1], ], [ [1, 1, 1], [1, 0, 1], [1, 1, 1], ], [ [1, 1, 1], [1, 1, 1], [1, 1, 1], ], ]
- set_heuristic(*, cardinal: int = 0, diagonal: int = 0, z: int = 0, w: int = 0) None [source]¶
Sets a pathfinder heuristic so that pathfinding can done with A*.
cardinal, diagonal, z, and `w are the lower-bound cost of movement in those directions. Values above the lower-bound can be used to create a greedy heuristic, which will be faster at the cost of accuracy.
Example:
>>> import numpy as np >>> import tcod >>> graph = tcod.path.CustomGraph((5, 5)) >>> cost = np.ones((5, 5), dtype=np.int8) >>> EUCLIDEAN = [[99, 70, 99], [70, 0, 70], [99, 70, 99]] >>> graph.add_edges(edge_map=EUCLIDEAN, cost=cost) >>> graph.set_heuristic(cardinal=70, diagonal=99) >>> pf = tcod.path.Pathfinder(graph) >>> pf.add_root((0, 0)) >>> pf.path_to((4, 4)) array([[0, 0], [1, 1], [2, 2], [3, 3], [4, 4]]...) >>> pf.distance array([[ 0, 70, 198, 2147483647, 2147483647], [ 70, 99, 169, 297, 2147483647], [ 198, 169, 198, 268, 396], [2147483647, 297, 268, 297, 367], [2147483647, 2147483647, 396, 367, 396]]...) >>> pf.path_to((2, 0)) array([[0, 0], [1, 0], [2, 0]]...) >>> pf.distance array([[ 0, 70, 198, 2147483647, 2147483647], [ 70, 99, 169, 297, 2147483647], [ 140, 169, 198, 268, 396], [ 210, 239, 268, 297, 367], [2147483647, 2147483647, 396, 367, 396]]...)
Without a heuristic the above example would need to evaluate the entire array to reach the opposite side of it. With a heuristic several nodes can be skipped, which will process faster. Some of the distances in the above example look incorrect, that’s because those nodes are only partially evaluated, but pathfinding to those nodes will work correctly as long as the heuristic isn’t greedy.
- class tcod.path.Dijkstra(cost: Any, diagonal: float = 1.41)[source]¶
- Parameters
cost (Union[tcod.map.Map, numpy.ndarray, Any]) –
diagonal (float) – Multiplier for diagonal movement. A value of 0 will disable diagonal movement entirely.
- class tcod.path.EdgeCostCallback(callback: Callable[[int, int, int, int], float], shape: Tuple[int, int])[source]¶
Calculate cost from an edge-cost callback.
callback is the custom userdata to send to the C call.
shape is a 2-item tuple representing the maximum boundary for the algorithm. The callback will not be called with parameters outside of these bounds.
Changed in version 5.0: Now only accepts a shape argument instead of width and height.
- class tcod.path.NodeCostArray(array: numpy.typing.ArrayLike)[source]¶
Calculate cost from a numpy array of nodes.
array is a NumPy array holding the path-cost of each node. A cost of 0 means the node is blocking.
- static __new__(cls, array: numpy.typing.ArrayLike) NodeCostArray [source]¶
Validate a numpy array and setup a C callback.
- class tcod.path.Pathfinder(graph: Union[CustomGraph, SimpleGraph])[source]¶
A generic modular pathfinder.
How the pathfinder functions depends on the graph provided. see
SimpleGraph
for how to set one up.New in version 11.13.
- add_root(index: Tuple[int, ...], value: int = 0) None [source]¶
Add a root node and insert it into the pathfinder frontier.
index is the root point to insert. The length of index must match the dimensions of the graph.
value is the distance to use for this root. Zero is typical, but if multiple roots are added they can be given different weights.
- clear() None [source]¶
Reset the pathfinder to its initial state.
This sets all values on the
distance
array to their maximum value.
- path_from(index: Tuple[int, ...]) NDArray[Any] [source]¶
Return the shortest path from index to the nearest root.
The returned array is of shape (length, ndim) where length is the total inclusive length of the path and ndim is the dimensions of the pathfinder defined by the graph.
The return value is inclusive, including both the starting and ending points on the path. If the root point is unreachable or index is already at a root then index will be the only point returned.
This automatically calls
resolve
if the pathfinder has not yet reached index.A common usage is to slice off the starting point and convert the array into a list.
Example:
>>> cost = np.ones((5, 5), dtype=np.int8) >>> cost[:, 3:] = 0 >>> graph = tcod.path.SimpleGraph(cost=cost, cardinal=2, diagonal=3) >>> pf = tcod.path.Pathfinder(graph) >>> pf.add_root((0, 0)) >>> pf.path_from((2, 2)).tolist() [[2, 2], [1, 1], [0, 0]] >>> pf.path_from((2, 2))[1:].tolist() # Exclude the starting point by slicing the array. [[1, 1], [0, 0]] >>> pf.path_from((4, 4)).tolist() # Blocked paths will only have the index point. [[4, 4]] >>> pf.path_from((4, 4))[1:].tolist() # Exclude the starting point so that a blocked path is an empty list. []
- path_to(index: Tuple[int, ...]) NDArray[Any] [source]¶
Return the shortest path from the nearest root to index.
See
path_from
. This is an alias forpath_from(...)[::-1]
.This is the method to call when the root is an entity to move to a position rather than a destination itself.
Example:
>>> graph = tcod.path.SimpleGraph( ... cost=np.ones((5, 5), np.int8), cardinal=2, diagonal=3, ... ) >>> pf = tcod.path.Pathfinder(graph) >>> pf.add_root((0, 0)) >>> pf.path_to((0, 0)).tolist() # This method always returns at least one point. [[0, 0]] >>> pf.path_to((3, 3)).tolist() # Always includes both ends on a valid path. [[0, 0], [1, 1], [2, 2], [3, 3]] >>> pf.path_to((3, 3))[1:].tolist() # Exclude the starting point by slicing the array. [[1, 1], [2, 2], [3, 3]] >>> pf.path_to((0, 0))[1:].tolist() # Exclude the starting point so that a blocked path is an empty list. []
- rebuild_frontier() None [source]¶
Reconstruct the frontier using the current distance array.
If you are using
add_root
then you will not need to call this function. This is only needed if thedistance
array has been modified manually.After you are finished editing
distance
you must call this function before callingresolve
or any function which callsresolve
implicitly such aspath_from
orpath_to
.
- resolve(goal: Optional[Tuple[int, ...]] = None) None [source]¶
Manually run the pathfinder algorithm.
The
path_from
andpath_to
methods will automatically call this method on demand.If goal is None then this will attempt to complete the entire
distance
andtraversal
arrays without a heuristic. This is similar to Dijkstra.If goal is given an index then it will attempt to resolve the
distance
andtraversal
arrays only up to the goal. If the graph has set a heuristic then it will be used with a process similar to A*.Example:
>>> graph = tcod.path.SimpleGraph( ... cost=np.ones((4, 4), np.int8), cardinal=2, diagonal=3, ... ) >>> pf = tcod.path.Pathfinder(graph) >>> pf.distance array([[2147483647, 2147483647, 2147483647, 2147483647], [2147483647, 2147483647, 2147483647, 2147483647], [2147483647, 2147483647, 2147483647, 2147483647], [2147483647, 2147483647, 2147483647, 2147483647]]...) >>> pf.add_root((0, 0)) >>> pf.distance array([[ 0, 2147483647, 2147483647, 2147483647], [2147483647, 2147483647, 2147483647, 2147483647], [2147483647, 2147483647, 2147483647, 2147483647], [2147483647, 2147483647, 2147483647, 2147483647]]...) >>> pf.resolve((1, 1)) # Resolve up to (1, 1) as A*. >>> pf.distance # Partially resolved distance. array([[ 0, 2, 6, 2147483647], [ 2, 3, 5, 2147483647], [ 6, 5, 6, 2147483647], [2147483647, 2147483647, 2147483647, 2147483647]]...) >>> pf.resolve() # Resolve the full graph as Dijkstra. >>> pf.distance # Fully resolved distance. array([[0, 2, 4, 6], [2, 3, 5, 7], [4, 5, 6, 8], [6, 7, 8, 9]]...)
- property distance: NDArray[Any]¶
The distance values of the pathfinder.
The array returned from this property maintains the graphs order.
Unreachable or unresolved points will be at their maximum values. You can use
numpy.iinfo
if you need to check for these.Example:
pf # Resolved Pathfinder instance. reachable = pf.distance != numpy.iinfo(pf.distance.dtype).max reachable # A boolean array of reachable area.
You may edit this array manually, but the pathfinder won’t know of your changes until
rebuild_frontier
is called.
- property traversal: NDArray[Any]¶
An array used to generate paths from any point to the nearest root.
The array returned from this property maintains the graphs order. It has an extra dimension which includes the index of the next path.
Example:
# This example demonstrates the purpose of the traversal array. >>> graph = tcod.path.SimpleGraph( ... cost=np.ones((5, 5), np.int8), cardinal=2, diagonal=3, ... ) >>> pf = tcod.path.Pathfinder(graph) >>> pf.add_root((0, 0)) >>> pf.resolve() >>> pf.traversal[3, 3].tolist() # Faster. [2, 2] >>> pf.path_from((3, 3))[1].tolist() # Slower. [2, 2] >>> i, j = (3, 3) # Starting index. >>> path = [(i, j)] # List of nodes from the start to the root. >>> while not (pf.traversal[i, j] == (i, j)).all(): ... i, j = pf.traversal[i, j] ... path.append((i, j)) >>> path # Slower. [(3, 3), (2, 2), (1, 1), (0, 0)] >>> pf.path_from((3, 3)).tolist() # Faster. [[3, 3], [2, 2], [1, 1], [0, 0]]
The above example is slow and will not detect infinite loops. Use
path_from
orpath_to
when you need to get a path.As the pathfinder is resolved this array is filled
- class tcod.path.SimpleGraph(*, cost: numpy.typing.ArrayLike, cardinal: int, diagonal: int, greed: int = 1)[source]¶
A simple 2D graph implementation.
cost is a NumPy array where each node has the cost for movement into that node. Zero or negative values are used to mark blocked areas. A reference of this array is used. Any changes to the array will be reflected in the graph.
cardinal and diagonal are the cost to move along the edges for those directions. The total cost to move from one node to another is the cost array value multiplied by the edge cost. A value of zero will block that direction.
greed is used to define the heuristic. To get the fastest accurate heuristic greed should be the lowest non-zero value on the cost array. Higher values may be used for an inaccurate but faster heuristic.
Example:
>>> import numpy as np >>> import tcod >>> cost = np.ones((5, 10), dtype=np.int8, order="F") >>> graph = tcod.path.SimpleGraph(cost=cost, cardinal=2, diagonal=3) >>> pf = tcod.path.Pathfinder(graph) >>> pf.add_root((2, 4)) >>> pf.path_to((3, 7)).tolist() [[2, 4], [2, 5], [2, 6], [3, 7]]
New in version 11.15.
- set_heuristic(*, cardinal: int, diagonal: int) None [source]¶
Change the heuristic for this graph.
When created a
SimpleGraph
will automatically have a heuristic. So calling this method is often unnecessary.cardinal and diagonal are weights for the heuristic. Higher values are more greedy. The default values are set to
cardinal * greed
anddiagonal * greed
when theSimpleGraph
is created.
- tcod.path.dijkstra2d(distance: ArrayLike, cost: ArrayLike, cardinal: Optional[int] = None, diagonal: Optional[int] = None, *, edge_map: Any = None, out: Optional[np.ndarray] = Ellipsis) NDArray[Any] [source]¶
Return the computed distance of all nodes on a 2D Dijkstra grid.
distance is an input array of node distances. Is this often an array filled with maximum finite values and 1 or more points with a low value such as 0. Distance will flow from these low values to adjacent nodes based the cost to reach those nodes.
cost is an array of node costs. Any node with a cost less than or equal to 0 is considered blocked off. Positive values are the distance needed to reach that node.
cardinal and diagonal are the cost multipliers for edges in those directions. A value of None or 0 will disable those directions. Typical values could be:
1, None
,1, 1
,2, 3
, etc.edge_map is a 2D array of edge costs with the origin point centered on the array. This can be used to define the edges used from one node to another. This parameter can be hard to understand so you should see how it’s used in the examples.
out is the array to fill with the computed Dijkstra distance map. Having out be the same as distance will modify the array in-place, which is normally the fastest option. If out is None then the result is returned as a new array.
Example:
>>> import numpy as np >>> import tcod >>> cost = np.ones((3, 3), dtype=np.uint8) >>> cost[:2, 1] = 0 >>> cost array([[1, 0, 1], [1, 0, 1], [1, 1, 1]], dtype=uint8) >>> dist = tcod.path.maxarray((3, 3), dtype=np.int32) >>> dist[0, 0] = 0 >>> dist array([[ 0, 2147483647, 2147483647], [2147483647, 2147483647, 2147483647], [2147483647, 2147483647, 2147483647]]...) >>> tcod.path.dijkstra2d(dist, cost, 2, 3, out=dist) array([[ 0, 2147483647, 10], [ 2, 2147483647, 8], [ 4, 5, 7]]...) >>> path = tcod.path.hillclimb2d(dist, (2, 2), True, True) >>> path array([[2, 2], [2, 1], [1, 0], [0, 0]], dtype=int32) >>> path = path[::-1].tolist() >>> while path: ... print(path.pop(0)) [0, 0] [1, 0] [2, 1] [2, 2]
edge_map is used for more complicated graphs. The following example uses a ‘knight move’ edge map.
Example:
>>> import numpy as np >>> import tcod >>> knight_moves = [ ... [0, 1, 0, 1, 0], ... [1, 0, 0, 0, 1], ... [0, 0, 0, 0, 0], ... [1, 0, 0, 0, 1], ... [0, 1, 0, 1, 0], ... ] >>> dist = tcod.path.maxarray((8, 8)) >>> dist[0,0] = 0 >>> cost = np.ones((8, 8), int) >>> tcod.path.dijkstra2d(dist, cost, edge_map=knight_moves, out=dist) array([[0, 3, 2, 3, 2, 3, 4, 5], [3, 4, 1, 2, 3, 4, 3, 4], [2, 1, 4, 3, 2, 3, 4, 5], [3, 2, 3, 2, 3, 4, 3, 4], [2, 3, 2, 3, 4, 3, 4, 5], [3, 4, 3, 4, 3, 4, 5, 4], [4, 3, 4, 3, 4, 5, 4, 5], [5, 4, 5, 4, 5, 4, 5, 6]]...) >>> tcod.path.hillclimb2d(dist, (7, 7), edge_map=knight_moves) array([[7, 7], [5, 6], [3, 5], [1, 4], [0, 2], [2, 1], [0, 0]], dtype=int32)
edge_map can also be used to define a hex-grid. See https://www.redblobgames.com/grids/hexagons/ for more info. The following example is using axial coordinates.
Example:
hex_edges = [ [0, 1, 1], [1, 0, 1], [1, 1, 0], ]
New in version 11.2.
Changed in version 11.13: Added the edge_map parameter.
Changed in version 12.1: Added out parameter. Now returns the output array.
- tcod.path.hillclimb2d(distance: ArrayLike, start: Tuple[int, int], cardinal: Optional[bool] = None, diagonal: Optional[bool] = None, *, edge_map: Any = None) NDArray[Any] [source]¶
Return a path on a grid from start to the lowest point.
distance should be a fully computed distance array. This kind of array is returned by
dijkstra2d
.start is a 2-item tuple with starting coordinates. The axes if these coordinates should match the axis of the distance array. An out-of-bounds start index will raise an IndexError.
At each step nodes adjacent toe current will be checked for a value lower than the current one. Which directions are checked is decided by the boolean values cardinal and diagonal. This process is repeated until all adjacent nodes are equal to or larger than the last point on the path.
If edge_map was used with
tcod.path.dijkstra2d
then it should be reused for this function. Keep in mind that edge_map must be bidirectional since hill-climbing will traverse the map backwards.The returned array is a 2D NumPy array with the shape: (length, axis). This array always includes both the starting and ending point and will always have at least one item.
Typical uses of the returned array will be to either convert it into a list which can be popped from, or transpose it and convert it into a tuple which can be used to index other arrays using NumPy’s advanced indexing rules.
New in version 11.2.
Changed in version 11.13: Added edge_map parameter.
- tcod.path.maxarray(shape: Tuple[int, ...], dtype: Any = <class 'numpy.int32'>, order: Literal[('C', 'F')] = 'C') NDArray[Any] [source]¶
Return a new array filled with the maximum finite value for dtype.
shape is of the new array. Same as other NumPy array initializers.
dtype should be a single NumPy integer type.
order can be “C” or “F”.
This works the same as
np.full(shape, np.iinfo(dtype).max, dtype, order)
.This kind of array is an ideal starting point for distance maps. Just set any point to a lower value such as 0 and then pass this array to a function such as
dijkstra2d
.