# Source code for 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)]

.. versionchanged:: 5.0
All path-finding functions now respect the NumPy array shape (if a NumPy
array is used.)
"""
from typing import Any, Callable, List, Optional, Tuple, Union  # noqa: F401

import numpy as np

from tcod.loader import lib, ffi
from tcod._internal import _check
import tcod.map  # noqa: F401

@ffi.def_extern()  # type: ignore
def _pycall_path_old(x1: int, y1: int, x2: int, y2: int, handle: Any) -> float:
"""libtcodpy style callback, needs to preserve the old userData issue."""
func, userData = ffi.from_handle(handle)
return func(x1, y1, x2, y2, userData)  # type: ignore

@ffi.def_extern()  # type: ignore
def _pycall_path_simple(
x1: int, y1: int, x2: int, y2: int, handle: Any
) -> float:
"""Does less and should run faster, just calls the handle function."""
return ffi.from_handle(handle)(x1, y1, x2, y2)  # type: ignore

@ffi.def_extern()  # type: ignore
def _pycall_path_swap_src_dest(
x1: int, y1: int, x2: int, y2: int, handle: Any
) -> float:
"""A TDL function dest comes first to match up with a dest only call."""
return ffi.from_handle(handle)(x2, y2, x1, y1)  # type: ignore

@ffi.def_extern()  # type: ignore
def _pycall_path_dest_only(
x1: int, y1: int, x2: int, y2: int, handle: Any
) -> float:
"""A TDL function which samples the dest coordinate only."""
return ffi.from_handle(handle)(x2, y2)  # type: ignore

def _get_pathcost_func(
name: str,
) -> Callable[[int, int, int, int, Any], float]:
"""Return a properly cast PathCostArray callback."""
return ffi.cast(  # type: ignore
)

class _EdgeCostFunc(object):
"""Generic edge-cost function factory.

`userdata` is the custom userdata to send to the C call.

`shape` is the maximum boundary for the algorithm.
"""

_CALLBACK_P = lib._pycall_path_old

def __init__(self, userdata: Any, shape: Tuple[int, int]) -> None:
self._userdata = userdata
self.shape = shape

def get_tcod_path_ffi(self) -> Tuple[Any, Any, Tuple[int, int]]:
"""Return (C callback, userdata handle, shape)"""
return self._CALLBACK_P, ffi.new_handle(self._userdata), self.shape

def __repr__(self) -> str:
return "%s(%r, shape=%r)" % (
self.__class__.__name__,
self._userdata,
self.shape,
)

[docs]class EdgeCostCallback(_EdgeCostFunc):
"""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.

.. versionchanged:: 5.0
Now only accepts a `shape` argument instead of `width` and `height`.
"""

_CALLBACK_P = lib._pycall_path_simple

def __init__(
self,
callback: Callable[[int, int, int, int], float],
shape: Tuple[int, int],
):
self.callback = callback
super(EdgeCostCallback, self).__init__(callback, shape)

[docs]class NodeCostArray(np.ndarray):  # type: ignore
"""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.
"""

_C_ARRAY_CALLBACKS = {
np.float32: ("float*", _get_pathcost_func("PathCostArrayFloat32")),
np.bool_: ("int8_t*", _get_pathcost_func("PathCostArrayInt8")),
np.int8: ("int8_t*", _get_pathcost_func("PathCostArrayInt8")),
np.uint8: ("uint8_t*", _get_pathcost_func("PathCostArrayUInt8")),
np.int16: ("int16_t*", _get_pathcost_func("PathCostArrayInt16")),
np.uint16: ("uint16_t*", _get_pathcost_func("PathCostArrayUInt16")),
np.int32: ("int32_t*", _get_pathcost_func("PathCostArrayInt32")),
np.uint32: ("uint32_t*", _get_pathcost_func("PathCostArrayUInt32")),
}

[docs]    def __new__(cls, array: np.ndarray) -> "NodeCostArray":
"""Validate a numpy array and setup a C callback."""
self = np.asarray(array).view(cls)
return self  # type: ignore

def __repr__(self) -> str:
return "%s(%r)" % (
self.__class__.__name__,
repr(self.view(np.ndarray)),
)

def get_tcod_path_ffi(self) -> Tuple[Any, Any, Tuple[int, int]]:
if len(self.shape) != 2:
raise ValueError(
"Array must have a 2d shape, shape is %r" % (self.shape,)
)
if self.dtype.type not in self._C_ARRAY_CALLBACKS:
raise ValueError(
"dtype must be one of %r, dtype is %r"
% (self._C_ARRAY_CALLBACKS.keys(), self.dtype.type)
)

array_type, callback = self._C_ARRAY_CALLBACKS[self.dtype.type]
userdata = ffi.new(
"struct PathCostArray*",
(ffi.cast("char*", self.ctypes.data), self.strides),
)
return callback, userdata, self.shape

class _PathFinder(object):
"""A class sharing methods used by AStar and Dijkstra."""

def __init__(self, cost: Any, diagonal: float = 1.41):
self.cost = cost
self.diagonal = diagonal
self._path_c = None  # type: Any
self._callback = self._userdata = None

if hasattr(self.cost, "map_c"):
self.shape = self.cost.width, self.cost.height
self._path_c = ffi.gc(
self._path_new_using_map(self.cost.map_c, diagonal),
self._path_delete,
)
return

if not hasattr(self.cost, "get_tcod_path_ffi"):
assert not callable(self.cost), (
"Any callback alone is missing shape information. "
"Wrap your callback in tcod.path.EdgeCostCallback"
)
self.cost = NodeCostArray(self.cost)

(
self._callback,
self._userdata,
self.shape,
) = self.cost.get_tcod_path_ffi()
self._path_c = ffi.gc(
self._path_new_using_function(
self.cost.shape[0],
self.cost.shape[1],
self._callback,
self._userdata,
diagonal,
),
self._path_delete,
)

def __repr__(self) -> str:
return "%s(cost=%r, diagonal=%r)" % (
self.__class__.__name__,
self.cost,
self.diagonal,
)

def __getstate__(self) -> Any:
state = self.__dict__.copy()
del state["_path_c"]
del state["shape"]
del state["_callback"]
del state["_userdata"]
return state

def __setstate__(self, state: Any) -> None:
self.__dict__.update(state)
self.__init__(self.cost, self.diagonal)  # type: ignore

_path_new_using_map = lib.TCOD_path_new_using_map
_path_new_using_function = lib.TCOD_path_new_using_function
_path_delete = lib.TCOD_path_delete

[docs]class AStar(_PathFinder):
"""
Args:
cost (Union[tcod.map.Map, numpy.ndarray, Any]):
diagonal (float): Multiplier for diagonal movement.
A value of 0 will disable diagonal movement entirely.
"""

[docs]    def get_path(
self, start_x: int, start_y: int, goal_x: int, goal_y: int
) -> List[Tuple[int, int]]:
"""Return a list of (x, y) steps to reach the goal point, if possible.

Args:
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:
List[Tuple[int, int]]:
A list of points, or an empty list if there is no valid path.
"""
lib.TCOD_path_compute(self._path_c, start_x, start_y, goal_x, goal_y)
path = []
x = ffi.new("int[2]")
y = x + 1
while lib.TCOD_path_walk(self._path_c, x, y, False):
path.append((x[0], y[0]))
return path

[docs]class Dijkstra(_PathFinder):
"""
Args:
cost (Union[tcod.map.Map, numpy.ndarray, Any]):
diagonal (float): Multiplier for diagonal movement.
A value of 0 will disable diagonal movement entirely.
"""

_path_new_using_map = lib.TCOD_dijkstra_new
_path_new_using_function = lib.TCOD_dijkstra_new_using_function
_path_delete = lib.TCOD_dijkstra_delete

[docs]    def set_goal(self, x: int, y: int) -> None:
"""Set the goal point and recompute the Dijkstra path-finder.
"""
lib.TCOD_dijkstra_compute(self._path_c, x, y)

[docs]    def get_path(self, x: int, y: int) -> List[Tuple[int, int]]:
"""Return a list of (x, y) steps to reach the goal point, if possible.
"""
lib.TCOD_dijkstra_path_set(self._path_c, x, y)
path = []
pointer_x = ffi.new("int[2]")
pointer_y = pointer_x + 1
while lib.TCOD_dijkstra_path_walk(self._path_c, pointer_x, pointer_y):
path.append((pointer_x[0], pointer_y[0]))
return path

_INT_TYPES = {
np.int8: lib.np_int8,
np.int16: lib.np_int16,
np.int32: lib.np_int32,
np.int64: lib.np_int64,
np.uint8: lib.np_uint8,
np.uint16: lib.np_uint16,
np.uint32: lib.np_uint32,
np.uint64: lib.np_uint64,
}

[docs]def maxarray(
shape: Tuple[int, ...], dtype: Any = int, order: str = "C"
) -> np.array:
"""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 :any:`dijkstra2d`.
"""
return np.full(shape, np.iinfo(dtype).max, dtype, order)

def _export(array: np.array) -> Any:
"""Convert a NumPy array into a ctype object."""
return ffi.new(
"struct NArray4*",
(
_INT_TYPES[array.dtype.type],
ffi.cast("void*", array.ctypes.data),
array.shape,
array.strides,
),
)

[docs]def dijkstra2d(
distance: np.array,
cost: np.array,
cardinal: Optional[int],
diagonal: Optional[int],
) -> None:
"""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]

"""
dist = distance
cost = np.asarray(cost)
if dist.shape != cost.shape:
raise TypeError(
"distance and cost must have the same shape %r != %r"
% (dist.shape, cost.shape)
)
if cardinal is None:
cardinal = 0
if diagonal is None:
diagonal = 0
_check(lib.dijkstra2d(_export(dist), _export(cost), cardinal, diagonal))

[docs]def hillclimb2d(
distance: np.array, start: Tuple[int, int], cardinal: bool, diagonal: bool
) -> np.array:
"""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 :any:`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.

"""
x, y = start
dist = np.asarray(distance)
if not (0 <= x < dist.shape[0] and 0 <= y < dist.shape[1]):
raise IndexError(
"Starting point %r not in shape %r" % (start, dist.shape)
)
c_dist = _export(dist)
length = _check(
lib.hillclimb2d(c_dist, x, y, cardinal, diagonal, ffi.NULL)
)
path = np.ndarray((length, 2), dtype=np.intc)
c_path = ffi.cast("int*", path.ctypes.data)
_check(lib.hillclimb2d(c_dist, x, y, cardinal, diagonal, c_path))
return path
```