From 3d1b65d6859a4a7497b2c0e7c3d5a8e6ee3df28a Mon Sep 17 00:00:00 2001 From: Axy Date: Mon, 16 Mar 2026 20:01:58 +0100 Subject: [PATCH] Finished network tracker, need to improve perf --- __main__.py | 152 +++++++++----------- amazeing/maze_class/maze.py | 31 ++-- amazeing/maze_class/maze_network_tracker.py | 136 ++++++++++++------ amazeing/maze_make_empty.py | 2 +- amazeing/maze_make_perfect.py | 10 +- amazeing/utils/avl.py | 30 +++- example.conf | 4 +- 7 files changed, 211 insertions(+), 154 deletions(-) diff --git a/__main__.py b/__main__.py index 082ffa2..9b35b9c 100644 --- a/__main__.py +++ b/__main__.py @@ -11,23 +11,11 @@ import random from amazeing.config.config_parser import Config -from amazeing.maze_class import maze_network_tracker -from amazeing.maze_class.maze_coords import Cardinal, CellCoord, WallCoord +from amazeing.maze_class.maze_network_tracker import MazeNetworkTracker +from amazeing.maze_class.maze_coords import Cardinal, CellCoord +from amazeing.maze_class.maze_dirty_tracker import MazeDirtyTracker from amazeing.maze_display.TTYdisplay import TileCycle, TileMaps, extract_pairs from amazeing.maze_display.backend import CloseRequested, IVec2 -from amazeing.utils import AVLTree - -forest = maze_network_tracker.DualForest() -for wall in CellCoord(0, 0).walls(): - forest.fill_wall(wall) -for wall in CellCoord(1, 0).walls(): - forest.fill_wall(wall) -for wall in CellCoord(3, 0).walls(): - forest.fill_wall(wall) - -print(forest) - -exit(0) config = Config.parse(open("./example.conf").read()) @@ -38,6 +26,8 @@ dims = IVec2(config.width, config.height) maze = Maze(dims) +dirty_tracker = MazeDirtyTracker(maze) + maze.outline() excluded = set() @@ -71,8 +61,8 @@ path = TileCycle(tilemaps.path, backend.map_style_cb()) def clear_backend() -> None: backend.set_style(empty.curr_style()) - for wall in maze.walls_dirty(): - if maze.get_wall(wall).is_full(): + for wall in dirty_tracker.curr_dirty(): + if maze.get_wall(wall): continue for tile in wall.tile_coords(): backend.draw_tile(tile) @@ -80,22 +70,22 @@ def clear_backend() -> None: def display_maze(maze: Maze) -> None: clear_backend() - pathfind() + # pathfind() backend.set_style(full.curr_style()) rewrites = { - wall for wall in maze.walls_dirty() if maze.get_wall(wall).is_full() + wall for wall in dirty_tracker.curr_dirty() if maze.get_wall(wall) } | { e - for wall in maze.walls_dirty() + for wall in dirty_tracker.curr_dirty() for e in wall.neighbours() - if maze.check_coord(e) and maze.get_wall(e).is_full() + if maze.check_coord(e) and maze.get_wall(e) } for wall in rewrites: for pixel in wall.tile_coords(): backend.draw_tile(pixel) - maze.clear_dirty() + dirty_tracker.clear() backend.present() poll_events(0) @@ -138,67 +128,67 @@ def elipse_manhattan(a: IVec2, b: IVec2, a2: IVec2, b2: IVec2) -> int: ) -def pathfind_necessary() -> bool: - entry = config.entry - exit = config.exit - if entry is None or exit is None: - return False - if len(prev_solution) == 0: - return True - if any( - map( - lambda e: e in maze.walls_dirty() and maze.get_wall(e).is_full(), - Cardinal.path_to_walls(prev_solution, CellCoord(entry)), - ) - ): - return True - if any( - map( - lambda e: elipse_manhattan(entry, exit, *e.neighbour_cells()) - < len(prev_solution), - filter( - lambda wall: not maze.get_wall(wall).is_full(), - maze.walls_dirty(), - ), - ) - ): - return True - return False - - -def pathfind() -> None: - if not pathfind_necessary(): - return - if config.entry is None or config.exit is None: - return - solution = maze.pathfind(CellCoord(config.entry), CellCoord(config.exit)) - if solution is None or prev_solution == solution: - return - prev_tiles = Cardinal.path_to_tiles(prev_solution, CellCoord(config.entry)) - tiles = Cardinal.path_to_tiles(solution, CellCoord(config.entry)) - backend.set_style(empty.curr_style()) - for tile in prev_tiles: - backend.draw_tile(tile) - backend.set_style(path.curr_style()) - for tile in tiles: - backend.draw_tile(tile) - backend.present() - prev_solution.clear() - prev_solution.extend(solution) - - -maze_make_perfect(maze, callback=display_maze) -maze_make_pacman(maze, walls_const, callback=display_maze) - - -pathfind() - - -while True: - maze_make_perfect(maze, callback=display_maze) +# def pathfind_necessary() -> bool: +# entry = config.entry +# exit = config.exit +# if entry is None or exit is None: +# return False +# if len(prev_solution) == 0: +# return True +# if any( +# map( +# lambda e: e in dirty_tracker.curr_dirty() and maze.get_wall(e), +# Cardinal.path_to_walls(prev_solution, CellCoord(entry)), +# ) +# ): +# return True +# if any( +# map( +# lambda e: elipse_manhattan(entry, exit, *e.neighbour_cells()) +# < len(prev_solution), +# filter( +# lambda wall: not maze.get_wall(wall), +# dirty_tracker.curr_dirty(), +# ), +# ) +# ): +# return True +# return False +# +# +# def pathfind() -> None: +# if not pathfind_necessary(): +# return +# if config.entry is None or config.exit is None: +# return +# solution = maze.pathfind(CellCoord(config.entry), CellCoord(config.exit)) +# if solution is None or prev_solution == solution: +# return +# prev_tiles = Cardinal.path_to_tiles(prev_solution, CellCoord(config.entry)) +# tiles = Cardinal.path_to_tiles(solution, CellCoord(config.entry)) +# backend.set_style(empty.curr_style()) +# for tile in prev_tiles: +# backend.draw_tile(tile) +# backend.set_style(path.curr_style()) +# for tile in tiles: +# backend.draw_tile(tile) +# backend.present() +# prev_solution.clear() +# prev_solution.extend(solution) + + +network_tracker = MazeNetworkTracker(maze) +maze_make_perfect(maze, network_tracker, callback=display_maze) +# maze_make_pacman(maze, walls_const, callback=display_maze) + + +# pathfind() + +while False: + maze_make_perfect(maze, network_tracker, callback=display_maze) # poll_events(200) maze_make_pacman(maze, walls_const, callback=display_maze) # maze_make_empty(maze, walls_const, callback=display_maze) # poll_events(200) - maze._rebuild() + # maze._rebuild() poll_events() diff --git a/amazeing/maze_class/maze.py b/amazeing/maze_class/maze.py index 032d7ea..71b7166 100644 --- a/amazeing/maze_class/maze.py +++ b/amazeing/maze_class/maze.py @@ -14,31 +14,20 @@ class Maze: def __init__(self, dims: IVec2) -> None: self.__dims = dims self.observers: set[MazeObserver] = set() - # list of lines - self.horizontal: list[list[bool]] = [ - [False for _ in range(0, self.__dims.x)] - for _ in range(0, self.__dims.y + 1) - ] - # list of lines - self.vertical: list[list[bool]] = [ - [False for _ in range(0, self.__dims.y)] - for _ in range(0, self.__dims.x + 1) - ] + self.__walls_full: dict[WallCoord, None] = {} def get_wall(self, coord: WallCoord) -> bool: - if coord.orientation == Orientation.HORIZONTAL: - return self.horizontal[coord.a][coord.b] - return self.vertical[coord.a][coord.b] + return coord in self.__walls_full - def set_wall(self, coord: WallCoord, value: bool) -> None: - wall = self.get_wall(coord) - if wall != value: - if coord.orientation == Orientation.HORIZONTAL: - self.horizontal[coord.a][coord.b] = value - self.vertical[coord.a][coord.b] = value + def set_wall(self, wall: WallCoord, value: bool) -> None: + if self.get_wall(wall) != value: + if value: + self.__walls_full[wall] = None + else: + self.__walls_full.pop(wall) for observer in self.observers: - observer(coord) + observer(wall) def all_walls(self) -> Generator[WallCoord]: for orientation, a_count, b_count in [ @@ -90,7 +79,7 @@ class Maze: self.set_wall(WallCoord(orientation, a, b), True) def walls_full(self) -> Iterable[WallCoord]: - return filter(lambda w: self.get_wall(w), self.all_walls()) + return self.__walls_full def walls_empty(self) -> Iterable[WallCoord]: return filter(lambda w: not self.get_wall(w), self.all_walls()) diff --git a/amazeing/maze_class/maze_network_tracker.py b/amazeing/maze_class/maze_network_tracker.py index 5f6ad30..14c1e0a 100644 --- a/amazeing/maze_class/maze_network_tracker.py +++ b/amazeing/maze_class/maze_network_tracker.py @@ -1,13 +1,10 @@ from amazeing.maze_class.maze import Maze from amazeing.maze_class.maze_coords import ( - Cardinal, - CellCoord, SplitWall, WallCoord, split_wall_ccw, split_wall_opposite, ) -from amazeing.utils import BiMap from amazeing.utils import AVLTree, AVLLeaf @@ -36,63 +33,77 @@ class DualForest: + f"{self.__trees}\n revmap:\n{self.__revmap}\n" ) + def find_split( + self, + split_wall: SplitWall, + ) -> SplitWall | None: + split_wall = split_wall_opposite(split_wall) + for _ in range(3): + split_wall = split_wall_ccw(split_wall) + if split_wall in self.__revmap: + return split_wall + return None + def fill_wall(self, wall: WallCoord) -> None: - lhs, rhs = wall.to_split_wall() - if lhs in self.__revmap or rhs in self.__revmap: + if self.get_wall(wall): return - a_tree = AVLTree() - b_tree = AVLTree() - self.__revmap[lhs] = a_tree.append(lhs) - self.__revmap[rhs] = b_tree.append(rhs) - - def find_split(split_wall: SplitWall) -> SplitWall | None: - split_wall = split_wall_opposite(split_wall) - for _ in range(3): - split_wall = split_wall_ccw(split_wall) - if split_wall in self.__revmap: - return split_wall - return None - - match (find_split(lhs), find_split(rhs)): + a_wall, b_wall = wall.to_split_wall() + a_tree = AVLTree[SplitWall]() + b_tree = AVLTree[SplitWall]() + self.__revmap[a_wall] = a_tree.append(a_wall) + self.__revmap[b_wall] = b_tree.append(b_wall) + + match (self.find_split(a_wall), self.find_split(b_wall)): case (None, None): a_tree.rjoin(b_tree) self.__trees.add(a_tree) case (None, b_split): - self.__trees.remove(self.__revmap[b_split].root()) - lhs, rhs = self.__revmap[b_split].split_up() + # mypy is stupid + if b_split is None: + raise Exception() + b_leaf = self.__revmap.pop(b_split) + self.__trees.remove(b_leaf.root()) + lhs, rhs = b_leaf.split_up() lhs.rjoin(a_tree) lhs.rjoin(b_tree) self.__revmap[b_split] = lhs.append(b_split) lhs.rjoin(rhs) self.__trees.add(lhs) case (a_split, None): - self.__trees.remove(self.__revmap[a_split].root()) - lhs, rhs = self.__revmap[a_split].split_up() + # mypy is stupid + if a_split is None: + raise Exception() + a_leaf = self.__revmap.pop(a_split) + self.__trees.remove(a_leaf.root()) + lhs, rhs = a_leaf.split_up() lhs.rjoin(b_tree) lhs.rjoin(a_tree) self.__revmap[a_split] = lhs.append(a_split) lhs.rjoin(rhs) self.__trees.add(lhs) case (a_split, b_split): - if ( - self.__revmap[a_split].root() - is self.__revmap[b_split].root() - ): - self.__trees.remove(self.__revmap[a_split].root()) - lhs, rhs = self.__revmap[a_split].split_up() + # mypy is stupid + if a_split is None or b_split is None: + raise Exception() + a_leaf, b_leaf = self.__revmap.pop(a_split), self.__revmap.pop( + b_split + ) + if a_leaf.root() is b_leaf.root(): + self.__trees.remove(a_leaf.root()) + lhs, rhs = a_leaf.split_up() lhs.rjoin(b_tree) self.__revmap[a_split] = rhs.prepend(a_split) rhs.ljoin(a_tree) rhs.rjoin(lhs) - lhs, rhs = self.__revmap[b_split].split_up() + lhs, rhs = b_leaf.split_up() self.__revmap[b_split] = rhs.prepend(b_split) self.__trees.add(lhs) self.__trees.add(rhs) else: - self.__trees.remove(self.__revmap[a_split].root()) - self.__trees.remove(self.__revmap[b_split].root()) - a_lhs, a_rhs = self.__revmap[a_split].split_up() - b_lhs, b_rhs = self.__revmap[b_split].split_up() + self.__trees.remove(a_leaf.root()) + self.__trees.remove(b_leaf.root()) + a_lhs, a_rhs = a_leaf.split_up() + b_lhs, b_rhs = b_leaf.split_up() self.__revmap[a_split] = a_rhs.prepend(a_split) self.__revmap[b_split] = b_rhs.prepend(b_split) res = a_lhs @@ -104,25 +115,66 @@ class DualForest: self.__trees.add(res) def empty_wall(self, wall: WallCoord) -> None: - pass + if not self.get_wall(wall): + return + a_wall, b_wall = wall.to_split_wall() + a_leaf, b_leaf = self.__revmap.pop(a_wall), self.__revmap.pop(b_wall) + if a_leaf.root() is b_leaf.root(): + self.__trees.remove(a_leaf.root()) + lhs, rhs = a_leaf.split_up() + rhs.rjoin(lhs) + a_res, b_res = b_leaf.split_up() + if a_res.height() > 0: + self.__trees.add(a_res) + if b_res.height() > 0: + self.__trees.add(b_res) + else: + self.__trees.remove(a_leaf.root()) + self.__trees.remove(b_leaf.root()) + a_lhs, a_rhs = a_leaf.split_up() + b_lhs, b_rhs = b_leaf.split_up() + res = AVLTree[SplitWall]() + res.rjoin(a_lhs) + res.rjoin(b_rhs) + res.rjoin(b_lhs) + res.rjoin(a_rhs) + if res.height() > 0: + self.__trees.add(res) + + def get_wall(self, wall: WallCoord) -> bool: + a_wall, b_wall = wall.to_split_wall() + return a_wall in self.__revmap and b_wall in self.__revmap + + def wall_bisects(self, wall: WallCoord) -> bool: + a_wall, b_wall = wall.to_split_wall() + a_split = self.find_split(a_wall) + b_split = self.find_split(b_wall) + if a_split is None or b_split is None: + return False + a_leaf, b_leaf = self.__revmap[a_split], self.__revmap[b_split] + if self.get_wall(wall): + return a_leaf.root() is not b_leaf.root() + else: + return a_leaf.root() is b_leaf.root() class MazeNetworkTracker: def __init__(self, maze: Maze) -> None: self.__maze: Maze = maze - self.__networks_wall: BiMap[NetworkID, WallCoord] = BiMap() - self.__networks_cell: BiMap[NetworkID, CellCoord] = BiMap() - - netid = NetworkID() - for cell in maze.all_cells(): - self.__networks_cell.add(netid, cell) + self.__forest: DualForest = DualForest() maze.observers.add(self.__observer) for wall in maze.walls_full(): self.__observer(wall) def __observer(self, wall: WallCoord) -> None: - return + if self.__maze.get_wall(wall): + self.__forest.fill_wall(wall) + else: + self.__forest.empty_wall(wall) + + def wall_bisects(self, wall: WallCoord) -> bool: + return self.__forest.wall_bisects(wall) def end(self): self.__maze.observers.discard(self.__observer) diff --git a/amazeing/maze_make_empty.py b/amazeing/maze_make_empty.py index 68f9808..336ac5b 100644 --- a/amazeing/maze_make_empty.py +++ b/amazeing/maze_make_empty.py @@ -12,5 +12,5 @@ def maze_make_empty( walls = [wall for wall in maze.walls_full() if wall not in walls_const] random.shuffle(walls) for wall in walls: - maze.set_wall(wall) + maze.set_wall(wall, False) callback(maze) diff --git a/amazeing/maze_make_perfect.py b/amazeing/maze_make_perfect.py index 282db0d..bfb629f 100644 --- a/amazeing/maze_make_perfect.py +++ b/amazeing/maze_make_perfect.py @@ -2,13 +2,17 @@ from typing import Callable from amazeing import Maze import random +from amazeing.maze_class.maze_network_tracker import MazeNetworkTracker + def maze_make_perfect( - maze: Maze, callback: Callable[[Maze], None] = lambda _: None + maze: Maze, + tracker: MazeNetworkTracker, + callback: Callable[[Maze], None] = lambda _: None, ) -> None: empty = list(maze.walls_empty()) random.shuffle(empty) for wall in empty: - if not maze.wall_bisects(wall): - maze.fill_wall(wall) + if not tracker.wall_bisects(wall): + maze.set_wall(wall, True) callback(maze) diff --git a/amazeing/utils/avl.py b/amazeing/utils/avl.py index 4f0c177..75c03ac 100644 --- a/amazeing/utils/avl.py +++ b/amazeing/utils/avl.py @@ -10,6 +10,10 @@ class Tree[T]: def __repr__(self) -> str: return f"{self.root}" if self.root is not None else "(empty)" + def validate(self) -> None: + if self.root is not None: + self.root.validate() + def append(self, value: T) -> "Leaf[T]": if self.root is None: leaf = Leaf(self, value) @@ -64,6 +68,8 @@ class Tree[T]: self.root = b def ljoin(self, lhs: "Tree[T]") -> None: + if self is lhs: + raise Exception("Cannot merge tree with itself") if self.height() >= lhs.height(): self.__ljoin(lhs) else: @@ -71,6 +77,8 @@ class Tree[T]: self.exchange(lhs) def rjoin(self, rhs: "Tree[T]") -> None: + if self is rhs: + raise Exception("Cannot merge tree with itself") if self.height() >= rhs.height(): self.__rjoin(rhs) else: @@ -115,6 +123,18 @@ class Node[T]: self.parent: Branch[T] | Tree[T] = parent self.height: int = 1 + def validate(self) -> None: + visited = set() + border: list[Node[T]] = [self] + while len(border): + curr = border.pop() + if curr in visited: + raise Exception("Cycle in tree") + visited.add(curr) + if isinstance(curr, Branch): + border.append(curr.lhs) + border.append(curr.rhs) + def with_parent(self, parent: "Branch[T] | Tree[T]") -> "Node[T]": self.parent = parent return self @@ -129,11 +149,11 @@ class Node[T]: makes self.parent empty """ curr = self - lhs = Tree() - rhs = Tree() + lhs = Tree[T]() + rhs = Tree[T]() while isinstance(curr.parent, Node): curr_parent = curr.parent - extra = Tree() + extra = Tree[T]() if curr_parent.lhs is curr: extra.root = curr_parent.rhs.with_parent(extra) rhs.rjoin(extra) @@ -250,7 +270,7 @@ class Branch[T](Node[T]): # m d a b c d # / \ # b c - n = self.lhs + n = self.rhs if not isinstance(n, Branch): return m = n.lhs @@ -341,6 +361,7 @@ class Branch[T](Node[T]): def balance_one(self): if abs(self.get_balance()) <= 1: return + if self.get_balance() > 0: # right is taller if not isinstance(self.rhs, Branch): @@ -357,6 +378,7 @@ class Branch[T](Node[T]): self.rotate_lr() else: self.rotate_ll() + self.root().validate() def balance_one_propagate(self) -> None: init_height = self.height diff --git a/example.conf b/example.conf index 9d60574..a0f7394 100644 --- a/example.conf +++ b/example.conf @@ -1,5 +1,5 @@ -WIDTH=25 -HEIGHT=25 +WIDTH=100 +HEIGHT=100 ENTRY=0,0 EXIT=24,24 OUTPUT_FILE=test -- 2.53.0