Source code for pathfinding3d.finder.a_star

from typing import Callable, List, Optional, Tuple, Union

from ..core.diagonal_movement import DiagonalMovement
from ..core.grid import Grid
from ..core.heuristic import manhattan, octile
from ..core.node import GridNode
from ..core.util import backtrace, bi_backtrace
from .finder import BY_END, MAX_RUNS, TIME_LIMIT, Finder


[docs]class AStarFinder(Finder):
[docs] def __init__( self, heuristic: Optional[Callable] = None, weight: int = 1, diagonal_movement: int = DiagonalMovement.never, time_limit: float = TIME_LIMIT, max_runs: Union[int, float] = MAX_RUNS, ): """ Find shortest path using A* algorithm 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) 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. """ super().__init__( heuristic=heuristic, weight=weight, diagonal_movement=diagonal_movement, time_limit=time_limit, max_runs=max_runs, ) if not heuristic: if diagonal_movement == DiagonalMovement.never: self.heuristic = manhattan else: # When diagonal movement is allowed the manhattan heuristic is # not admissible it should be octile instead self.heuristic = octile
[docs] def check_neighbors( self, start: GridNode, end: GridNode, grid: Grid, open_list: List, open_value: int = 1, backtrace_by=None, ) -> Optional[List[GridNode]]: """ 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 Returns ------- Optional[List[GridNode]] path """ # pop node with minimum 'f' value node = open_list.pop_node() node.closed = True # if reached the end position, construct the path and return it # (ignored for bi-directional a*, there we look for a neighbor that is # part of the oncoming path) if not backtrace_by and node == end: return backtrace(end) # get neighbors of the current node neighbors = self.find_neighbors(grid, node) for neighbor in neighbors: if neighbor.closed: # already visited last minimum f value continue if backtrace_by and neighbor.opened == backtrace_by: # found the oncoming path if backtrace_by == BY_END: return bi_backtrace(node, neighbor) return bi_backtrace(neighbor, node) # check if the neighbor has not been inspected yet, or # can be reached with smaller cost from the current node self.process_node(grid, neighbor, node, end, open_list, open_value) # the end has not been reached (yet) keep the find_path loop running return None
[docs] def find_path(self, start: GridNode, end: GridNode, grid: Grid) -> Tuple[List, int]: """ Find a path from start to end node on grid using the A* algorithm Parameters ---------- start : GridNode start node end : GridNode end node grid : Grid grid that stores all possible steps/tiles as 3D-list Returns ------- Tuple[List, int] path, number of iterations """ start.g = 0 start.f = 0 return super().find_path(start, end, grid)