pathfinding3d.finder.finder module

exception pathfinding3d.finder.finder.ExecutionTimeException(message)

Bases: Exception

__init__(message)

args

with_traceback()

Exception.with_traceback(tb) – set self.__traceback__ to tb and return self.

exception pathfinding3d.finder.finder.ExecutionRunsException(message)

Bases: Exception

__init__(message)

args

with_traceback()

Exception.with_traceback(tb) – set self.__traceback__ to tb and return self.

class pathfinding3d.finder.finder.Finder(heuristic=None, weight=1, diagonal_movement=DiagonalMovement.never, weighted=True, time_limit=TIME_LIMIT, max_runs=MAX_RUNS)

Bases: object

Parameters:

• heuristic (Callable | None) –

• weight (int) –

• diagonal_movement (int) –

• weighted (bool) –

• time_limit (float) –

• max_runs (int | float) –

__init__(heuristic=None, weight=1, diagonal_movement=DiagonalMovement.never, weighted=True, time_limit=TIME_LIMIT, max_runs=MAX_RUNS)

Find shortest path

Parameters:

• heuristic (Callable) – heuristic used to calculate distance of 2 points

• weight (int) – weight for the edges

• diagonal_movement (int) – if diagonal movement is allowed (see enum in diagonal_movement)

• weighted (the algorithm supports weighted nodes) – (should be True for A* and Dijkstra)

• time_limit (float) – max. runtime in seconds

• max_runs (int) – max. amount of tries until we abort the search (optional, only if we enter huge grids and have time constrains) <=0 means there are no constrains and the code might run on any large map.

apply_heuristic(node_a, node_b, heuristic=None)

Helper function to apply heuristic

Parameters:

• node_a (GridNode) – first node

• node_b (GridNode) – second node

• heuristic (Callable) – heuristic used to calculate distance of 2 points

Returns:

heuristic value

Return type:

float

find_neighbors(grid, node, diagonal_movement=None)

Find neighbor, same for Djikstra, A*, Bi-A*, IDA*

Parameters:

• grid (Grid) – grid that stores all possible steps/tiles as 3D-list

• node (GridNode) – node to find neighbors for

• diagonal_movement (int) – if diagonal movement is allowed (see enum in diagonal_movement)

Returns:

list of neighbors

Return type:

List[GridNode]

keep_running()

Check, if we run into time or iteration constrains.

Raises:

• ExecutionTimeException – if we run into a time constrain

• ExecutionRunsException – if we run into a iteration constrain

process_node(grid, node, parent, end, open_list, open_value=1)

We check if the given node is part of the path by calculating its cost and add or remove it from our path

Parameters:

• grid (Grid) – grid that stores all possible steps/tiles as 3D-list

• node (GridNode) – the node we like to test (the neighbor in A* or jump-node in JumpPointSearch)

• parent (GridNode) – the parent node (of the current node we like to test)

• end (GridNode) – the end point to calculate the cost of the path

• open_list (List) – the list that keeps track of our current path

• open_value (bool) – needed if we like to set the open list to something else than True (used for bi-directional algorithms)

check_neighbors(start, end, grid, open_list, open_value=1, backtrace_by=None)

find next path segment based on given node (or return path if we found the end)

Parameters:

• start (GridNode) – start node

• end (GridNode) – end node

• grid (Grid) – grid that stores all possible steps/tiles as 3D-list

• open_list (List) – stores nodes that will be processed next

• open_value (int) –

Returns:

path

Return type:

Optional[List[GridNode]]

find_path(start, end, grid)

Find a path from start to end node on grid by iterating over all neighbors of a node (see check_neighbors)

Parameters:

• start (GridNode) – start node

• end (GridNode) – end node

• grid (Grid) – grid that stores all possible steps/tiles as 3D-list (can be a list of grids)

Returns:

path, number of iterations

Return type:

Tuple[List, int]