From a15897289b0c47702a975a9101d4ddec7a60ea92 Mon Sep 17 00:00:00 2001 From: Axy Date: Tue, 17 Mar 2026 21:05:25 +0100 Subject: [PATCH] AVL update, TODO: maintain avl node order, not just leaf, and update comments --- __main__.py | 3 +- amazeing/maze_class/maze_dirty_tracker.py | 7 ++-- amazeing/maze_class/maze_pacman_tracker.py | 33 +++++++++++++++ amazeing/maze_make_pacman.py | 7 ++-- amazeing/utils/avl.py | 49 +++------------------- amazeing/utils/randset.py | 5 +-- 6 files changed, 48 insertions(+), 56 deletions(-) create mode 100644 amazeing/maze_class/maze_pacman_tracker.py diff --git a/__main__.py b/__main__.py index b489290..d6a8d3f 100644 --- a/__main__.py +++ b/__main__.py @@ -13,6 +13,7 @@ from amazeing.config.config_parser import Config 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_class.maze_pacman_tracker import MazePacmanTracker from amazeing.maze_display.TTYdisplay import TileCycle, TileMaps, extract_pairs from amazeing.maze_display.backend import CloseRequested, IVec2 @@ -26,7 +27,7 @@ dims = IVec2(config.width, config.height) maze = Maze(dims) dirty_tracker = MazeDirtyTracker(maze) -pacman_tracker = MazeDirtyTracker(maze) +pacman_tracker = MazePacmanTracker(maze) maze.outline() diff --git a/amazeing/maze_class/maze_dirty_tracker.py b/amazeing/maze_class/maze_dirty_tracker.py index 7300320..ed8c91a 100644 --- a/amazeing/maze_class/maze_dirty_tracker.py +++ b/amazeing/maze_class/maze_dirty_tracker.py @@ -1,13 +1,12 @@ from collections.abc import Iterable from amazeing.maze_class.maze import Maze from amazeing.maze_class.maze_coords import WallCoord -from amazeing.utils.randset import Randset class MazeDirtyTracker: def __init__(self, maze: Maze) -> None: self.__maze: Maze = maze - self.__dirty: Randset[WallCoord] = Randset() + self.__dirty: set[WallCoord] = set() maze.observers.add(self.__observer) def __repr__(self) -> str: @@ -19,9 +18,9 @@ class MazeDirtyTracker: def __observer(self, wall: WallCoord) -> None: self.__dirty ^= {wall} - def clear(self) -> Randset[WallCoord]: + def clear(self) -> set[WallCoord]: res = self.__dirty - self.__dirty = Randset() + self.__dirty = set() return res def curr_dirty(self) -> Iterable[WallCoord]: diff --git a/amazeing/maze_class/maze_pacman_tracker.py b/amazeing/maze_class/maze_pacman_tracker.py new file mode 100644 index 0000000..559f8d0 --- /dev/null +++ b/amazeing/maze_class/maze_pacman_tracker.py @@ -0,0 +1,33 @@ +from collections.abc import Iterable +from amazeing.maze_class.maze import Maze +from amazeing.maze_class.maze_coords import WallCoord +from amazeing.utils.randset import Randset + + +class MazePacmanTracker: + def __init__(self, maze: Maze) -> None: + self.__maze: Maze = maze + self.__dirty: Randset[WallCoord] = Randset() + maze.observers.add(self.__observer) + + def __repr__(self) -> str: + return f"MazeDirtyTracker({self.__dirty})" + + def __del__(self) -> None: + self.__maze.observers.discard(self.__observer) + + def __observer(self, wall: WallCoord) -> None: + for cell in wall.neighbour_cells(): + for e in cell.walls(): + self.__dirty.add(e) + + def clear(self) -> Randset[WallCoord]: + res = self.__dirty + self.__dirty = Randset() + return res + + def curr_dirty(self) -> Iterable[WallCoord]: + return self.__dirty + + def end(self) -> None: + self.__maze.observers.discard(self.__observer) diff --git a/amazeing/maze_make_pacman.py b/amazeing/maze_make_pacman.py index fd754a8..408772f 100644 --- a/amazeing/maze_make_pacman.py +++ b/amazeing/maze_make_pacman.py @@ -2,18 +2,19 @@ from typing import Callable from amazeing import Maze, WallCoord import random -from amazeing.maze_class.maze_dirty_tracker import MazeDirtyTracker +from amazeing.maze_class.maze_pacman_tracker import MazePacmanTracker def maze_make_pacman( maze: Maze, walls_const: set[WallCoord], - dirty_tracker: MazeDirtyTracker, + pacman_tracker: MazePacmanTracker, callback: Callable[[Maze], None] = lambda _: None, iterations: int = 10, ) -> None: for _ in range(0, iterations): - walls = dirty_tracker.clear() + walls = pacman_tracker.clear() + random.shuffle(walls) n = 0 for wall in walls: if not maze.get_wall(wall) or wall in walls_const: diff --git a/amazeing/utils/avl.py b/amazeing/utils/avl.py index 5ce17ff..588bfb4 100644 --- a/amazeing/utils/avl.py +++ b/amazeing/utils/avl.py @@ -273,28 +273,8 @@ class Branch[T](Node[T]): n = self.rhs if not isinstance(n, Branch): return - m = n.lhs - if not isinstance(m, Branch): - return - a = self.lhs - b = m.lhs - c = m.rhs - d = n.rhs - n.lhs = a - n.rhs = b - m.lhs = c - m.rhs = d - self.lhs = n - self.rhs = m - a.parent = n - b.parent = n - c.parent = m - d.parent = m - n.parent = self - m.parent = self - n.update_height() - m.update_height() - self.update_height() + n.rotate_ll() + self.rotate_rr() def rotate_lr(self) -> None: # Double AVL rotate: @@ -309,28 +289,9 @@ class Branch[T](Node[T]): n = self.lhs if not isinstance(n, Branch): return - m = n.rhs - if not isinstance(m, Branch): - return - a = n.lhs - b = m.lhs - c = m.rhs - d = self.rhs - n.lhs = a - n.rhs = b - m.lhs = c - m.rhs = d - self.lhs = n - self.rhs = m - a.parent = n - b.parent = n - c.parent = m - d.parent = m - n.parent = self - m.parent = self - n.update_height() - m.update_height() - self.update_height() + n.rotate_rr() + self.rotate_ll() + n = self.lhs def append(self, value: T) -> "Leaf[T]": if isinstance(self.rhs, Branch): diff --git a/amazeing/utils/randset.py b/amazeing/utils/randset.py index 62ab2f5..6989f38 100644 --- a/amazeing/utils/randset.py +++ b/amazeing/utils/randset.py @@ -3,9 +3,6 @@ from typing import cast, overload class Randset[T](MutableSequence[T], MutableSet[T]): - # __getitem__, __setitem__, __delitem__, __len__, and insert(). - # __contains__, __iter__, __len__, - # add(), and discard(). def __init__(self) -> None: self.__elems: list[T] = [] self.__idx_map: dict[T, int] = {} @@ -72,4 +69,4 @@ class Randset[T](MutableSequence[T], MutableSet[T]): del self.__idx_map[value] def insert(self, index: int, value: T) -> None: - raise NotImplementedError("slice setitem in randset") + raise NotImplementedError("index insert randset") -- 2.53.0