Source code for pathfinding3d.finder.msp

import time
from collections import deque, namedtuple
from typing import List, Tuple

from ..core import heuristic
from ..core.grid import Grid
from ..core.heap import SimpleHeap
from ..core.node import GridNode
from ..finder.finder import Finder


[docs]class MinimumSpanningTree(Finder): """ Minimum Spanning Tree implementation by Brad Beattie (see https://github.com/brean/python-pathfinding/issues/18) The wikipedia page has a nice description about MSP: https://en.wikipedia.org/wiki/Minimum_spanning_tree """
[docs] def __init__(self, *args, **kwargs): super().__init__(*args, **kwargs) self.heuristic = heuristic.null
[docs] def tree(self, grid: Grid, start: GridNode) -> List[GridNode]: """ Returns a list of nodes that are part of the minimum spanning tree of the grid. Parameters ---------- grid : Grid grid that stores all possible steps/tiles as 3D-list start : GridNode start node Returns ------- List[GridNode] """ return list(self.itertree(grid, start))
[docs] def itertree(self, grid: Grid, start: GridNode): """ Returns a generator that yields nodes that are part of the minimum spanning tree of the grid. Parameters ---------- grid : Grid grid that stores all possible steps/tiles as 3D-list start : GridNode start node """ # Finder.process_node requires an end node, which we don't have. # The following value tricks the call to Finder.apply_heuristic. # Though maybe we want to generate a limited spanning tree that # trends in a certain direction? In which case we'd want a more # nuanced solution. end = namedtuple("FakeNode", ["x", "y", "z"])(-1, -1, -1) start.opened = True open_list = SimpleHeap(start, grid) while len(open_list) > 0: self.runs += 1 self.keep_running() node = open_list.pop_node() node.closed = True yield node neighbors = self.find_neighbors(grid, node) for neighbor in neighbors: if not neighbor.closed: self.process_node(grid, neighbor, node, end, open_list, open_value=True)
[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 Minimum Spanning Tree 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 for node in self.itertree(grid, start): if node == end: path = deque() step = node while step.parent: path.appendleft(step) step = step.parent path.appendleft(step) return path, self.runs return [], self.runs