# Pathfinding `tcod.path`#

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]#

The older libtcod A* pathfinder.

Parameters:
• cost (Union[tcod.map.Map, numpy.ndarray, Any]) –

• diagonal (float) – Multiplier for diagonal movement. A value of 0 will disable diagonal movement entirely.

get_path(start_x: int, start_y: int, goal_x: int, goal_y: int) list[tuple[int, int]][source]#

Return a list of (x, y) steps to reach the goal point, if possible.

Parameters:
• start_x (int) – Starting X position.

• start_y (int) – Starting Y position.

• goal_x (int) – Destination X position.

• goal_y (int) – Destination Y position.

Returns:

A list of points, or an empty list if there is no valid path.

Return type:

List[Tuple[int, int]]

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],
... ]
>>> pf = tcod.path.Pathfinder(graph)
>>> 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: ArrayLike | None = None) None[source]#

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_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.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: ArrayLike | None = 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]#

Set 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.set_heuristic(cardinal=70, diagonal=99)
>>> pf = tcod.path.Pathfinder(graph)
>>> 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.

property ndim: int#

Return the number of dimensions.

property shape: tuple[int, ...]#

Return the shape of this graph.

class tcod.path.Dijkstra(cost: Any, diagonal: float = 1.41)[source]#

The older libtcod Dijkstra pathfinder.

Parameters:
• cost (Union[tcod.map.Map, numpy.ndarray, Any]) –

• diagonal (float) – Multiplier for diagonal movement. A value of 0 will disable diagonal movement entirely.

get_path(x: int, y: int) list[tuple[int, int]][source]#

Return a list of (x, y) steps to reach the goal point, if possible.

set_goal(x: int, y: int) None[source]#

Set the goal point and recompute the Dijkstra path-finder.

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) [source]#

Validate a numpy array and setup a C callback.

class tcod.path.Pathfinder(graph: )[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:

```>>> import tcod.path
>>> 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.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 for `path_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:

```>>> import tcod.path
>>> graph = tcod.path.SimpleGraph(
...     cost=np.ones((5, 5), np.int8), cardinal=2, diagonal=3,
... )
>>> pf = tcod.path.Pathfinder(graph)
>>> 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 the `distance` array has been modified manually.

After you are finished editing `distance` you must call this function before calling `resolve` or any function which calls `resolve` implicitly such as `path_from` or `path_to`.

resolve(goal: tuple[int, ...] | None = None) None[source]#

Manually run the pathfinder algorithm.

The `path_from` and `path_to` methods will automatically call this method on demand.

If goal is None then this will attempt to complete the entire `distance` and `traversal` arrays without a heuristic. This is similar to Dijkstra.

If goal is given an index then it will attempt to resolve the `distance` and `traversal` 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:

```>>> import tcod.path
>>> 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.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]#

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]#

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.
>>> import tcod.path
>>> graph = tcod.path.SimpleGraph(
...     cost=np.ones((5, 5), np.int8), cardinal=2, diagonal=3,
... )
>>> pf = tcod.path.Pathfinder(graph)
>>> 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` or `path_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.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` and `diagonal * greed` when the `SimpleGraph` is created.

tcod.path.dijkstra2d(distance: ArrayLike, cost: ArrayLike, cardinal: = None, diagonal: = None, *, edge_map: ArrayLike | None = None, out: np.ndarray | None = 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: = None, diagonal: = None, *, edge_map: ArrayLike | None = 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: DTypeLike = <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`.