Source code for pathfinding3d.finder.ida_star

import time
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 .finder import MAX_RUNS, TIME_LIMIT, Finder


[docs]class IDAStarFinder(Finder): """ Iterative Deeping A Star (IDA*) path-finder. Recursion based on: http://www.apl.jhu.edu/~hall/AI-Programming/IDA-Star.html Path retracing based on: V. Nageshwara Rao, Vipin Kumar and K. Ramesh "A Parallel Implementation of Iterative-Deeping-A*", January 1987. ftp://ftp.cs.utexas.edu/.snapshot/hourly.1/pub/AI-Lab/tech-reports/ UT-AI-TR-87-46.pdf based on the JavaScript implementation by Gerard Meier (www.gerardmeier.com) """
[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, track_recursion: bool = True, ): """ Find shortest path using IDA* 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. track_recursion : bool if we should track recursion """ super().__init__( heuristic=heuristic, weight=weight, diagonal_movement=diagonal_movement, weighted=False, time_limit=time_limit, max_runs=max_runs, ) self.track_recursion = track_recursion 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 self.nodes_visited: int
[docs] def search( self, node: GridNode, g: float, cutoff: float, path: List[GridNode], depth: int, end: GridNode, grid: Grid, ) -> Union[float, GridNode]: """ Recursive IDA* search implementation Parameters ---------- node : GridNode current node g : float cost from start to current node cutoff : float cutoff cost path : List[GridNode] path depth : int current depth end : GridNode end node grid : Grid grid that stores all possible steps/tiles as 3D-list Returns ------- Union[float, GridNode] cutoff cost or end node """ self.runs += 1 self.keep_running() self.nodes_visited += 1 f = g + self.apply_heuristic(node, end) * self.weight # We've searched too deep for this iteration. if f > cutoff: return f if node == end: if len(path) < depth: path += [None] * (depth - len(path) + 1) path[depth] = node return node neighbors = self.find_neighbors(grid, node) # Sort the neighbors, gives nicer paths. But, this deviates # from the original algorithm - so I left it out # TODO: make this an optional parameter # def sort_neighbors(a, b): # return self.apply_heuristic(a, end) - \ # self.apply_heuristic(b, end) # sorted(neighbors, sort_neighbors) min_t = float("inf") for neighbor in neighbors: if self.track_recursion: # Retain a copy for visualisation. Due to recursion, this # node may be part of other paths too. neighbor.retain_count += 1 neighbor.tested = True t = self.search( neighbor, g + grid.calc_cost(node, neighbor), cutoff, path, depth + 1, end, grid, ) if isinstance(t, GridNode): if len(path) < depth: path += [None] * (depth - len(path) + 1) path[depth] = node return t # Decrement count, then determine whether it's actually closed. if self.track_recursion: neighbor.retain_count -= 1 if neighbor.retain_count == 0: neighbor.tested = False if t < min_t: min_t = t return min_t
[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 IDA* 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 """ self.start_time = time.time() # execution time limitation self.runs = 0 # count number of iterations self.nodes_visited = 0 # for statistics # initial search depth, given the typical heuristic contraints, # there should be no cheaper route possible. cutoff = self.apply_heuristic(start, end) while True: path = [] # search till cut-off depth: t = self.search(start, 0, cutoff, path, 0, end, grid) if isinstance(t, bool) and not t: # only when an error occured we return "False" break # If t is a node, it's also the end node. Route is now # populated with a valid path to the end node. if isinstance(t, GridNode): return ( [(node.x, node.y, node.z, node.grid_id) for node in path], self.runs, ) # Try again, this time with a deeper cut-off. The t score # is the closest we got to the end node. cutoff = t return [], self.runs