From dce3ed6d687f4ca76a16d3e198f5822664deb165 Mon Sep 17 00:00:00 2001
From: Axy <gilliardmarthey.axel@gmail.com>
Date: Thu, 19 Mar 2026 18:47:13 +0100
Subject: [PATCH] Quadtree parital impl, only need substraction and addition

---
 __main__.py                         |   5 ++
 amazeing/maze_class/maze_pattern.py |   4 +
 amazeing/utils/quadtree.py          | 115 ++++++++++++++++++++++++++++
 3 files changed, 124 insertions(+)
 create mode 100644 amazeing/utils/quadtree.py

diff --git a/__main__.py b/__main__.py
index d6a8d3f..dad4907 100644
--- a/__main__.py
+++ b/__main__.py
@@ -16,6 +16,11 @@ 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
+from amazeing.utils import quadtree
+
+tree = quadtree.Tree.rectangle((IVec2(3, 3), IVec2(8, 11)))
+print(tree)
+exit(0)
 
 config = Config.parse(open("./example.conf").read())
 
diff --git a/amazeing/maze_class/maze_pattern.py b/amazeing/maze_class/maze_pattern.py
index cda2221..5594cdb 100644
--- a/amazeing/maze_class/maze_pattern.py
+++ b/amazeing/maze_class/maze_pattern.py
@@ -86,6 +86,10 @@ class Pattern:
     def centered_for(
         self, canvas: IVec2, excluding: set[CellCoord] = set()
     ) -> "Pattern":
+        # TODO: don't make a set for the whole maze at the start then
+        # remove from it, find the set of invalid spots then iterate
+        # through valid spots in order of priority and find the first
+        # that matches
         normalized: Pattern = self.normalized()
         negative = normalized.flood_filled().mirrored()
         dims = normalized.dims()
diff --git a/amazeing/utils/quadtree.py b/amazeing/utils/quadtree.py
new file mode 100644
index 0000000..2cd7425
--- /dev/null
+++ b/amazeing/utils/quadtree.py
@@ -0,0 +1,115 @@
+from typing import cast
+from amazeing.maze_display.backend import IVec2
+from functools import partial
+from itertools import chain
+
+type tuple4[T] = tuple[T, T, T, T]
+
+type Node = tuple4[MaybeNode]
+type MaybeNode = Node | bool
+
+# start, end
+type Rect = tuple[IVec2, IVec2]
+
+
+class Tree:
+    def __init__(self) -> None:
+        self.__root: MaybeNode = False
+        self.__height: int = 0
+
+    def __repr__(self) -> str:
+        tab = Tree.node_to_tab(self.__root, self.__height)
+        data = "\n".join(
+            "".join("#" if char else "-" for char in line) for line in tab
+        )
+        return f"Quadtree: height - {self.__height}, data:\n{data}"
+
+    @staticmethod
+    def rectangle(rect: Rect) -> "Tree":
+        res = Tree()
+        while (s := 1 << res.__height) < rect[1].x or s < rect[1].y:
+            res.__height += 1
+        res.__root = Tree.node_from_rect(IVec2(0, 0), res.__height, rect)
+        return res
+
+    @staticmethod
+    def node_to_tab(node: MaybeNode, height: int) -> list[list[bool]]:
+        if isinstance(node, bool):
+            dim = 1 << height
+            return [[node for _ in range(dim)] for _ in range(dim)]
+        a, b, c, d = node
+        subtab = partial(Tree.node_to_tab, height=height - 1)
+        return [
+            l1 + l2
+            for l1, l2 in chain(
+                zip(subtab(a), subtab(b)),
+                zip(subtab(c), subtab(d)),
+            )
+        ]
+
+    @staticmethod
+    def node_simplify(node: MaybeNode) -> MaybeNode:
+        match node:
+            case (True, True, True, True):
+                return True
+            case (False, False, False, False):
+                return False
+        return node
+
+    @staticmethod
+    def node_from_rect(pos: IVec2, height: int, rect: Rect) -> MaybeNode:
+        node_rect = Tree.node_rect(pos, height)
+        if Tree.rect_contains(rect, node_rect):
+            return True
+        if not Tree.rect_collide(rect, node_rect):
+            return False
+        starts = Tree.node_starts(pos, height)
+        return cast(
+            Node,
+            tuple(
+                map(
+                    partial(Tree.node_from_rect, height=height - 1, rect=rect),
+                    starts,
+                )
+            ),
+        )
+
+    @staticmethod
+    def node_rect(pos: IVec2, height: int) -> Rect:
+        return (pos, pos + IVec2.splat(1 << height))
+
+    @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
+
+        # fmt: off
+        return (
+            f(0, 0), f(1, 0),
+            f(0, 1), f(1, 1),
+        )
+        # fmt: on
+
+    @staticmethod
+    def rect_collide(a: Rect, b: Rect) -> bool:
+        a_start, a_end = a
+        b_start, b_end = b
+        return (
+            a_end.x > b_start.x
+            and a_end.y > b_start.y
+            and b_end.x > a_start.x
+            and b_end.y > a_start.y
+        )
+
+    @staticmethod
+    def rect_contains(a: Rect, b: Rect) -> bool:
+        a_start, a_end = a
+        b_start, b_end = b
+        return (
+            a_start.x <= b_start.x
+            and a_start.y <= b_start.y
+            and a_end.x >= b_end.x
+            and a_end.y >= b_end.y
+        )
-- 
2.53.0