From da1d4c753cbd12f5b05456fbb4ac6779955ef200 Mon Sep 17 00:00:00 2001 From: Axy Date: Fri, 20 Mar 2026 17:47:43 +0100 Subject: [PATCH] Perf optimization and pad drawn tree tracking, need to do lazy drawing then this phase should be done --- .gitignore | 2 + __main__.py | 20 ++++----- amazeing/maze_class/maze_coords.py | 4 +- amazeing/maze_class/maze_pattern.py | 6 +-- amazeing/maze_display/TTYdisplay.py | 39 +++++++++++++++--- amazeing/maze_display/backend.py | 34 +++++++-------- amazeing/utils/__init__.py | 4 +- amazeing/utils/quadtree.py | 64 ++++++++++++++++++++--------- 8 files changed, 113 insertions(+), 60 deletions(-) diff --git a/.gitignore b/.gitignore index 93e9841..9cc1138 100644 --- a/.gitignore +++ b/.gitignore @@ -1,4 +1,6 @@ **/__pycache__ **/.mypy_cache out.prof +prof.svg +tmp .venv diff --git a/__main__.py b/__main__.py index 0b82cd1..656eb62 100644 --- a/__main__.py +++ b/__main__.py @@ -18,17 +18,6 @@ from amazeing.maze_display.TTYdisplay import TileCycle, TileMaps, extract_pairs from amazeing.maze_display.backend import CloseRequested, IVec2 from amazeing.utils import quadtree -tree1 = quadtree.Tree.rectangle((IVec2(3, 3), IVec2(8, 11))) -print(tree1) -tree2 = quadtree.Tree.rectangle((IVec2(0, 0), IVec2(4, 8))) -print(tree2) -tree3 = quadtree.Tree.rectangle((IVec2(1, 1), IVec2(8, 10))) -print(tree3) -tree4 = tree1 | tree2 -print(tree4) -print(tree4 & tree3) -exit(0) - config = Config.parse(open("./example.conf").read()) if config.seed is not None: @@ -81,7 +70,16 @@ def clear_backend() -> None: backend.draw_tile(tile) +class Tick: + tick: float = time.monotonic() + + def display_maze(maze: Maze) -> None: + now = time.monotonic() + if now - Tick.tick < 0.016: + return + Tick.tick = time.monotonic() + clear_backend() # pathfind() backend.set_style(full.curr_style()) diff --git a/amazeing/maze_class/maze_coords.py b/amazeing/maze_class/maze_coords.py index d6e524d..30c32ea 100644 --- a/amazeing/maze_class/maze_coords.py +++ b/amazeing/maze_class/maze_coords.py @@ -53,7 +53,9 @@ class Cardinal(Enum): res = [src.tile_coords()] for card in path: nxt = src.get_neighbour(card) - res.append((src.tile_coords() + nxt.tile_coords()) // 2) + res.append( + (src.tile_coords() + nxt.tile_coords()) // IVec2.splat(2) + ) res.append(nxt.tile_coords()) src = nxt return res diff --git a/amazeing/maze_class/maze_pattern.py b/amazeing/maze_class/maze_pattern.py index 5594cdb..efb401a 100644 --- a/amazeing/maze_class/maze_pattern.py +++ b/amazeing/maze_class/maze_pattern.py @@ -95,15 +95,15 @@ class Pattern: dims = normalized.dims() slots = set( map( - lambda e: CellCoord(e + 1), - CellCoord(canvas - dims - 1).all_up_to(), + lambda e: CellCoord(e + IVec2.splat(1)), + CellCoord(canvas - dims - IVec2.splat(1)).all_up_to(), ) ) for excluded in excluding: slots -= negative.offset(excluded).__cells if len(slots) == 0: return Pattern([]) - ideal = (canvas - dims) // 2 + ideal = (canvas - dims) // IVec2.splat(2) slot = min( slots, key=lambda c: int.__add__(*((e := c - ideal) * e).xy()) ) diff --git a/amazeing/maze_display/TTYdisplay.py b/amazeing/maze_display/TTYdisplay.py index d9b0f4a..d1ede80 100644 --- a/amazeing/maze_display/TTYdisplay.py +++ b/amazeing/maze_display/TTYdisplay.py @@ -1,5 +1,6 @@ from abc import ABC, abstractmethod from collections.abc import Callable, Generator, Iterable +import time from amazeing.utils import BiMap from amazeing.config.config_parser import Color, Config, ColoredLine, ColorPair from amazeing.maze_display.layout import ( @@ -14,6 +15,7 @@ from amazeing.maze_display.layout import ( layout_sort_chunked, layout_split, ) +from amazeing.utils import Rect, QuadTree from .backend import IVec2, BackendEvent, KeyboardInput import curses @@ -186,13 +188,23 @@ class MazeTileMap: return res def dst_coord(self, pos: IVec2) -> IVec2: - return (n := pos // 2) * self.__cell_dim + (pos - n) * self.__wall_dim + return (n := pos // IVec2.splat(2)) * self.__cell_dim + ( + pos - n + ) * self.__wall_dim def src_coord(self, pos: IVec2) -> IVec2: - return pos % 2 * self.__wall_dim + return pos % IVec2.splat(2) * self.__wall_dim + + def dst_coord_rev(self, pixel: IVec2) -> IVec2: + mod = self.__wall_dim + self.__cell_dim + return (pixel // mod) * IVec2.splat(2) + IVec2[int].with_op( + lambda a, b: 0 if a < b else 1 + )(pixel % mod, self.__wall_dim) def tile_size(self, pos: IVec2) -> IVec2: - return (pos + 1) % 2 * self.__wall_dim + pos % 2 * self.__cell_dim + return (pos + IVec2.splat(1)) % IVec2.splat( + 2 + ) * self.__wall_dim + pos % IVec2.splat(2) * self.__cell_dim def draw_at(self, at: IVec2, idx: int, window: curses.window) -> None: self.__tiles[idx].blit( @@ -217,12 +229,14 @@ class ScrollablePad: def __init__( self, dims: IVec2, + cb: Callable[[Rect], None], constrained: bool = True, init_pos: IVec2 = IVec2.splat(0), ) -> None: self.__pos = init_pos self.pad: curses.window = curses.newpad(*dims.yx()) self.constrained = constrained + self.cb = cb def dims(self) -> IVec2: y, x = self.pad.getmaxyx() @@ -248,6 +262,7 @@ class ScrollablePad: return draw_start = at + win_start draw_end = draw_start + draw_dim - IVec2.splat(1) + self.cb((pad_start, pad_start + draw_dim)) self.pad.overwrite( window, *pad_start.yx(), @@ -391,7 +406,9 @@ class TTYBackend: self.__tilemap: MazeTileMap = MazeTileMap(wall_dim, cell_dim) self.__style = 0 - dims = self.__tilemap.dst_coord(maze_dims * 2 + 1) + dims = self.__tilemap.dst_coord( + maze_dims * IVec2.splat(2) + IVec2.splat(1) + ) self.__screen: curses.window = curses.initscr() curses.start_color() @@ -401,7 +418,8 @@ class TTYBackend: self.__screen.keypad(True) self.__scratch: curses.window = curses.newpad(1, 1) - self.__pad: ScrollablePad = ScrollablePad(dims) + self.__drawn: QuadTree = QuadTree() + self.__pad: ScrollablePad = ScrollablePad(dims, self.pad_callback) self.__dims = maze_dims maze_box = FBox( @@ -460,6 +478,16 @@ class TTYBackend: curses.echo() curses.endwin() + def pad_callback(self, rect: Rect) -> None: + start, end_excl = rect + drawn_rect = ( + self.__tilemap.dst_coord_rev(start), + self.__tilemap.dst_coord_rev(end_excl - IVec2.splat(1)) + + IVec2.splat(1), + ) + self.__drawn += QuadTree.rectangle(drawn_rect) + pass + def set_filler(self, style: int) -> None: if self.__filler == style: return @@ -518,6 +546,7 @@ class TTYBackend: key = self.__screen.getkey() except curses.error: return False + match key: case "KEY_RESIZE": self.__resize = True diff --git a/amazeing/maze_display/backend.py b/amazeing/maze_display/backend.py index 77ecf16..184e76f 100644 --- a/amazeing/maze_display/backend.py +++ b/amazeing/maze_display/backend.py @@ -37,31 +37,27 @@ class IVec2[T = int]: def innertype(self) -> Type[T]: return type(self.x) - def __mul__(self, other: "T | IVec2[T]") -> "IVec2[T]": - return self.with_op(getattr(self.innertype(), "__mul__"))(self, other) + def __mul__(self, other: "IVec2[T]") -> "IVec2[T]": + return IVec2(self.x * other.x, self.y * other.y) # type:ignore - def __add__(self, other: "T | IVec2[T]") -> "IVec2[T]": - return self.with_op(getattr(self.innertype(), "__add__"))(self, other) + def __add__(self, other: "IVec2[T]") -> "IVec2[T]": + return IVec2(self.x + other.x, self.y + other.y) # type:ignore - def __sub__(self, other: "T | IVec2[T]") -> "IVec2[T]": - return self.with_op(getattr(self.innertype(), "__sub__"))(self, other) + def __sub__(self, other: "IVec2[T]") -> "IVec2[T]": + return IVec2(self.x - other.x, self.y - other.y) # type:ignore - def __floordiv__(self, other: "T| IVec2[T]") -> "IVec2[T]": - return self.with_op(getattr(self.innertype(), "__floordiv__"))( - self, other - ) + def __floordiv__(self, other: "IVec2[T]") -> "IVec2[T]": + return IVec2(self.x // other.x, self.y // other.y) # type:ignore - def __mod__(self, other: "T | IVec2[T]") -> "IVec2[T]": - return self.with_op(getattr(self.innertype(), "__mod__"))(self, other) + def __mod__(self, other: "IVec2[T]") -> "IVec2[T]": + return IVec2(self.x % other.x, self.y % other.y) # type:ignore def __eq__(self, value: object, /) -> bool: - if not isinstance(value, IVec2): - return False - if self.x != value.x: - return False - if self.y != value.y: - return False - return True + return ( + isinstance(value, IVec2) + and self.x == value.x + and self.y == value.y + ) def __hash__(self) -> int: return hash((self.x, self.y)) diff --git a/amazeing/utils/__init__.py b/amazeing/utils/__init__.py index 75a6923..30fd547 100644 --- a/amazeing/utils/__init__.py +++ b/amazeing/utils/__init__.py @@ -1,5 +1,7 @@ from .bi_map import BiMap from .avl import Tree as AVLTree from .avl import Leaf as AVLLeaf +from .quadtree import Tree as QuadTree +from .quadtree import Rect -__all__ = ["BiMap", "AVLTree", "AVLLeaf"] +__all__ = ["BiMap", "AVLTree", "AVLLeaf", "QuadTree", "Rect"] diff --git a/amazeing/utils/quadtree.py b/amazeing/utils/quadtree.py index 69d3473..47e06fd 100644 --- a/amazeing/utils/quadtree.py +++ b/amazeing/utils/quadtree.py @@ -1,5 +1,5 @@ from collections.abc import Callable -from typing import assert_never, cast +from typing import cast from amazeing.maze_display.backend import IVec2 from functools import partial from itertools import chain @@ -8,11 +8,14 @@ type tuple4[T] = tuple[T, T, T, T] def map4[T, U](fn: Callable[[T], U], tup: tuple4[T]) -> tuple4[U]: - return cast(tuple4[U], tuple(map(fn, tup))) + a, b, c, d = tup + return (fn(a), fn(b), fn(c), fn(d)) def zip4[T, U](a: tuple4[T], b: tuple4[U]) -> tuple4[tuple[T, U]]: - return cast(tuple4[tuple[T, U]], tuple(zip(a, b))) + a1, b1, c1, d1 = a + a2, b2, c2, d2 = b + return ((a1, a2), (b1, b2), (c1, c2), (d1, d2)) type Node = tuple4[MaybeNode] @@ -82,7 +85,7 @@ class Tree: res = self.raised_to(other.__height) def descend(node: MaybeNode, depth: int = 0) -> MaybeNode: - if other.__height + depth == self.__height: + if other.__height + depth == res.__height: return fn(node, other.__root) (a, b, c, d) = Tree.node_split(node) a = descend(a, depth + 1) @@ -92,10 +95,16 @@ class Tree: return res.normalized() def __or__(self, other: "Tree") -> "Tree": - return self.shared_layer_apply(Tree.node_union, other) + return self.shared_layer_apply(Tree.node_or, other) def __and__(self, other: "Tree") -> "Tree": - return self.shared_layer_apply(Tree.node_intersection, other) + return self.shared_layer_apply(Tree.node_and, other) + + def __add__(self, other: "Tree") -> "Tree": + return self | other + + def __sub__(self, other: "Tree") -> "Tree": + return self.shared_layer_apply(Tree.node_sub, other) @staticmethod def rectangle(rect: Rect) -> "Tree": @@ -157,26 +166,25 @@ class Tree: @staticmethod def node_starts(pos: IVec2, height: int) -> tuple4[IVec2]: - dims = IVec2.splat(1 << (height - 1)) - - def f(x: int, y: int) -> IVec2: - return pos + IVec2(x, y) * dims + dim = 1 << (height - 1) + x = IVec2(dim, 0) + y = IVec2(0, dim) return ( - f(0, 0), - f(1, 0), - f(0, 1), - f(1, 1), + pos, + e := pos + x, + pos + y, + e + y, ) @staticmethod - def node_negation(node: MaybeNode) -> MaybeNode: + def node_neg(node: MaybeNode) -> MaybeNode: if isinstance(node, bool): return not node - return map4(Tree.node_negation, node) + return map4(Tree.node_neg, node) @staticmethod - def node_union(a: MaybeNode, b: MaybeNode) -> MaybeNode: + def node_or(a: MaybeNode, b: MaybeNode) -> MaybeNode: match (a, b): case (True, _) | (_, True): return True @@ -184,13 +192,13 @@ class Tree: return n case (a, b): return Tree.node_normalize( - map4(lambda e: Tree.node_union(*e), zip4(a, b)) + map4(lambda e: Tree.node_or(*e), zip4(a, b)) ) # mypy please do proper control flow analysis raise Exception() @staticmethod - def node_intersection(a: MaybeNode, b: MaybeNode) -> MaybeNode: + def node_and(a: MaybeNode, b: MaybeNode) -> MaybeNode: match (a, b): case (False, _) | (_, False): return False @@ -198,7 +206,23 @@ class Tree: return n case (a, b): return Tree.node_normalize( - map4(lambda e: Tree.node_intersection(*e), zip4(a, b)) + map4(lambda e: Tree.node_and(*e), zip4(a, b)) + ) + # ditto + raise Exception() + + @staticmethod + def node_sub(a: MaybeNode, b: MaybeNode) -> MaybeNode: + match (a, b): + case (False, _) | (_, True): + return False + case (n, False): + return n + case (True, n): + return Tree.node_neg(n) + case (a, b): + return Tree.node_normalize( + map4(lambda e: Tree.node_sub(*e), zip4(a, b)) ) # ditto raise Exception() -- 2.53.0