Source code for pathfinding3d.core.heap

"""
Simple heap with ordering and removal.
Inspired from https://github.com/brean/python-pathfinding/pull/54
Original author: https://github.com/peterchenadded
"""
import heapq
from typing import Callable, Union

from .grid import Grid
from .node import GridNode
from .world import World


[docs]class SimpleHeap: """ A simple implementation of a heap data structure optimized for pathfinding. It maintains an open list of nodes, a status for each node, and a function to retrieve nodes. """
[docs] def __init__(self, node: GridNode, grid: Union[Grid, World]): """ Initializes the SimpleHeap with a given node and grid. Parameters ---------- node : GridNode The initial node to be added to the heap. This node should have an 'f' attribute representing its cost. grid : Union[Grid, World] The grid in which the nodes are located. """ self.grid = grid self._get_node_tuple = self._determine_node_retrieval_function() self._get_node = self._determine_node_function() self.open_list = [self._get_node_tuple(node, 0)] self.removed_node_tuples = set() self.heap_order = {} self.number_pushed = 0
[docs] def _determine_node_retrieval_function(self) -> Callable: """ Determines the node retrieval function based on the type of grid. Returns ------- function A function that takes a node tuple and returns the corresponding node. Raises ------ ValueError If the grid is not of type Grid or World. """ if isinstance(self.grid, Grid): return lambda node, heap_order: (node.f, heap_order, *node.identifier) if isinstance(self.grid, World): return lambda node, heap_order: (node.f, heap_order, *node.identifier) raise ValueError("Unsupported grid type")
[docs] def _determine_node_function(self) -> Callable: """ Determines the node function based on the type of grid. Returns ------- function A function that takes a node tuple and returns the corresponding node. Raises ------ ValueError If the grid is not of type Grid or World. """ if isinstance(self.grid, Grid): return lambda node_tuple: self.grid.node(*node_tuple[2:]) if isinstance(self.grid, World): return lambda node_tuple: self.grid.grids[node_tuple[5]].node(*node_tuple[2:5]) raise ValueError("Unsupported grid type")
[docs] def pop_node(self) -> GridNode: """ Pops the node with the lowest cost from the heap. Returns ------- GridNode The node with the lowest cost. """ node_tuple = heapq.heappop(self.open_list) while node_tuple in self.removed_node_tuples: node_tuple = heapq.heappop(self.open_list) return self._get_node(node_tuple)
[docs] def push_node(self, node: GridNode): """ Pushes a node to the heap. Parameters ---------- node : GridNode The node to be pushed to the heap. """ self.number_pushed = self.number_pushed + 1 node_tuple = self._get_node_tuple(node, self.number_pushed) self.heap_order[node.identifier] = self.number_pushed heapq.heappush(self.open_list, node_tuple)
[docs] def remove_node(self, node: GridNode, old_f: float): """ Remove the node from the heap. This just stores it in a set and we just ignore the node if it does get popped from the heap. Parameters ---------- node : GridNode The node to be removed from the heap. old_f: float The old cost of the node. """ heap_order = self.heap_order[node.identifier] node_tuple = self._get_node_tuple(node, heap_order) self.removed_node_tuples.add(node_tuple)
def __len__(self) -> int: """ Returns the length of the heap. Returns ------- int The length of the heap. """ return len(self.open_list)