# tcod.path¶

Example:

```>>> import numpy as np
>>> import tcod.path
>>> dungeon = np.array(
...     [
...         [1, 0, 1, 1, 1],
...         [1, 0, 1, 0, 1],
...         [1, 1, 1, 0, 1],
...     ],
...     dtype=np.int8,
...     )
...

# Create a pathfinder from a numpy array.
# This is the recommended way to use the tcod.path module.
>>> astar = tcod.path.AStar(dungeon)
>>> print(astar.get_path(0, 0, 2, 4))
[(1, 0), (2, 1), (1, 2), (0, 3), (1, 4), (2, 4)]
>>> astar.cost[0, 1] = 1 # You can access the map array via this attribute.
>>> print(astar.get_path(0, 0, 2, 4))
[(0, 1), (0, 2), (0, 3), (1, 4), (2, 4)]

# Create a pathfinder from an edge_cost function.
# Calling Python functions from C is known to be very slow.
>>> def edge_cost(my_x, my_y, dest_x, dest_y):
...     return dungeon[dest_x, dest_y]
...
>>> dijkstra = tcod.path.Dijkstra(
...     tcod.path.EdgeCostCallback(edge_cost, dungeon.shape),
...     )
...
>>> dijkstra.set_goal(0, 0)
>>> print(dijkstra.get_path(2, 4))
[(0, 1), (0, 2), (0, 3), (1, 4), (2, 4)]
```

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.
`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. A list of points, or an empty list if there is no valid path. List[Tuple[int, int]]
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.
`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`[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.ndarray) → tcod.path.NodeCostArray[source]

Validate a numpy array and setup a C callback.

`tcod.path.``dijkstra2d`(distance: numpy.array, cost: numpy.array, cardinal: Optional[int], diagonal: Optional[int]) → None[source]

Return the computed distance of all nodes on a 2D Dijkstra grid.

distance is an input/output 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. This array is modified in-place.

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.

Example

```>>> import numpy as np
>>> import tcod.path
>>> 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)
>>> 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]
```

New in version 11.2.

`tcod.path.``hillclimb2d`(distance: numpy.array, start: Tuple[int, int], cardinal: bool, diagonal: bool) → numpy.array[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.

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.

`tcod.path.``maxarray`(shape: Tuple[int, ...], dtype: Any = <class 'int'>, order: str = 'C') → numpy.array[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`.