Source code for pathfinding3d.finder.theta_star

import logging
from typing import Callable, List, Union

from ..core.diagonal_movement import DiagonalMovement
from ..core.grid import Grid
from ..core.node import GridNode
from ..core.util import line_of_sight
from .a_star import AStarFinder
from .finder import MAX_RUNS, TIME_LIMIT


[docs]class ThetaStarFinder(AStarFinder):
[docs] def __init__( self, heuristic: Callable = None, weight: int = 1, diagonal_movement: int = DiagonalMovement.always, time_limit: float = TIME_LIMIT, max_runs: Union[int, float] = MAX_RUNS, ): """ Find shortest path using Theta* algorithm Diagonal movement is forced to always. Not weighted. 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. """ if diagonal_movement != DiagonalMovement.always: logging.warning("Diagonal movement is forced to always for Theta*") diagonal_movement = DiagonalMovement.always super().__init__( heuristic=heuristic, weight=weight, diagonal_movement=diagonal_movement, time_limit=time_limit, max_runs=max_runs, ) self.weighted = False
[docs] def process_node( self, grid: Grid, node: GridNode, parent: GridNode, end: GridNode, open_list: List, open_value: int = 1, ): """ Check if we can reach the grandparent node directly from the current node and if so, skip the parent. Parameters ---------- grid : Grid grid that stores all possible steps/tiles as 3D-list node : GridNode the node we like to test 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 for line of sight to the grandparent if parent and parent.parent and parent.parent.grid_id == node.grid_id: grid_to_use = grid.grids[node.grid_id] if hasattr(grid, "grids") else grid if line_of_sight(grid_to_use, node, parent.parent): ng = parent.parent.g + grid.calc_cost(parent.parent, node, self.weighted) if not node.opened or ng < node.g: old_f = node.f node.g = ng node.h = node.h or self.apply_heuristic(node, end) node.f = node.g + node.h node.parent = parent.parent if not node.opened: open_list.push_node(node) node.opened = open_value else: open_list.remove_node(node, old_f) open_list.push_node(node) else: super().process_node(grid, node, parent, end, open_list) else: super().process_node(grid, node, parent, end, open_list)