pathfinding3d.finder.ida_star module
- class pathfinding3d.finder.ida_star.IDAStarFinder(heuristic=None, weight=1, diagonal_movement=DiagonalMovement.never, time_limit=TIME_LIMIT, max_runs=MAX_RUNS, track_recursion=True)[source]
Bases:
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)
- Parameters:
- __init__(heuristic=None, weight=1, diagonal_movement=DiagonalMovement.never, time_limit=TIME_LIMIT, max_runs=MAX_RUNS, track_recursion=True)[source]
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
- search(node, g, cutoff, path, depth, end, grid)[source]
Recursive IDA* search implementation
- Parameters:
- Returns:
cutoff cost or end node
- Return type:
- apply_heuristic(node_a, node_b, heuristic=None)
Helper function to apply heuristic
- 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)
- find_neighbors(grid, node, diagonal_movement=None)
Find neighbor, same for Djikstra, A*, Bi-A*, IDA*
- find_path(start, end, grid)[source]
Find a path from start to end node on grid using the IDA* algorithm
- 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)