From 5f51816e1984932ae00768ebd8237a0e06c7a386 Mon Sep 17 00:00:00 2001 From: Axy Date: Sun, 29 Mar 2026 20:02:18 +0200 Subject: [PATCH] Docstrings everywhere --- mazegen/config/config_parser.py | 168 +++++++++++++++++++++++++--- mazegen/config/parser_combinator.py | 129 +++++++++++++++++++-- mazegen/display/layout.py | 95 +++++++++++++++- mazegen/display/observer.py | 36 +++++- mazegen/display/tty.py | 151 +++++++++++++++++++++++++ mazegen/maze/dirty_tracker.py | 17 ++- mazegen/maze/make_empty.py | 3 + mazegen/maze/make_pacman.py | 5 +- mazegen/maze/make_perfect.py | 4 + mazegen/maze/maze.py | 68 +++++++++-- mazegen/maze/network_tracker.py | 39 ++++--- mazegen/maze/output.py | 16 +++ mazegen/maze/pacman_tracker.py | 13 +++ mazegen/maze/path.py | 31 +++-- mazegen/maze/pattern.py | 40 ++++++- mazegen/utils/avl.py | 147 ++++++++++++++++++++++-- mazegen/utils/bi_map.py | 28 +++++ mazegen/utils/coords.py | 98 +++++++++++++--- mazegen/utils/ivec2.py | 29 +++++ mazegen/utils/quadtree.py | 69 ++++++++++++ mazegen/utils/randset.py | 5 + 21 files changed, 1092 insertions(+), 99 deletions(-) diff --git a/mazegen/config/config_parser.py b/mazegen/config/config_parser.py index ac3730d..ad8c5c6 100644 --- a/mazegen/config/config_parser.py +++ b/mazegen/config/config_parser.py @@ -34,6 +34,9 @@ from .parser_combinator import ( def parse_bool(s: str) -> ParseResult[bool]: + """ + Parses a boolean, with its first letter a capital + """ return parser_map_err( lambda e: ParseError("Expected boolean 'True' or 'False'", e.at), alt( @@ -44,6 +47,9 @@ def parse_bool(s: str) -> ParseResult[bool]: def parse_int(s: str) -> ParseResult[int]: + """ + Parses an unsigned integer + """ return parser_map_err( lambda e: ParseError("Expected integer literal", e.at), parser_map(int, recognize(many_count(ascii_digit, min_n=1))), @@ -51,24 +57,38 @@ def parse_int(s: str) -> ParseResult[int]: def multispace0(s: str) -> ParseResult[str]: + """ + Parses zero or more spaces or tabs + """ return recognize(many_count(one_of(" \t")))(s) def parse_comment(s: str) -> ParseResult[str]: + """ + Parses a python-style comment, that is a `#`, and all following characters + up to a newline + """ return recognize(seq(tag("#"), many_count(none_of("\n"))))(s) def spaced[T](parser: Parser[T]) -> Parser[T]: + """ + Makes the given parser be surrounded by multispace0, allowing for spaces + before and after + """ return delimited(multispace0, parser, multispace0) def parse_coord(s: str) -> ParseResult[IVec2]: + """ + Parses coordinates, that is two int separated by a spaced comma + """ return parser_map( lambda e: IVec2(*e), pair( terminated( parse_int, - delimited(multispace0, tag(","), multispace0), + spaced(tag(",")), ), parse_int, ), @@ -76,10 +96,17 @@ def parse_coord(s: str) -> ParseResult[IVec2]: def parse_path(s: str) -> ParseResult[str]: + """ + Parses a file path, which simply recognizes any character except a newline + Requires at least one character + """ return recognize(many_count(none_of("\n"), min_n=1))(s) def char_range(a: str, b: str) -> str: + """ + A simple function to create a string from a range of characters + """ res = "" for c in range(ord(a), ord(b) + 1): res = res + chr(c) @@ -87,6 +114,10 @@ def char_range(a: str, b: str) -> str: def parse_varname(s: str) -> ParseResult[str]: + """ + Parses a variable name, that is one alphabetic or underscore character, + followed by zero or more alphanumeric or unerscore characters + """ varstart = "_" + char_range("a", "z") + char_range("A", "Z") vartail = varstart + char_range("0", "9") return parser_map_err( @@ -103,6 +134,10 @@ type Grouped[T] = tuple[int, T] def parse_color(s: str) -> ParseResult[Color]: + """ + Parses a color, which is either a variable name, or three integers + separated by spaced comma + """ cut_comma = spaced( cut(lookahead_parser(tag(","), seq(multispace0, parse_int))) ) @@ -122,6 +157,9 @@ def parse_color(s: str) -> ParseResult[Color]: def parse_color_pair(s: str) -> ParseResult[ColorPair]: + """ + Parses a color pair, that is two colors separated by a spaced colon + """ return cast( ParseResult[ColorPair], parser_map( @@ -135,7 +173,9 @@ def parse_colored_line( s: str, ) -> ParseResult[ColoredLine]: """ - returns a list of a color pair variable associated with its string + Parses a colored line, that is a sequence of possibly escaped strings + of characters, each preceeded by a color pair surrounded by braces, + all of which is surrounded by double quotes """ color_prefix = delimited( @@ -173,6 +213,9 @@ def parse_colored_line( def parse_str_line(s: str) -> ParseResult[str]: + """ + Parses a single line string with no escapes + """ return spaced( delimited( tag('"'), @@ -187,14 +230,26 @@ def parse_str_line(s: str) -> ParseResult[str]: def grouped_parser[T](parser: Parser[T]) -> Parser[Grouped[T]]: + """ + Returns a parser that first parses a spaced int, or assumes zero, followed + by the given parser, giving a tuple of the two + """ return pair(alt(spaced(parse_int), value(0, null_parser)), parser) -class ConfigException(Exception): - pass +class ConfigError(Exception): + """ + A simple exception for filtering, raised when a field is set an invalid + amount of times, or when certain config invariants are not held up + """ class ConfigField[T, U = T](ABC): + """ + A field in the config, defining methods to parse it, and how to resolve + multiple definitions + """ + def __init__( self, name: str, @@ -205,7 +260,7 @@ class ConfigField[T, U = T](ABC): def parse(self, s: str) -> ParseResult[T]: ... def default(self) -> U: - raise ConfigException(f"Value {self.__name} not provided") + raise ConfigError(f"Value {self.__name} not provided") @abstractmethod def merge(self, vals: list[T]) -> U: ... @@ -215,32 +270,54 @@ class ConfigField[T, U = T](ABC): class SimpleField[T](ConfigField[T, T]): + """ + A simlpe imlpementation of ConfigField, simply using the default if no + value was provided, giving the value if only one was specified, raising + an error otherwise + """ + def merge(self, vals: list[T]) -> T: if len(vals) == 0: return self.default() if len(vals) == 1: return vals[0] - raise ConfigException( + raise ConfigError( f"More than one definition of config field {self.__name}" ) class IntField(SimpleField[int]): + """ + A config field that parses an integer + """ + def parse(self, s: str) -> ParseResult[int]: return parse_int(s) class BoolField(SimpleField[bool]): + """ + A config field that parses a boolean + """ + def parse(self, s: str) -> ParseResult[bool]: return parse_bool(s) class CoordField(SimpleField[IVec2]): + """ + A config field that parses a coordinate + """ + def parse(self, s: str) -> ParseResult[IVec2]: return parse_coord(s) class PathField(SimpleField[str]): + """ + A config field that parses a file path + """ + def parse(self, s: str) -> ParseResult[str]: return parse_path(s) @@ -248,12 +325,19 @@ class PathField(SimpleField[str]): def OptionalField[T, U]( cls: Type[ConfigField[T, U]], ) -> Type[ConfigField[T, U | None]]: + """ + Maps the config field to be None, resovling to it if no value was given + """ return DefaultedField(cls, None) def DefaultedField[T, U]( cls: Type[ConfigField[T, U]], default: U ) -> Type[ConfigField[T, U]]: + """ + Maps the config field to resovle to a default if no value was given + """ + class Inner(cls): # type: ignore def default(self) -> U: return default @@ -267,6 +351,11 @@ def DefaultedField[T, U]( def DefaultedStrField[T, U]( cls: Type[ConfigField[T, U]], default_strs: list[str] ) -> Type[ConfigField[T, U]]: + """ + Same as DefaultedField except the default value is parsed from the list + of strings + """ + class Inner(cls): # type: ignore def default(self) -> U: acc = [] @@ -288,6 +377,10 @@ def DefaultedStrField[T, U]( def MappedField[T, U, V]( cls: Type[ConfigField[T, U]], mapping: Callable[[U], V] ) -> Type[ConfigField[T, V]]: + """ + Maps a field to apply the given function to its output + """ + class Inner(ConfigField[T, V]): def __init__(self, name: str) -> None: self.__inner = cls(name) @@ -306,7 +399,13 @@ def MappedField[T, U, V]( return Inner -def ListParser[T](parser: Parser[T]) -> Type[ConfigField[list[T]]]: +def ListField[T](parser: Parser[T]) -> Type[ConfigField[list[T]]]: + """ + A field that resolves multiple instances of a field by putting them in + a list. + Defaults to an empty list + """ + class Inner(ConfigField[list[T]]): def parse(self, s: str) -> ParseResult[list[T]]: return parser_map(lambda e: [e], parser)(s) @@ -325,6 +424,10 @@ def ListParser[T](parser: Parser[T]) -> Type[ConfigField[list[T]]]: def map_grouped[T](vals: list[Grouped[T]]) -> list[list[T]]: + """ + Takse a list of grouped-by-integer elements, and separates them into + multiple lists, one per distinct integer + """ res: dict[int, list[T]] = {} for group, elem in vals: if group not in res: @@ -334,31 +437,38 @@ def map_grouped[T](vals: list[Grouped[T]]) -> list[list[T]]: ColoredLineField = MappedField( - ListParser(grouped_parser(parse_colored_line)), map_grouped + ListField(grouped_parser(parse_colored_line)), map_grouped ) -PatternField = ListParser(parse_str_line) +PatternField = ListField(parse_str_line) def line_parser[T]( fields: dict[str, ConfigField[T]], ) -> Parser[tuple[str, T] | None]: + """ + Parses a line from any of the given fields, or an empty/comment line + Expects the name of the parser, followed by an equal sign, and then + the field itself, each of which may be spaced + """ return parser_map_err( lambda e: ParseError("Expected valid field name", e.at), alt( parser_map(lambda _: None, parse_comment), *( preceeded( - seq(tag(name), multispace0, tag("="), multispace0), - parser_map( - (lambda name: lambda res: (name, res))(name), - cut(terminated(field.parse, multispace0)), + seq(spaced(tag(name)), tag("=")), + spaced( + parser_map( + (lambda name: lambda res: (name, res))(name), + cut(terminated(field.parse, multispace0)), + ) ), ) for name, field in fields.items() ), parser_map( - lambda _: None, lookahead_parser(null_parser, tag("\n")) + lambda _: None, lookahead_parser(multispace0, tag("\n")) ), ), ) @@ -367,6 +477,13 @@ def line_parser[T]( def fields_parser( fields_raw: dict[str, type[ConfigField[Any]]], ) -> Parser[dict[str, Any]]: + """ + A general parser for all the given fields + Initializes the config field classes with their name as argument, then + applies a line parser created from them repeatedly, then finally resolves + the multiple definitions with the field's implementation + Returns a dict of the name of the field to its resolved output + """ fields = {key: cls(key) for key, cls in fields_raw.items()} parse_line = nonempty_parser( cut( @@ -419,6 +536,10 @@ def fields_parser( class Config: + """ + The config as parsed from a file + """ + width: int height: int entry: IVec2 | None @@ -444,6 +565,10 @@ class Config: @staticmethod def parse(s: str) -> "Config": + """ + Parses the config from a string, defaulting values as needed + May raise a ParserError or ConfigError + """ from mazegen.maze import Pattern fields = parser_complete( @@ -503,7 +628,7 @@ class Config: CoordField, IVec2(1, 1) ), "TILEMAP_BOX": DefaultedStrField( - ListParser(parse_colored_line), + ListField(parse_colored_line), [ '"{RED:BLACK}╔═╦╗"', '"{RED:BLACK}║ ║║"', @@ -513,7 +638,7 @@ class Config: ), "PROMPT_SIZE": DefaultedField(CoordField, IVec2(32, 5)), "PROMPT": DefaultedStrField( - ListParser(parse_colored_line), + ListField(parse_colored_line), [ '"{WHITE:BLACK} "', '"{WHITE:BLACK} q: quit r: regenerate "', @@ -534,4 +659,15 @@ class Config: if res.screensaver: res.visual = True + if res.entry is not None: + if res.entry.x >= res.width or res.entry.y >= res.height: + raise ConfigError( + f"The given entry {res.entry} is out of bounds of the maze" + ) + if res.exit is not None: + if res.exit.x >= res.width or res.exit.y >= res.height: + raise ConfigError( + f"The given exit {res.exit} is out of bounds of the maze" + ) + return res diff --git a/mazegen/config/parser_combinator.py b/mazegen/config/parser_combinator.py index 8bc2f3f..23fc0d7 100644 --- a/mazegen/config/parser_combinator.py +++ b/mazegen/config/parser_combinator.py @@ -1,7 +1,6 @@ from collections.abc import Callable from typing import Any import textwrap -from dataclasses import dataclass from mazegen.utils.ivec2 import IVec2 @@ -11,6 +10,11 @@ type Parser[T] = Callable[[str], ParseResult[T]] class ParseError(Exception): + """ + A parser error, with a message, location information, and subcauses + Provides convenient ways to format the error for reporting + """ + def __init__( self, msg: str, at: str, caused_by: list["ParseError"] | None = None ) -> None: @@ -22,19 +26,31 @@ class ParseError(Exception): ) def get_text_pos(self, input_str: str) -> IVec2: + """ + Returns the position of the error as one-indexed row and column, + from the given input text + """ pred_len = len(input_str) - len(self.at) row = input_str.count("\n", 0, pred_len) + 1 column = pred_len - max(input_str.rfind("\n", 0, pred_len), 0) return IVec2(column, row) def get_line(self, input_str: str) -> str: + """ + Returns the line where this error occured, from the input str + """ pred_len = len(input_str) - len(self.at) line_start = input_str.rfind("\n", 0, pred_len) + 1 line_end = max(input_str.find("\n", pred_len), 0) return input_str[line_start:line_end] def pretty_format(self, input_str: str, filename: str) -> str: - # Style taken from the excellent rustc error messages + """ + Returns a string containing the formatted error message, with + subcause information, convenient position indication, and subcauses + + The style is roughly taken from rustc error messages + """ pos = self.get_text_pos(input_str) col = pos.x row = pos.y @@ -62,19 +78,30 @@ class ParseError(Exception): ) -def error_map[T, R]( - f: Callable[[T], R], val: T | ParseError +def result_map[T, R]( + f: Callable[[T], R], res: T | ParseError ) -> R | ParseError: - return f(val) if not isinstance(val, ParseError) else val + """ + Applies the given function to the result type if it is not an error + Returns the mapped result + """ + return f(res) if not isinstance(res, ParseError) else res def parser_map[T, M](m: Callable[[T], M], p: Parser[T]) -> Parser[M]: - return lambda s: error_map(lambda res: (m(res[0]), res[1]), p(s)) + """ + Like result, but composed with the given parser, such that output is + mapped + """ + return lambda s: result_map(lambda res: (m(res[0]), res[1]), p(s)) def parser_map_err[T]( m: Callable[[ParseError], ParseError], p: Parser[T] ) -> Parser[T]: + """ + Maps the parser to a parser where the error case has been mapped by m + """ return lambda s: ( res if not isinstance( @@ -86,23 +113,36 @@ def parser_map_err[T]( def parser_default[T](p: Parser[T], default: T) -> Parser[T]: + """ + Makes a parser infallible by giving a default value if it fails + """ return alt(p, value(default, null_parser)) def parser_complete[T]( p: Parser[T], ) -> Parser[T]: + """ + Makes the parser require for it to reach end of file + """ return terminated(p, eof_parser()) def recognize[T](p: Parser[T]) -> Parser[str]: - return lambda s: error_map( + """ + Maps any parser to a parser that returns as a value the consumed string + """ + return lambda s: result_map( lambda rem: (s[: len(s) - len(rem[1])], rem[1]), p(s), ) def cut[T](p: Parser[T]) -> Parser[T]: + """ + Makes the parser fail through exception when it fails through a value + """ + def inner(s: str) -> ParseResult[T]: res: ParseResult[T] = p(s) if isinstance(res, ParseError): @@ -113,6 +153,10 @@ def cut[T](p: Parser[T]) -> Parser[T]: def tag(tag: str) -> Parser[str]: + """ + A parser that expects exactly the given string as input, then consumes + and returns it + """ return lambda s: ( (s[: len(tag)], s[len(tag) :]) # noqa E203 if s.startswith(tag) @@ -121,14 +165,25 @@ def tag(tag: str) -> Parser[str]: def char(s: str) -> ParseResult[str]: + """ + A parser that consumes one character + """ return (s[0], s[1:]) if len(s) > 0 else ParseError("Early EOF", s) def null_parser(s: str) -> ParseResult[str]: + """ + An infallible parser that matches and consumes zero characters + """ return ("", s) def lookahead_parser[T, U](p1: Parser[T], p2: Parser[U]) -> Parser[T]: + """ + Uses the first parser, and checks that the second parser succeeds to + return a success, without having said second parser consume its input + """ + def inner(s: str) -> ParseResult[T]: res = p1(s) if isinstance(res, ParseError): @@ -142,20 +197,36 @@ def lookahead_parser[T, U](p1: Parser[T], p2: Parser[U]) -> Parser[T]: def eof_parser() -> Parser[str]: + """ + A parser that expects end of file, that is an empty string + """ return lambda s: ( ("", "") if len(s) == 0 else ParseError("Expected EOF", s) ) def nonempty_parser[T](p: Parser[T]) -> Parser[T]: + """ + Takes a parser and only runs it if the input string is nonempty, otherwise + errors + """ return lambda s: p(s) if len(s) > 0 else ParseError("Early EOF", s) def value[T, V](val: V, p: Parser[T]) -> Parser[V]: + """ + Maps the given parser to always return val instead + """ return parser_map(lambda _: val, p) def alt[T](*choices: Parser[T]) -> Parser[T]: + """ + A parser that returns the first of choices that matches + Returns an error containing as subcauses all the parser's errors when + no parser matches + """ + def inner(s: str) -> ParseResult[T]: acc: list[ParseError] = [] for e in map(lambda p: p(s), choices): @@ -176,9 +247,8 @@ def fold[T, R]( sep: Parser[Any] = null_parser, ) -> Parser[R]: """ - Repeatedly call the p parser, folding the results using f, with an acc - created through acc_init - Returns error if and only if min_n iterations are not reached + Folds the given parser, interspered with sep, into accumulator, with at + least min_n elements, and stops when max_n is reached """ # no clean way to do this with lambdas i could figure out :< @@ -209,6 +279,10 @@ def many[T]( max_n: int | None = None, sep: Parser[Any] = null_parser, ) -> Parser[list[T]]: + """ + Folds the given parser, interspered with sep, into a list of at least + min_n elements, and stops when max_n is reached + """ return fold( parser_map(lambda e: [e], p), list.__add__, @@ -225,10 +299,18 @@ def many_count[T]( max_n: int | None = None, sep: Parser[Any] = null_parser, ) -> Parser[int]: + """ + Folds the given parser, interspered with sep, into a count of parses, + with at least min_n elements, and stops when max_n is reached + """ return fold(value(1, p), int.__add__, lambda: 0, min_n, max_n, sep) def seq[T](*parsers: Parser[T]) -> Parser[str]: + """ + Applies the given parsers in succession, then returns the consumed string + """ + def inner(s: str) -> ParseResult[None]: for parser in parsers: res = parser(s) @@ -241,27 +323,43 @@ def seq[T](*parsers: Parser[T]) -> Parser[str]: def pair[T, U](p1: Parser[T], p2: Parser[U]) -> Parser[tuple[T, U]]: - return lambda s: error_map( + """ + Applies both parsers, returning a tuple of the two values if both succeed, + or the first error it encounters + """ + return lambda s: result_map( lambda res1: parser_map(lambda res2: (res1[0], res2), p2)(res1[1]), p1(s), ) def preceeded[_T0, T1](p1: Parser[_T0], p2: Parser[T1]) -> Parser[T1]: + """ + Applies the parsers in succession then returns the value of p2 + """ return parser_map(lambda res: res[1], pair(p1, p2)) def terminated[T0, _T1](p1: Parser[T0], p2: Parser[_T1]) -> Parser[T0]: + """ + Applies the parsers in succession then returns the value of p1 + """ return parser_map(lambda res: res[0], pair(p1, p2)) def delimited[_T0, T1, _T2]( p1: Parser[_T0], p2: Parser[T1], p3: Parser[_T2] ) -> Parser[T1]: + """ + Applies the parsers in succession then returns the value of p2 + """ return preceeded(p1, terminated(p2, p3)) def one_of(chars: str) -> Parser[str]: + """ + Parses exactly one character, if it is within chars + """ return parser_map_err( lambda s: ParseError(f"Expected one char of {repr(chars)}", s.at), alt( @@ -271,6 +369,9 @@ def one_of(chars: str) -> Parser[str]: def none_of(chars: str) -> Parser[str]: + """ + Parses exactly one character, if it is not within chars + """ return lambda s: ( char(s) if isinstance(one_of(chars)(s), ParseError) @@ -279,8 +380,14 @@ def none_of(chars: str) -> Parser[str]: def ascii_hexdigit(s: str) -> ParseResult[str]: + """ + Parses one ascii hexadecimal character + """ return one_of("0123456789abcdefABCDEF")(s) def ascii_digit(s: str) -> ParseResult[str]: + """ + Parses one ascii decimal character + """ return one_of("0123456789")(s) diff --git a/mazegen/display/layout.py b/mazegen/display/layout.py index 8cd460e..3a3e03e 100644 --- a/mazegen/display/layout.py +++ b/mazegen/display/layout.py @@ -4,6 +4,11 @@ from mazegen.utils import IVec2 class BInt: + """ + An integer for use with layout operations, storing whether this may be + expanded to fit + """ + def __init__(self, val: int, has_flex: bool = False) -> None: self.val: int = val self.has_flex: bool = has_flex @@ -13,6 +18,9 @@ class BInt: @staticmethod def vector_sum(elems: list["BInt"]) -> "BInt": + """ + Merges the elements by summing its values and or-ing its flex-values + """ res = BInt( sum(map(lambda e: e.val, elems)), any(map(lambda e: e.has_flex, elems)), @@ -21,6 +29,10 @@ class BInt: @staticmethod def vector_max(elems: list["BInt"]) -> "BInt": + """ + Merges the elements by doing a max of its values and or-ing its + flex-values + """ res = BInt( max(map(lambda e: e.val, elems), default=0), any(map(lambda e: e.has_flex, elems)), @@ -36,6 +48,10 @@ type Layout[T] = Callable[[list[tuple[BInt, T]], int], list[int]] def layout_priority[T]( sizes: list[tuple[BInt, T]], available: int ) -> list[int]: + """ + A layout that attributes its avaialble space in order into the non-flex + parts of sizes, then gives the remaining space to the first flex size + """ res = [] for size, _ in sizes: size_scaled = min(size.val, available) @@ -49,10 +65,17 @@ def layout_priority[T]( def rdiv(a: int, b: int) -> int: + """ + A division that rounds up, and returns zero when dividing by zero + """ return a // b + (a % b != 0) if a != 0 else 0 def layout_fair[T](sizes: list[tuple[BInt, T]], available: int) -> list[int]: + """ + Evenly allocates its available space to the non-flex parts, then allocates + the remaining space evenly between the flex parts as well + """ res = [0 for _ in sizes] count = len(sizes) for idx, (size, _) in sorted(enumerate(sizes), key=lambda e: e[1][0].val): @@ -72,6 +95,11 @@ def layout_fair[T](sizes: list[tuple[BInt, T]], available: int) -> list[int]: def layout_split[T](sized: Layout[T], flexed: Layout[T]) -> Layout[T]: + """ + Composes two layouts by using one for the flex part, then one for the + non-flex part + """ + def inner(sizes: list[tuple[BInt, T]], available: int) -> list[int]: flexes = [(BInt(0, e[0].has_flex), e[1]) for e in sizes] sizes = [(BInt(e[0].val), e[1]) for e in sizes] @@ -85,6 +113,11 @@ def layout_split[T](sized: Layout[T], flexed: Layout[T]) -> Layout[T]: def layout_sort_shuffled[T]( init: Layout[T], extract: Callable[[T], int] ) -> Layout[T]: + """ + Modifies the layout by sorting the values according to extract, applying + the layout, and finally shuffling the result back to the right order + """ + def inner(sizes: list[tuple[BInt, T]], available: int) -> list[int]: mapping = [(i, extract(assoc)) for i, (_, assoc) in enumerate(sizes)] mapping.sort(key=lambda e: e[1]) @@ -100,6 +133,9 @@ def layout_sort_shuffled[T]( def layout_mapped[T, U](init: Layout[T], f: Callable[[U], T]) -> Layout[U]: + """ + Maps a layout by calling f to its inputs first + """ return lambda sizes, available: init( list(map(lambda e: (e[0], f(e[1])), sizes)), available ) @@ -110,6 +146,13 @@ def layout_sort_chunked[T]( chunk_layout: Layout[list[tuple[BInt, T]]], extract: Callable[[T], int], ) -> Layout[T]: + """ + Composes the layouts by first extracting chunks, grouped by identical + results of extract, merging the chunk sizes, applying the chunk layout to + those merged sizes, sub-applying the layout to each chunk, and finally + shuffling back to the original order + """ + def layout_chunk_seq( sizes: list[tuple[BInt, T]], available: int ) -> list[int]: @@ -157,13 +200,28 @@ def layout_sort_chunked[T]( class Box(ABC): + """ + A layout box ABC, the fundamental building block of layouts + """ + @abstractmethod - def dims(self) -> BVec2: ... + def dims(self) -> BVec2: + """ + Returns the dimensions of this box + """ + @abstractmethod - def laid_out(self, at: IVec2, into: IVec2) -> None: ... + def laid_out(self, at: IVec2, into: IVec2) -> None: + """ + Lays out this box into the given dimensions + """ class VBox[T](Box): + """ + A container box that stacks its elements vertically + """ + def __init__( self, layout: Layout[T], boxes: list[tuple[Box, T]] = [] ) -> None: @@ -172,6 +230,9 @@ class VBox[T](Box): @staticmethod def noassoc(layout: Layout[None], boxes: list[Box]) -> "VBox[None]": + """ + Initializes a VBox with no associated data for its sub-boxes + """ return VBox(layout, [(box, None) for box in boxes]) def dims(self) -> BVec2: @@ -198,6 +259,10 @@ class VBox[T](Box): class HBox[T](Box): + """ + A container box that stacks its elements horizontally + """ + def __init__( self, layout: Layout[T], boxes: list[tuple[Box, T]] = [] ) -> None: @@ -206,6 +271,9 @@ class HBox[T](Box): @staticmethod def noassoc(layout: Layout[None], boxes: list[Box]) -> "HBox[None]": + """ + Initializes an HBox with no associated data for its sub-boxes + """ return HBox(layout, [(box, None) for box in boxes]) def dims(self) -> BVec2: @@ -231,6 +299,10 @@ class HBox[T](Box): class FBox(Box): + """ + A simple box with variable size that uses a callback when laid out + """ + def __init__( self, dims: BVec2, cb: Callable[[IVec2, IVec2], None] ) -> None: @@ -248,6 +320,11 @@ class FBox(Box): class DBox(Box): + """ + A container box to track dirtiness, not redrawing if its location hasn't + changed since it was last laid out + """ + def __init__(self, inner: Box) -> None: self.__inner: Box = inner self.__prev: tuple[IVec2, IVec2] | None = None @@ -269,6 +346,9 @@ def vpad_box( min_pad: int = 0, cb: Callable[[IVec2, IVec2], None] = lambda _at, _into: None, ) -> FBox: + """ + Returns a simple box that gives zero-width vertical padding + """ return FBox(IVec2(BInt(0), BInt(min_pad, True)), cb) @@ -276,14 +356,23 @@ def hpad_box( min_pad: int = 0, cb: Callable[[IVec2, IVec2], None] = lambda _at, _into: None, ) -> FBox: + """ + Returns a simple box that gives zero-height horizontal padding + """ return FBox(IVec2(BInt(min_pad, True), BInt(0)), cb) def print_cb(at: IVec2, into: IVec2) -> None: + """ + A simple callback that prints its layout location for use in debugging + """ print(f"at {at.x, at.y}, into {into.x, into.y}") -def example() -> None: +def test_print_layout() -> None: + """ + A simple example that prints layouts with basic layout usage + """ a = FBox(IVec2(BInt(8, False), BInt(4, False)), print_cb) c = HBox.noassoc( layout_fair, diff --git a/mazegen/display/observer.py b/mazegen/display/observer.py index d271108..79e1b76 100644 --- a/mazegen/display/observer.py +++ b/mazegen/display/observer.py @@ -3,7 +3,7 @@ from mazegen.config.config_parser import Config from mazegen.display.tty import TTYBackend, TileCycle from mazegen.maze.dirty_tracker import DirtyTracker from mazegen.maze.maze import Maze -from mazegen.maze.path import path_pixels, pathfind_astar +from mazegen.maze.path import pathfind_astar from mazegen.utils.coords import Cardinal @@ -12,6 +12,15 @@ class MazeRegenerate(Exception): class TTYTracker: + """ + A tracker which may be added to a maze to make it output to tty + This class probably is doing too much but a refactor sounds more painful + + This manages the different styles for use in interactively cycling them, + manages the shortest path drawing, pause status, and redrawing only at + specific intervals + """ + def __init__( self, maze: Maze, @@ -47,6 +56,9 @@ class TTYTracker: self.update: bool = True def clear_backend(self) -> None: + """ + Draws as empty the walls that have been made empty since last redraw + """ self.__backend.set_style(self.__empty_style.curr_style()) for wall in self.__dirty_tracker.curr_dirty(): if self.__maze.get_wall(wall): @@ -55,6 +67,9 @@ class TTYTracker: self.__backend.draw_tile(tile) def path_invalidated(self) -> bool: + """ + Returns whether the previous path was invalidated since last redraw + """ if self.__path is None: return True src = self.__maze.entry @@ -65,12 +80,18 @@ class TTYTracker: return False def redraw_path(self, style: int) -> None: + """ + Draws the current path with the given style + """ if self.__path is not None: self.__backend.set_style(style) - for tile in path_pixels(self.__maze.entry, self.__path): + for tile in Cardinal.path_to_tiles(self.__path, self.__maze.entry): self.__backend.draw_tile(tile) def display_path(self) -> None: + """ + Updates, and redraws if needed, the current path + """ if ( all(map(self.__maze.get_wall, self.__dirty_tracker.curr_dirty())) and not self.path_invalidated() @@ -83,6 +104,10 @@ class TTYTracker: self.redraw_path(self.__path_style.curr_style()) def poll_events(self) -> None: + """ + Consumes and processes all the keyboard events + Raises a MazeRegenerate exception if the user requested it + """ while True: event = self.__backend.event() if isinstance(event, bool): @@ -118,6 +143,11 @@ class TTYTracker: continue def display_maze(self, wait_for_tick: bool = False) -> None: + """ + Processes backend events and redraws this backend if the frametime + was elapsed + Raises MazeRegenerate exception if the user requested it + """ now = time.monotonic() if self.__tick is not None: if wait_for_tick: @@ -142,7 +172,7 @@ class TTYTracker: e for wall in self.__dirty_tracker.curr_dirty() for e in wall.neighbours() - if self.__maze.check_coord(e) and self.__maze.get_wall(e) + if self.__maze.check_wall(e) and self.__maze.get_wall(e) } self.__backend.set_style(self.__full_style.curr_style()) diff --git a/mazegen/display/tty.py b/mazegen/display/tty.py index add1147..098b2e8 100644 --- a/mazegen/display/tty.py +++ b/mazegen/display/tty.py @@ -31,6 +31,10 @@ class KeyboardInput: class ITile(ABC): + """ + The ABC for a tile, for use with screens + """ + @abstractmethod def size(self) -> IVec2: ... @abstractmethod @@ -43,6 +47,9 @@ class ITile(ABC): def blit( self, src: IVec2, dst: IVec2, size: IVec2, window: curses.window ) -> None: + """ + Copies data from self into the window + """ if size.x <= 0 or size.y <= 0: return @@ -56,6 +63,10 @@ class ITile(ABC): def blit_iter( self, src: IVec2, dst: IVec2, size: IVec2 ) -> Generator[tuple[IVec2, "SubPixel"]]: + """ + Generator of the coords that would be drawn through a blit, as well + as subpixels for said blit + """ for y in range(size.y): for x in range(size.x): pos = IVec2(x, y) @@ -68,6 +79,11 @@ class ITile(ABC): size: IVec2, justify: IVec2, ) -> Generator[tuple[IVec2, "SubTile"]]: + """ + Iterates over the subtiles that a wrapping blit would go through, + as well as where they would be blitted to + """ + def size_offset_iter( start: int, size: int, mod: int ) -> Generator[tuple[int, int]]: @@ -100,6 +116,9 @@ class ITile(ABC): window: curses.window, justify: IVec2 = IVec2.splat(0), ) -> None: + """ + Blits self to the window, wrapping the tile + """ for pos, subtile in self.blit_wrapping_subtiles( src, dst, size, justify ): @@ -112,6 +131,9 @@ class ITile(ABC): size: IVec2, justify: IVec2 = IVec2.splat(0), ) -> Generator[tuple[IVec2, "SubPixel"]]: + """ + An iterator over the subpixels a wrapping blit would write + """ for pos, subtile in self.blit_wrapping_subtiles( src, dst, size, justify ): @@ -120,6 +142,10 @@ class ITile(ABC): class Tile(ITile): + """ + A simple tile that is its entire pad, initliazed from pixel values + """ + def __init__( self, pixels: list[list[tuple[str, int]]], dims: IVec2 ) -> None: @@ -153,6 +179,10 @@ class Tile(ITile): class SubPixel(ITile): + """ + A tile that is just one pixel of its pad + """ + def __init__(self, tile: ITile, pos: IVec2) -> None: super().__init__(tile.pad) self.__pos: IVec2 = tile.pos() + pos @@ -165,6 +195,10 @@ class SubPixel(ITile): class SubTile(ITile): + """ + A tile that is a sub-section of its pad + """ + def __init__(self, tile: ITile, pos: IVec2, size: IVec2) -> None: super().__init__(tile.pad) self.__pos: IVec2 = tile.pos() + pos @@ -178,36 +212,59 @@ class SubTile(ITile): class MazeTileMap: + """ + A tilemap of tiles, for use in displaying + """ + def __init__(self, wall_dim: IVec2, cell_dim: IVec2) -> None: self.__wall_dim: IVec2 = wall_dim self.__cell_dim: IVec2 = cell_dim self.tiles: list[ITile] = [] def add_tile(self, tile: ITile) -> int: + """ + Adds a tile to the tilemap and returns its index + """ res = len(self.tiles) self.tiles.append(tile) return res def dst_coord(self, pos: IVec2) -> IVec2: + """ + Returns the coordinate in the output window from a tile coordinate + """ return (n := pos // IVec2.splat(2)) * self.__cell_dim + ( pos - n ) * self.__wall_dim def src_coord(self, pos: IVec2) -> IVec2: + """ + Returns the coordinate in a tile in the tilemap from a tile coordinate + """ return pos % IVec2.splat(2) * self.__wall_dim def dst_coord_rev(self, pixel: IVec2) -> IVec2: + """ + Returns the coordinate of a tile from the coordinate in the + destination window + """ mod = self.__wall_dim + self.__cell_dim return (pixel // mod) * IVec2.splat(2) + (pixel % mod).with_op( lambda a, b: 0 if a < b else 1, self.__wall_dim ) def tile_size(self, pos: IVec2) -> IVec2: + """ + Returns the size of the destination tile for a given tile coord + """ 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: + """ + Draws the given tile at tile position into the window + """ self.tiles[idx].blit( self.src_coord(at), self.dst_coord(at), @@ -223,10 +280,19 @@ class MazeTileMap: idx: int, window: curses.window, ) -> None: + """ + Draws the given tile to an area in the window specified in pixel + coord, wrapping + """ self.tiles[idx].blit_wrapping(start, at, into, window) class ScrollablePad: + """ + A pad that may be used for display objects too large to fit, which may be + scrolled + """ + def __init__( self, dims: IVec2, @@ -244,11 +310,17 @@ class ScrollablePad: return IVec2(x, y) def clamp(self, dims: IVec2) -> None: + """ + Clamps this tile's coordinates to fit within dims, not scrolling past + """ self.__pos = self.__pos.lane_max(dims - self.dims()).lane_min( IVec2.splat(0) ) def present(self, at: IVec2, into: IVec2, window: curses.window) -> None: + """ + Draws this pad at the location on the window + """ if self.constrained: self.clamp(into) @@ -268,15 +340,27 @@ class ScrollablePad: ) def move(self, by: IVec2) -> None: + """ + Moves the tile itself, opposite of scroll + """ self.__pos = self.__pos + by def scroll(self, by: IVec2) -> None: + """ + Scrolls through the tile, opposite of move + """ self.move(by * IVec2.splat(-1)) def extract_pairs( config: Config, extra_colors: Iterable[ColorPair] = [] ) -> dict[ColorPair, int]: + """ + Extracts the color pairs from the config, and maps them to text + attributes + May raise a backend exception if too many colors are used or an invalid + variable color is used + """ all_tilemaps = [ e for tilemaps in ( @@ -341,6 +425,10 @@ def extract_pairs( class TileMaps: + """ + A class to store all the tilemaps once extracted from the config + """ + def __init__( self, config: Config, @@ -396,6 +484,10 @@ class TileMaps: class TileCycle[T]: + """ + A store of tile styles, used to cycle through them + """ + def __init__( self, styles: list[T], cb: Callable[[T], None], i: int = 0 ) -> None: @@ -407,16 +499,31 @@ class TileCycle[T]: cb(styles[i]) def cycle(self, by: int = 1) -> None: + """ + Cycles the current style by a given amount + """ new = abs((self.__i + by) % len(self.__styles)) if new != self.__i: self.__cb(self.__styles[new]) self.__i = new def curr_style(self) -> T: + """ + Returns the current style + """ return self.__styles[self.__i] class TTYBackend: + """ + This class stores a lot of things, which may be better split but that's + a lot of work + This initializes everything required for the display, that is, the + tilemaps, the curses api, the color pairs, and the entire window + layout + May raise a BackendException if it fails to excract colors + """ + def __init__( self, config: Config, @@ -569,6 +676,9 @@ class TTYBackend: self.uninit() def uninit(self) -> None: + """ + Uninitializes self, such resetting the terminal to its previous state + """ if self.__uninit: return self.__uninit = True @@ -579,6 +689,10 @@ class TTYBackend: curses.endwin() def pad_callback(self, rect: Rect) -> None: + """ + The function to be called with the window area where the maze pad + should be drawn + """ start, end_excl = rect drawn_rect = ( self.__tilemap.dst_coord_rev(start), @@ -598,6 +712,9 @@ class TTYBackend: self.__drawn += drawn_tree def set_filler(self, style: int) -> None: + """ + Changes the filler style used for the window layout + """ if self.__filler == style: return self.__redraw = True @@ -606,12 +723,23 @@ class TTYBackend: box.mark_dirty() def set_bg_init(self, bg_init: Callable[[IVec2], int]) -> None: + """ + Sets the function for use to initialize the background of the maze + """ self.__bg_init = bg_init def get_style_height(self, style: int) -> int: + """ + Returns the tree height of the given style, if zero it means + no tile uses this style + """ return self.__style_bimap.get(style).height() def map_style(self, src: int, dst: int) -> None: + """ + Maps the src style to dst, such that any tile with src style currently + will be redrawn with dst from now on + """ if src == dst: return if self.get_style_height(src) != 0: @@ -620,6 +748,10 @@ class TTYBackend: self.__style_bimap.key_map(src, dst) def map_style_cb(self) -> Callable[[int], None]: + """ + The callback to use when one wants to initliaze then map consecutive + styles, for use with tile cycles + """ curr: int | None = None def inner(new: int) -> None: @@ -632,21 +764,36 @@ class TTYBackend: return inner def add_style(self, style: ITile) -> int: + """ + Adds the given style to the tilemap, and returns its index + """ return self.__tilemap.add_tile(style) def dims(self) -> IVec2: + """ + Returns the dimensions of the maze + """ return self.__dims def draw_tile(self, pos: IVec2) -> None: + """ + Draws a tile at the pos with the current style + """ style = self.__style self.__style_bimap.add(style, pos) self.__tilemap.draw_at(pos, style, self.__pad.pad) self.__redraw = True def set_style(self, style: int) -> None: + """ + Sets the current style + """ self.__style = style def present(self) -> None: + """ + Redraw and layout the screen + """ if not self.__redraw: return self.__redraw = False @@ -657,6 +804,10 @@ class TTYBackend: self.__scratch.overwrite(self.__screen) def event(self) -> KeyboardInput | bool: + """ + Poll for a keyboard input, some of which may already get handled + for scrolling + """ try: key = self.__screen.getkey() except curses.error: diff --git a/mazegen/maze/dirty_tracker.py b/mazegen/maze/dirty_tracker.py index e4b77ea..ee7d425 100644 --- a/mazegen/maze/dirty_tracker.py +++ b/mazegen/maze/dirty_tracker.py @@ -3,6 +3,10 @@ from mazegen.utils import WallCoord class DirtyTracker: + """ + A simple tracker that keeps track of which walls were changed + """ + def __init__(self, maze: Maze) -> None: self.__maze: Maze = maze self.__dirty: set[WallCoord] = set() @@ -11,19 +15,26 @@ class DirtyTracker: 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: self.__dirty ^= {wall} def clear(self) -> set[WallCoord]: + """ + Returns the currently dirty set of walls and resets it + """ res = self.__dirty self.__dirty = set() return res def curr_dirty(self) -> set[WallCoord]: + """ + Returns the currently dirty set of walls, which may be modified + if a wall is later changed + """ return self.__dirty def end(self) -> None: + """ + Remove this tracker from the observers of the maze + """ self.__maze.observers.discard(self.__observer) diff --git a/mazegen/maze/make_empty.py b/mazegen/maze/make_empty.py index 65099cd..c98d59f 100644 --- a/mazegen/maze/make_empty.py +++ b/mazegen/maze/make_empty.py @@ -7,6 +7,9 @@ def make_empty( maze: Maze, walls_const: set[WallCoord], ) -> None: + """ + Clears all the walls of the maze + """ walls = [wall for wall in maze.walls_full() if wall not in walls_const] random.shuffle(walls) for wall in walls: diff --git a/mazegen/maze/make_pacman.py b/mazegen/maze/make_pacman.py index 90bf731..93a4514 100644 --- a/mazegen/maze/make_pacman.py +++ b/mazegen/maze/make_pacman.py @@ -11,6 +11,9 @@ def make_pacman( pacman_tracker: PacmanTracker, iterations: int = 10, ) -> None: + """ + Heuristically attempts the minimize the amount of impasses in the maze + """ for _ in range(0, iterations): walls = pacman_tracker.clear() n = 0 @@ -21,7 +24,7 @@ def make_pacman( if not maze.get_wall(wall) or wall in walls_const: continue leaf_neighbours = maze.wall_leaf_neighbours(wall) - if not maze.wall_cuts_cycle(wall): + if not maze.wall_causes_impass(wall): continue if len(leaf_neighbours) == 0: maze.set_wall(wall, False) diff --git a/mazegen/maze/make_perfect.py b/mazegen/maze/make_perfect.py index 16809fe..3631090 100644 --- a/mazegen/maze/make_perfect.py +++ b/mazegen/maze/make_perfect.py @@ -8,6 +8,10 @@ def make_perfect( maze: Maze, tracker: NetworkTracker, ) -> None: + """ + Incrementally fills every wall of the maze that doesn't cause it to be + bisected + """ empty = list(maze.walls_empty()) random.shuffle(empty) for wall in empty: diff --git a/mazegen/maze/maze.py b/mazegen/maze/maze.py index c85bae8..3ac95e1 100644 --- a/mazegen/maze/maze.py +++ b/mazegen/maze/maze.py @@ -11,6 +11,11 @@ type MazeObserver = Callable[[WallCoord], None] class Maze: + """ + A simple maze class, which is simply a set of filled walls + Its observers are called whenever the status of a wall changes + """ + def __init__(self, config: Config) -> None: self.dims = IVec2(config.width, config.height) self.observers: set[MazeObserver] = set() @@ -27,9 +32,16 @@ class Maze: self.__walls_full: dict[WallCoord, None] = {} def get_wall(self, coord: WallCoord) -> bool: + """ + Returns whether said wall is filled in + """ return coord in self.__walls_full def set_wall(self, wall: WallCoord, value: bool) -> None: + """ + Sets the status of the wall, as in whether it is filled, and + calls observers if needed + """ if self.get_wall(wall) != value: if value: self.__walls_full[wall] = None @@ -40,6 +52,10 @@ class Maze: observer(wall) def all_walls(self) -> Generator[WallCoord]: + """ + Returns an iterator over all the wall coords that are contained + within this maze, full or not + """ for orientation, a_count, b_count in [ (Orientation.HORIZONTAL, self.dims.y + 1, self.dims.x), (Orientation.VERTICAL, self.dims.x + 1, self.dims.y), @@ -49,9 +65,15 @@ class Maze: yield WallCoord(orientation, a, b) def all_cells(self) -> Iterable[CellCoord]: + """ + Returns an iterator over all the cell coords of this maze + """ return CellCoord(self.dims).all_up_to() def check_cell(self, cell: CellCoord) -> bool: + """ + Returns whether the given cell coord is valid in this maze + """ return ( self.dims.x > cell.x and self.dims.y > cell.y @@ -59,7 +81,10 @@ class Maze: and cell.y >= 0 ) - def check_coord(self, coord: WallCoord) -> bool: + def check_wall(self, coord: WallCoord) -> bool: + """ + Returns whether the given wall coord is valid in this maze + """ if coord.a < 0 or coord.b < 0: return False (a_max, b_max) = ( @@ -71,13 +96,16 @@ class Maze: return False return True - def get_walls_checked(self, ids: list[WallCoord]) -> list[bool]: - return [self.get_wall(id) for id in ids if self.check_coord(id)] - - def get_neighbours(self, id: WallCoord) -> list[bool]: - return self.get_walls_checked(id.neighbours()) + def get_walls_checked(self, walls: list[WallCoord]) -> list[bool]: + """ + Maps the given wall to whether it is full, skipping out of bound walls + """ + return [self.get_wall(id) for id in walls if self.check_wall(id)] def outline(self) -> None: + """ + Fills in the outline of the maze, calling observers as needed + """ if self.dims.x < 1 or self.dims.y < 1: return for orientation, a_iter, b_iter in [ @@ -97,12 +125,26 @@ class Maze: self.set_wall(WallCoord(orientation, a, b), True) def walls_full(self) -> Iterable[WallCoord]: + """ + Returns an iterator over this maze's filled walls + The iterator is only valid as long as the walls of the maze don't + change + """ return self.__walls_full def walls_empty(self) -> Iterable[WallCoord]: + """ + Returns an iterator over this maze's empty walls + The iterator is still valid after a wall has been altered, if it + was filled it shall not be yielded + """ return filter(lambda w: not self.get_wall(w), self.all_walls()) - def wall_cuts_cycle(self, wall: WallCoord) -> bool: + def wall_causes_impass(self, wall: WallCoord) -> bool: + """ + Return whether the wall, if full, creates an impass, that is a cell + with at most 1 empty wall + """ return any( ( len( @@ -117,12 +159,18 @@ class Maze: for cell in wall.neighbour_cells() ) - def wall_leaf_neighbours(self, coord: WallCoord) -> list[WallCoord]: + def wall_leaf_neighbours(self, wall: WallCoord) -> list[WallCoord]: + """ + From each junction between this wall and other walls, gets either an + empty list if at least one of them is full, otherwise the list of said + neighbour walls. + Returns the result of that operation concatenated for both junctions + """ leaf_f: Callable[ [Callable[[WallCoord], list[WallCoord]]], list[WallCoord] ] = lambda f: ( - list(filter(lambda c: self.check_coord(c), f(coord))) - if all(not wall for wall in self.get_walls_checked(f(coord))) + list(filter(lambda c: self.check_wall(c), f(wall))) + if all(not wall for wall in self.get_walls_checked(f(wall))) else [] ) return leaf_f(WallCoord.a_neighbours) + leaf_f(WallCoord.b_neighbours) diff --git a/mazegen/maze/network_tracker.py b/mazegen/maze/network_tracker.py index 128cda9..6f557e8 100644 --- a/mazegen/maze/network_tracker.py +++ b/mazegen/maze/network_tracker.py @@ -5,7 +5,6 @@ from mazegen.utils.coords import ( ) from mazegen.utils import AVLTree, AVLLeaf, SplitWall, WallCoord from mazegen.utils.avl import BVHKey -from mazegen.utils.quadtree import Rect class DualForest: @@ -33,6 +32,10 @@ class DualForest: self, split_wall: SplitWall, ) -> SplitWall | None: + """ + Attemps to find a full split wall starting after the given wall, + going counter clockwise + """ split_wall = split_wall_opposite(split_wall) for _ in range(3): split_wall = split_wall_ccw(split_wall) @@ -41,6 +44,9 @@ class DualForest: return None def fill_wall(self, wall: WallCoord) -> None: + """ + Updates that this wall is full, and maintains the countour forest + """ if self.get_wall(wall): return a_wall, b_wall = wall.to_split_wall() @@ -123,6 +129,9 @@ class DualForest: self.__trees.add(res) def empty_wall(self, wall: WallCoord) -> None: + """ + Updates that this wall is empty, and maintains the countour forest + """ if not self.get_wall(wall): return a_wall, b_wall = wall.to_split_wall() @@ -150,19 +159,16 @@ class DualForest: self.__trees.add(res) def get_wall(self, wall: WallCoord) -> bool: + """ + Checks whether the given wall is full + """ a_wall, b_wall = wall.to_split_wall() return a_wall in self.__revmap and b_wall in self.__revmap - def contour_bound(self, wall: SplitWall) -> Rect | None: - if wall not in self.__revmap: - return None - leaf = self.__revmap[wall] - parent = leaf.root() - if parent.root is None: - raise Exception() - return parent.root.key.rect - def wall_bisects(self, wall: WallCoord) -> bool: + """ + Returns whether this wall, if full, would split the maze in two + """ a_wall, b_wall = wall.to_split_wall() a_split = self.find_split(a_wall) b_split = self.find_split(b_wall) @@ -176,6 +182,10 @@ class DualForest: class NetworkTracker: + """ + A tracker of wall countour networks, used to check maze connectivity + """ + def __init__(self, maze: Maze) -> None: self.__maze: Maze = maze self.__forest: DualForest = DualForest() @@ -191,10 +201,13 @@ class NetworkTracker: self.__forest.empty_wall(wall) def wall_bisects(self, wall: WallCoord) -> bool: + """ + Returns whether this wall, if full, would split the maze in two + """ return self.__forest.wall_bisects(wall) - def contour_bound(self, wall: SplitWall) -> Rect | None: - return self.__forest.contour_bound(wall) - def end(self) -> None: + """ + Removes this tracker's observers from the maze + """ self.__maze.observers.discard(self.__observer) diff --git a/mazegen/maze/output.py b/mazegen/maze/output.py index e710ada..e02461f 100644 --- a/mazegen/maze/output.py +++ b/mazegen/maze/output.py @@ -4,6 +4,9 @@ from mazegen.maze.path import pathfind_astar def to_hex(cell: list[bool]) -> str: + """ + Converts a list of bits to a hex digit + """ val = ( (1 if cell[0] else 0) + (2 if cell[1] else 0) @@ -14,6 +17,9 @@ def to_hex(cell: list[bool]) -> str: def format_maze(maze: Maze) -> str: + """ + Formats the maze to a string in with hex cells as specified by the subject + """ dims = maze.dims maze_str = "" for y in range(dims.y): @@ -29,12 +35,19 @@ def format_maze(maze: Maze) -> str: def format_doors(maze: Maze) -> str: + """ + Formats the entry and exit to a string as specified by the subject + """ entry = f"{maze.entry.x},{maze.entry.y}\n" exit = f"{maze.exit.x},{maze.exit.y}\n" return entry + exit def format_path(maze: Maze) -> str: + """ + Formats the shortest path in the maze to a direction string as specificer + by the subject + """ path = pathfind_astar(maze) if path is None: raise Exception("Could not pathfind!") @@ -42,4 +55,7 @@ def format_path(maze: Maze) -> str: def format_output(maze: Maze) -> str: + """ + Formats the maze to an output string as the subject asks + """ return format_maze(maze) + "\n" + format_doors(maze) + format_path(maze) diff --git a/mazegen/maze/pacman_tracker.py b/mazegen/maze/pacman_tracker.py index c39d838..7fecd32 100644 --- a/mazegen/maze/pacman_tracker.py +++ b/mazegen/maze/pacman_tracker.py @@ -4,6 +4,10 @@ from mazegen.utils import Randset, WallCoord class PacmanTracker: + """ + A simple tracker that keeps track of dirty cells for impass removal + """ + def __init__(self, maze: Maze) -> None: self.__maze: Maze = maze self.__dirty: Randset[WallCoord] = Randset() @@ -21,12 +25,21 @@ class PacmanTracker: self.__dirty.add(e) def clear(self) -> Randset[WallCoord]: + """ + Clears the current set of dirty walls and returns it + """ res = self.__dirty self.__dirty = Randset() return res def curr_dirty(self) -> Iterable[WallCoord]: + """ + Returns an iterator over the currently dirty elements + """ return self.__dirty def end(self) -> None: + """ + Removes this tracker's observer from the maze + """ self.__maze.observers.discard(self.__observer) diff --git a/mazegen/maze/path.py b/mazegen/maze/path.py index e62688f..9ebf337 100644 --- a/mazegen/maze/path.py +++ b/mazegen/maze/path.py @@ -1,4 +1,3 @@ -from collections.abc import Generator from dataclasses import dataclass from mazegen.maze.maze import Maze from mazegen.utils.coords import Cardinal, CellCoord @@ -7,6 +6,9 @@ import heapq def taxicab_distance(a: IVec2, b: IVec2) -> int: + """ + Returns the taxicab/manhattan distance between two points + """ return sum(a.with_op(lambda lhs, rhs: abs(lhs - rhs), b).xy()) @@ -15,6 +17,11 @@ type LinkPath = None | tuple[Cardinal, LinkPath] @dataclass(slots=True) class AStarStep: + """ + A step in A* pathfinding, containing the previously traversed path as + well as distance heuristics for the grid + """ + dst: CellCoord path: LinkPath path_length: int @@ -27,6 +34,10 @@ class AStarStep: ) def append(self, card: Cardinal, dst: CellCoord) -> "AStarStep": + """ + Adds the current direction to the path and returns it, with target + coord dst + """ next_dst = self.dst.get_neighbour(card) next_path = (card, self.path) next_dist = self.path_length + 1 @@ -34,9 +45,15 @@ class AStarStep: return AStarStep(next_dst, next_path, next_dist, next_min_dist) def ends_in_bounds(self, maze: Maze) -> bool: + """ + Checks whether this step ends within the maze + """ return maze.check_cell(self.dst) def to_path(self) -> list[Cardinal]: + """ + Turns this step to a path as a list of cardinal directions + """ curr = self.path res = [] while curr is not None: @@ -47,6 +64,9 @@ class AStarStep: def pathfind_astar(maze: Maze) -> list[Cardinal] | None: + """ + Finds the shortest path between the entrance and exit using A* + """ src = maze.entry dst = maze.exit queue = [AStarStep(src, None, 0, taxicab_distance(src, dst))] @@ -65,12 +85,3 @@ def pathfind_astar(maze: Maze) -> list[Cardinal] | None: visited.add(nxt.dst) heapq.heappush(queue, nxt) return None - - -def path_pixels(curr: CellCoord, path: list[Cardinal]) -> Generator[IVec2]: - yield curr.tile_coords() - for card in path: - nxt = curr.get_neighbour(card) - yield (curr.tile_coords() + nxt.tile_coords()) // IVec2.splat(2) - yield nxt.tile_coords() - curr = nxt diff --git a/mazegen/maze/pattern.py b/mazegen/maze/pattern.py index ef38b48..29df958 100644 --- a/mazegen/maze/pattern.py +++ b/mazegen/maze/pattern.py @@ -4,6 +4,10 @@ from mazegen.maze import Maze class Pattern: + """ + A pattern to be filled into the maze + """ + FT_PATTERN: list[str] = [ "# ###", "# #", @@ -25,9 +29,15 @@ class Pattern: } def offset(self, by: IVec2) -> "Pattern": + """ + Offsets the pattern by a vector and returns the result + """ return Pattern({CellCoord(cell + by) for cell in self.__cells}) def flood_filled(self) -> "Pattern": + """ + Fills the pattern to avoid enclosed spaces and returns it + """ dims = self.dims() border = {CellCoord(-1, -1)} reachable = set() @@ -38,7 +48,7 @@ class Pattern: def coord_propagate(coord: CellCoord) -> Iterable[CellCoord]: return ( cell - for cell in coord.neighbours_unchecked() + for cell in coord.neighbours() if cell not in self.__cells and cell not in reachable and cell not in border @@ -59,12 +69,21 @@ class Pattern: return Pattern(full - reachable) def add_cell(self, cell: CellCoord) -> None: + """ + Adds a cell to the pattern + """ self.__cells.add(cell) def remove_cell(self, cell: CellCoord) -> None: + """ + Removes a cell from the pattern + """ self.__cells.discard(cell) def dims(self) -> IVec2: + """ + Computes the dims of the pattern + """ dim_by: Callable[[Callable[[CellCoord], int]], int] = lambda f: ( max(map(lambda c: f(c) + 1, self.__cells), default=0) - min(map(f, self.__cells), default=0) @@ -72,6 +91,10 @@ class Pattern: return IVec2(dim_by(lambda e: e.x), dim_by(lambda e: e.y)) def normalized(self) -> "Pattern": + """ + Make it so there is at least one cell with a zero coordinate in each + dimension, and none negative + """ min_by: Callable[[Callable[[CellCoord], int]], int] = lambda f: min( map(f, self.__cells), default=0 ) @@ -79,15 +102,18 @@ class Pattern: return self.offset(offset) def mirrored(self) -> "Pattern": + """ + Flips the pattern vertically and horizontally + """ return Pattern({CellCoord(IVec2.splat(0) - e) for e in self.__cells}) 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 + """ + Centers the pattern for the given canvas without enclosing any coords + in excluding + """ normalized: Pattern = self.normalized() negative = normalized.flood_filled().mirrored() dims = normalized.dims() @@ -115,6 +141,10 @@ class Pattern: return Pattern([]) def fill(self, maze: "Maze") -> None: + """ + Fills the pattern into the maze by filling the walls of each pattern + cell + """ for cell in self.__cells: for wall in cell.walls(): maze.set_wall(wall, True) diff --git a/mazegen/utils/avl.py b/mazegen/utils/avl.py index e8e3eb4..9106d00 100644 --- a/mazegen/utils/avl.py +++ b/mazegen/utils/avl.py @@ -15,10 +15,17 @@ class Key(ABC): """ @abstractmethod - def reconcile(self, rhs: Self) -> Self: ... + def reconcile(self, rhs: Self) -> Self: + """ + The function that is called to recompute the parent node as needed + """ class NoopKey(Key): + """ + An AVL key that does nothing to reconciliate + """ + instance: Self | None = None def __new__(cls) -> Self: @@ -36,16 +43,26 @@ class NoopKey(Key): class BVHKey(Key): + """ + An AVL key that maintains a bounding rectangle for each subtree + """ + def __init__(self, rect: Rect) -> None: super().__init__() self.rect: Rect = rect @staticmethod def for_cell(cell: CellCoord) -> "BVHKey": + """ + Makes the BVH that corresponds to the given cell + """ return BVHKey((cell, cell + IVec2.splat(1))) @staticmethod def for_wall(wall: SplitWall) -> "BVHKey": + """ + Makes the BVH that corresponds to the given split wall + """ return BVHKey.for_cell(wall[0]) def reconcile(self, rhs: Key) -> "BVHKey": @@ -67,6 +84,9 @@ class Tree[K: Key, V]: return f"{self.root}" if self.root is not None else "(empty)" def validate(self) -> None: + """ + Checks that the AVL tree is valid and acyclic, for debugging + """ if self.root is not None: self.root.validate() @@ -76,6 +96,10 @@ class Tree[K: Key, V]: return iter(self.root) def append(self, key: K, value: V) -> "Leaf[K, V]": + """ + Adds the given key and value at the end of the tree, returns the + created leaf + """ if self.root is None: leaf = Leaf(self, key, value) self.root = leaf @@ -90,6 +114,10 @@ class Tree[K: Key, V]: return cast(Leaf[K, V], self.root.rhs) def prepend(self, key: K, value: V) -> "Leaf[K, V]": + """ + Adds the given key and value at the start of the tree, returns the + created leaf + """ if self.root is None: leaf = Leaf(self, key, value) self.root = leaf @@ -104,21 +132,37 @@ class Tree[K: Key, V]: return cast(Leaf[K, V], self.root.lhs) def height(self) -> int: + """ + Returns the height of the tree + """ return 0 if self.root is None else self.root.height def is_empty(self) -> bool: + """ + Returns whether this tree is empty + """ return self.root is None def replace(self, node: "Node[K, V]", by: "Node[K, V]") -> None: + """ + Replace a node by another in this node's children, asserting it is + present + """ if node is not self.root: raise Exception("Replace operation with unknown node") self.root = by by.parent = self def balance_update_propagate(self) -> None: + """ + Propagate the balance update of the tree upwards if needed + """ return def exchange(self, other: "Tree[K, V]") -> None: + """ + Exchange the two trees' roots in-place + """ a = self.root b = other.root if a is not None: @@ -129,6 +173,9 @@ class Tree[K: Key, V]: self.root = b def ljoin(self, lhs: "Tree[K, V]") -> None: + """ + Joins the tree to the left of self + """ if self is lhs: raise Exception("Cannot merge tree with itself") if self.height() >= lhs.height(): @@ -138,6 +185,9 @@ class Tree[K: Key, V]: self.exchange(lhs) def rjoin(self, rhs: "Tree[K, V]") -> None: + """ + Joins the tree to the right of self + """ if self is rhs: raise Exception("Cannot merge tree with itself") if self.height() >= rhs.height(): @@ -147,6 +197,9 @@ class Tree[K: Key, V]: self.exchange(rhs) def __ljoin(self, lhs: "Tree[K, V]") -> None: + """ + Joins the tree to the left of self, assuming self is taller than lhs + """ if self.root is None: self.exchange(lhs) if self.root is None or lhs.root is None: @@ -167,6 +220,9 @@ class Tree[K: Key, V]: parent.balance_update_propagate() def __rjoin(self, rhs: "Tree[K, V]") -> None: + """ + Joins the tree to the right of self, assuming self is taller than rhs + """ if self.root is None: self.exchange(rhs) if self.root is None or rhs.root is None: @@ -188,6 +244,10 @@ class Tree[K: Key, V]: class Node[K: Key, V](ABC): + """ + The abstract class of a node in an AVL tree + """ + __slots__: tuple[str, ...] = ("parent", "height", "key") def __init__(self, parent: "Branch[K, V] | Tree[K, V]", key: K) -> None: @@ -199,6 +259,9 @@ class Node[K: Key, V](ABC): def __iter__(self) -> Iterator[V]: ... def validate(self) -> None: + """ + Validates this node by checking it is acyclic for debugging + """ visited = set() border: list[Node[K, V]] = [self] while len(border): @@ -211,17 +274,36 @@ class Node[K: Key, V](ABC): border.append(curr.rhs) def with_parent(self, parent: "Branch[K, V] | Tree[K, V]") -> "Node[K, V]": + """ + Changes this node's parent and return self + """ self.parent = parent return self def root(self) -> Tree[K, V]: + """ + Get the root of the tree this node belongs to + """ if isinstance(self.parent, Tree): return self.parent return self.parent.root() + def remove(self) -> None: + """ + Removes this leaf from this node's parent tree + """ + if isinstance(self.parent, Tree): + self.parent.root = None + return + other = self.parent.get_other(self) + self.parent.parent.replace(self.parent, other) + other.parent.balance_update_propagate() + def split_up(self) -> tuple[Tree[K, V], Tree[K, V]]: """ - makes self.parent empty + Makes the root of this tree empty, and returns two trees which + maintain the order of the previous, left and right of this node + respectively """ curr = self lhs = Tree[K, V]() @@ -243,6 +325,10 @@ class Node[K: Key, V](ABC): class Branch[K: Key, V](Node[K, V]): + """ + A branch in an AVL tree, which necessarily has two children + """ + __slots__: tuple[str, ...] = ("lhs", "rhs") def __init__( @@ -271,6 +357,10 @@ class Branch[K: Key, V](Node[K, V]): ) def replace(self, node: Node[K, V], by: Node[K, V]) -> None: + """ + Replace a node by another in this node's children, asserting it is + present + """ if self.lhs is node: self.lhs = by elif self.rhs is node: @@ -280,6 +370,9 @@ class Branch[K: Key, V](Node[K, V]): by.parent = self def get_other(self, node: Node[K, V]) -> Node[K, V]: + """ + Returns the node that is not the given one in this branche's children + """ if self.lhs is node: return self.rhs elif self.rhs is node: @@ -288,15 +381,28 @@ class Branch[K: Key, V](Node[K, V]): raise Exception("Get other operation with unknown node") def update_height(self) -> None: + """ + Update this branch's height from its children + """ self.height = max(self.lhs.height, self.rhs.height) + 1 def update_key(self) -> None: + """ + Update this branche's key from its children + """ self.key = self.lhs.key.reconcile(self.rhs.key) def get_balance(self) -> int: + """ + Returns the AVL balance of this node + """ return self.rhs.height - self.lhs.height def rotate_rr(self) -> None: + """ + Rotates the subtree such that the right node of the right node is + lifted up + """ # Simple AVL rotate: # # n --> m @@ -328,6 +434,10 @@ class Branch[K: Key, V](Node[K, V]): m.parent.replace(self, m) def rotate_ll(self) -> None: + """ + Rotates the subtree such that the left node of the left node is + lifted up + """ # Simple AVL rotate: # # m --> n @@ -359,6 +469,10 @@ class Branch[K: Key, V](Node[K, V]): n.parent.replace(self, n) def rotate_rl(self) -> None: + """ + Rotates the subtree such that the left node of the right node is + lifted up + """ # Double AVL rotate: # # n --> n --> m @@ -375,6 +489,10 @@ class Branch[K: Key, V](Node[K, V]): self.rotate_rr() def rotate_lr(self) -> None: + """ + Rotates the subtree such that the right node of the left node is + lifted up + """ # Double AVL rotate: # # o --> o --> m @@ -392,6 +510,9 @@ class Branch[K: Key, V](Node[K, V]): n = self.lhs def append(self, key: K, value: V) -> "Leaf[K, V]": + """ + Append the given key and value to the end of this subtree + """ if isinstance(self.rhs, Branch): return self.rhs.append(key, value) new = Branch[K, V]( @@ -405,6 +526,9 @@ class Branch[K: Key, V](Node[K, V]): return new_leaf def prepend(self, key: K, value: V) -> "Leaf[K, V]": + """ + Prepend the given key and value to the end of this subtree + """ if isinstance(self.lhs, Branch): return self.lhs.prepend(key, value) new = Branch[K, V]( @@ -418,6 +542,10 @@ class Branch[K: Key, V](Node[K, V]): return new_leaf def balance_one(self) -> None: + """ + Balances, if necessary, the left and right hand sides of this subtree, + through AVL rotations + """ if abs(self.get_balance()) <= 1: return @@ -439,6 +567,9 @@ class Branch[K: Key, V](Node[K, V]): self.rotate_ll() def balance_update_propagate(self) -> None: + """ + Balance this subtree, then propagate up if necessary + """ init_height = self.height init_key = self.key self.update_height() @@ -449,6 +580,10 @@ class Branch[K: Key, V](Node[K, V]): class Leaf[K: Key, V](Node[K, V]): + """ + A leaf in an AVL Tree + """ + __slots__: tuple[str, ...] = ("value",) def __init__( @@ -465,11 +600,3 @@ class Leaf[K: Key, V](Node[K, V]): def __repr__(self) -> str: return f"leaf ({self.key}): {self.value}" - - def remove(self) -> None: - if isinstance(self.parent, Tree): - self.parent.root = None - return - other = self.parent.get_other(self) - self.parent.parent.replace(self.parent, other) - other.parent.balance_update_propagate() diff --git a/mazegen/utils/bi_map.py b/mazegen/utils/bi_map.py index d32e6cb..3771dd9 100644 --- a/mazegen/utils/bi_map.py +++ b/mazegen/utils/bi_map.py @@ -6,12 +6,19 @@ from mazegen.utils.avl import ( class BiMap[K, R]: + """ + A simple bidirectional map from elemnts to set of elements + """ + def __init__(self) -> None: self.__map: dict[K, AVLTree[AVLNoopKey, R]] = {} self.__revmap: dict[AVLTree[AVLNoopKey, R], K] = {} self.__leafmap: dict[R, AVLLeaf[AVLNoopKey, R]] = {} def add(self, key: K, revkey: R) -> None: + """ + Adds the given association to the map + """ if self.revcontains(revkey): self.revremove(revkey) if not self.contains(key): @@ -21,11 +28,17 @@ class BiMap[K, R]: self.__leafmap[revkey] = self.__map[key].append(AVLNoopKey(), revkey) def remove(self, key: K) -> None: + """ + Removes the given association from the map + """ for revkey in self.__map[key]: self.__leafmap.pop(revkey) self.__revmap.pop(self.__map.pop(key)) def revremove(self, revkey: R) -> None: + """ + Removes the given reverse association from the map + """ leaf = self.__leafmap.pop(revkey) root = leaf.root() leaf.remove() @@ -33,12 +46,21 @@ class BiMap[K, R]: self.__map.pop(self.__revmap.pop(root)) def get(self, key: K) -> AVLTree[AVLNoopKey, R]: + """ + Gets the set of elements associated with this key + """ return self.__map[key] if self.contains(key) else AVLTree() def revget(self, revkey: R) -> K: + """ + Gets the key associated with this element + """ return self.__revmap[self.__leafmap[revkey].root()] def key_map(self, src: K, dst: K) -> None: + """ + Moves all elements of the source key to the destination key + """ if src == dst: return if src not in self.__map: @@ -50,7 +72,13 @@ class BiMap[K, R]: self.__map[dst].rjoin(self.__map.pop(src)) def contains(self, key: K) -> bool: + """ + Checks whether this map contains the given key + """ return key in self.__map def revcontains(self, revkey: R) -> bool: + """ + Checks whether this map contains the given element + """ return revkey in self.__leafmap diff --git a/mazegen/utils/coords.py b/mazegen/utils/coords.py index ee7d0f5..a6b2933 100644 --- a/mazegen/utils/coords.py +++ b/mazegen/utils/coords.py @@ -1,9 +1,14 @@ +from collections.abc import Generator from enum import Enum, auto from typing import Iterable, cast, overload from mazegen.utils.ivec2 import IVec2 class Orientation(Enum): + """ + A simple orientation enum + """ + HORIZONTAL = auto() VERTICAL = auto() @@ -14,12 +19,19 @@ class Orientation(Enum): class Cardinal(Enum): + """ + A cardinal direction + """ + NORTH = auto() SOUTH = auto() EAST = auto() WEST = auto() def opposite(self) -> "Cardinal": + """ + Gets the cardinal direction opposite of this one + """ match self: case Cardinal.NORTH: return Cardinal.SOUTH @@ -31,6 +43,9 @@ class Cardinal(Enum): return Cardinal.EAST def left(self) -> "Cardinal": + """ + Gets the cardinal direction left of this one + """ match self: case Cardinal.NORTH: return Cardinal.WEST @@ -42,6 +57,9 @@ class Cardinal(Enum): return Cardinal.SOUTH def right(self) -> "Cardinal": + """ + Gets the cardinal direction right of this one + """ return self.left().opposite() def __str__(self) -> str: @@ -57,10 +75,16 @@ class Cardinal(Enum): @staticmethod def all() -> list["Cardinal"]: + """ + Returns the list of all cardinal directions + """ return [Cardinal.NORTH, Cardinal.SOUTH, Cardinal.EAST, Cardinal.WEST] @staticmethod def path_to_tiles(path: list["Cardinal"], src: "CellCoord") -> list[IVec2]: + """ + Return the tile coords from a path and start + """ res = [src.tile_coords()] for card in path: nxt = src.get_neighbour(card) @@ -75,23 +99,23 @@ class Cardinal(Enum): def path_to_cells( path: list["Cardinal"], src: "CellCoord" ) -> list["CellCoord"]: + """ + Return the cell coords from a path and start + """ res = [src] for card in path: src = src.get_neighbour(card) res.append(src) return res - @staticmethod - def path_to_walls( - path: list["Cardinal"], src: "CellCoord" - ) -> list["WallCoord"]: - return [ - cell.get_wall(card) - for cell, card in zip(Cardinal.path_to_cells(path, src), path) - ] - class WallCoord: + """ + Wall coordinates + a is the position in the list of lines/columns, and b is the position in + said line/column + """ + def __init__(self, orientation: Orientation, a: int, b: int) -> None: self.orientation: Orientation = orientation self.a: int = a @@ -111,6 +135,10 @@ class WallCoord: return hash(self.__members()) def a_neighbours(self) -> list["WallCoord"]: + """ + Returns the neighbours of this wall on an arbitrary a side + distinct from b_neighbours + """ return [ WallCoord(self.orientation.opposite(), self.b, self.a - 1), WallCoord(self.orientation, self.a, self.b - 1), @@ -118,6 +146,10 @@ class WallCoord: ] def b_neighbours(self) -> list["WallCoord"]: + """ + Returns the neighbours of this wall on an arbitrary b side + distinct from a_neighbours + """ return [ WallCoord(self.orientation.opposite(), self.b + 1, self.a - 1), WallCoord(self.orientation, self.a, self.b + 1), @@ -125,9 +157,15 @@ class WallCoord: ] def neighbours(self) -> list["WallCoord"]: + """ + Returns the list of all neigbours for this wall, in arbitrary order + """ return self.a_neighbours() + self.b_neighbours() def tile_coords(self) -> Iterable[IVec2]: + """ + Returns the tile coords for this wall + """ a: Iterable[int] = [self.a * 2] b: Iterable[int] = [self.b * 2, self.b * 2 + 1, self.b * 2 + 2] x_iter: Iterable[int] = ( @@ -139,6 +177,9 @@ class WallCoord: return (IVec2(x, y) for x in x_iter for y in y_iter) def neighbour_cells(self) -> tuple["CellCoord", "CellCoord"]: + """ + Returns the cells that are besides this wall + """ if self.orientation == Orientation.HORIZONTAL: return ( CellCoord(self.b, self.a), @@ -152,6 +193,10 @@ class WallCoord: def to_split_wall( self, ) -> tuple["SplitWall", "SplitWall"]: + """ + Returns the split wall of each side of this wall + """ + def find_cardinal(cell: CellCoord) -> Cardinal: for cardinal in Cardinal.all(): if cell.get_wall(cardinal) == self: @@ -163,6 +208,10 @@ class WallCoord: class CellCoord(IVec2): + """ + A cell coordinate, essentially an IVec2[int] with extra methods + """ + @overload def __init__(self, val: IVec2, /) -> None: ... @@ -176,9 +225,15 @@ class CellCoord(IVec2): super().__init__(a.x, a.y) def walls(self) -> Iterable[WallCoord]: + """ + Returns an iterable over the wall of this cell + """ return map(self.get_wall, Cardinal.all()) def get_wall(self, cardinal: Cardinal) -> WallCoord: + """ + Returns the wall of this cell in the given direction + """ match cardinal: case Cardinal.NORTH: return WallCoord(Orientation.HORIZONTAL, self.y, self.x) @@ -190,6 +245,9 @@ class CellCoord(IVec2): return WallCoord(Orientation.VERTICAL, self.x + 1, self.y) def get_neighbour(self, cardinal: Cardinal) -> "CellCoord": + """ + Returns the cell neighbour of this cell in the given direction + """ return next( filter( lambda e: e != self, self.get_wall(cardinal).neighbour_cells() @@ -197,17 +255,20 @@ class CellCoord(IVec2): ) def tile_coords(self) -> IVec2: + """ + Returns the tile coord of this cell + """ return IVec2(self.x * 2 + 1, self.y * 2 + 1) - def offset(self, by: IVec2) -> "CellCoord": - return CellCoord(self + by) - - def all_up_to(self) -> Iterable["CellCoord"]: + def all_up_to(self) -> Generator["CellCoord"]: + """ + Yields every cell from the origin up to self exclusive + """ for x in range(0, self.x): for y in range(0, self.y): yield CellCoord(x, y) - def neighbours_unchecked(self) -> Iterable["CellCoord"]: + def neighbours(self) -> Iterable["CellCoord"]: return map(self.get_neighbour, Cardinal.all()) @@ -215,12 +276,21 @@ type SplitWall = tuple[CellCoord, Cardinal] def split_wall_cw(wall: SplitWall) -> SplitWall: + """ + Rotates a split wall clockwise + """ return (wall[0].get_neighbour(wall[1]), wall[1].right()) def split_wall_ccw(wall: SplitWall) -> SplitWall: + """ + Rotates a split wall counter-clockwise + """ return (wall[0].get_neighbour(wall[1]), wall[1].left()) def split_wall_opposite(wall: SplitWall) -> SplitWall: + """ + Gets the opposite of a split wall + """ return (wall[0].get_neighbour(wall[1]), wall[1].opposite()) diff --git a/mazegen/utils/ivec2.py b/mazegen/utils/ivec2.py index 825ab3d..ae492a0 100644 --- a/mazegen/utils/ivec2.py +++ b/mazegen/utils/ivec2.py @@ -3,9 +3,16 @@ from typing import Type class IVec2[T = int]: + """ + A simlpe two dimensional vector class + """ + __slots__: tuple[str, str] = ("x", "y") def copy(self, inner_copy: Callable[[T], T] = lambda e: e) -> "IVec2[T]": + """ + Makes a copy of this vector to avoid pass-by-reference semantics + """ return IVec2(inner_copy(self.x), inner_copy(self.y)) def __init__(self, x: T, y: T) -> None: @@ -14,6 +21,9 @@ class IVec2[T = int]: @staticmethod def splat(n: T) -> "IVec2[T]": + """ + Creates a vector with each element set to the given avlue + """ return IVec2(n, n) def __repr__(self) -> str: @@ -22,12 +32,19 @@ class IVec2[T = int]: def with_op[T2]( self, op: Callable[[T, T], T2], other: "IVec2[T]" ) -> "IVec2[T2]": + """ + Returns the result of op applied to each horizontal pair of elemnts + in the vector, returning the result as a vector + """ return IVec2( op(self.x, other.x), op(self.y, other.y), ) def innertype(self) -> Type[T]: + """ + Returns the type of the inner values + """ return type(self.x) def __mul__(self, other: "IVec2[T]") -> "IVec2[T]": @@ -56,13 +73,25 @@ class IVec2[T = int]: return hash((self.x, self.y)) def lane_min(self, other: "IVec2[T]") -> "IVec2[T]": + """ + Obtains the pairwise minimum of each element + """ return IVec2(min(self.x, other.x), min(self.y, other.y)) # type:ignore def lane_max(self, other: "IVec2[T]") -> "IVec2[T]": + """ + Obtains the pairwise maximum of each element + """ return IVec2(max(self.x, other.x), max(self.y, other.y)) # type:ignore def xy(self) -> tuple[T, T]: + """ + Returns the x and y coords in a tuple + """ return (self.x, self.y) def yx(self) -> tuple[T, T]: + """ + Returns the y and x coords in a tuple + """ return (self.y, self.x) diff --git a/mazegen/utils/quadtree.py b/mazegen/utils/quadtree.py index 5d8c772..e487be4 100644 --- a/mazegen/utils/quadtree.py +++ b/mazegen/utils/quadtree.py @@ -7,11 +7,17 @@ type tuple4[T] = tuple[T, T, T, T] def map4[T, U](fn: Callable[[T], U], tup: tuple4[T]) -> tuple4[U]: + """ + Like map, but typed for a tuple4 + """ 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]]: + """ + Like zip, but typed for a tuple4 + """ a1, b1, c1, d1 = a a2, b2, c2, d2 = b return ((a1, a2), (b1, b2), (c1, c2), (d1, d2)) @@ -25,6 +31,9 @@ type Rect = tuple[IVec2, IVec2] def rects_overlap(a: Rect, b: Rect) -> bool: + """ + Checks whether two rectangles overlap + """ a_start, a_end = a b_start, b_end = b return ( @@ -36,6 +45,9 @@ def rects_overlap(a: Rect, b: Rect) -> bool: def rect_collides(a: Rect, b: IVec2) -> bool: + """ + Checks whether two rectangles collide + """ a_start, a_end = a return ( a_end.x > b.x @@ -46,6 +58,9 @@ def rect_collides(a: Rect, b: IVec2) -> bool: def rect_contains(a: Rect, b: Rect) -> bool: + """ + Checks whether a rect contains another + """ a_start, a_end = a b_start, b_end = b return ( @@ -57,6 +72,10 @@ def rect_contains(a: Rect, b: Rect) -> bool: class Tree: + """ + A boolean quadtree, with simplification for identical subcells + """ + def __init__(self, copy: "Tree | None" = None) -> None: self.__root: MaybeNode = False self.__height: int = 0 @@ -72,6 +91,10 @@ class Tree: return f"Quadtree: height - {self.__height}, data:\n{data}" def raised_to(self, target: int) -> "Tree": + """ + Increase the height of this tree and extend it to reach at least + target height + """ res = Tree(self) while res.__height < target: res.__root = (self.__root, False, False, False) @@ -79,6 +102,10 @@ class Tree: return res def normalized(self) -> "Tree": + """ + Lowers the tree for as long as can be simplified, to reach a canonical + form + """ res = Tree(self) while True: match res.__root: @@ -94,6 +121,10 @@ class Tree: def shared_layer_apply( self, fn: Callable[[MaybeNode, MaybeNode], MaybeNode], other: "Tree" ) -> "Tree": + """ + Applies the given function between two nodes that are at the same + layer and thus position + """ res = self.raised_to(other.__height) def descend(node: MaybeNode, depth: int = 0) -> MaybeNode: @@ -125,6 +156,10 @@ class Tree: def node_tiles( node: MaybeNode, pos: IVec2, height: int ) -> Generator[IVec2]: + """ + Iterates over the tile coords of a given node with a given position + and height + """ if height == 0 and node is True: yield pos if height == 0 or node is False: @@ -137,6 +172,9 @@ class Tree: @staticmethod def rectangle(rect: Rect) -> "Tree": + """ + Creates a tree that contains exactly a rectangle + """ res = Tree() while (s := 1 << res.__height) < rect[1].x or s < rect[1].y: res.__height += 1 @@ -145,6 +183,9 @@ class Tree: @staticmethod def node_to_tab(node: MaybeNode, height: int) -> list[list[bool]]: + """ + Creates a two dimensional array of booleans corresponding to this node + """ if isinstance(node, bool): dim = 1 << height return [[node for _ in range(dim)] for _ in range(dim)] @@ -160,6 +201,9 @@ class Tree: @staticmethod def node_normalize(node: MaybeNode) -> MaybeNode: + """ + Normalize this node by simlpifying when possible + """ match node: case (True, True, True, True): return True @@ -169,6 +213,9 @@ class Tree: @staticmethod def node_split(node: MaybeNode) -> Node: + """ + Split this node once, unsimplifying it + """ match node: case True: return (True, True, True, True) @@ -178,6 +225,10 @@ class Tree: @staticmethod def node_from_rect(pos: IVec2, height: int, rect: Rect) -> MaybeNode: + """ + Creates a node from a rectangle and is position, such that it fills + its overlapping region with that rectagle + """ node_rect = Tree.node_rect(pos, height) if rect_contains(rect, node_rect): return True @@ -191,10 +242,16 @@ class Tree: @staticmethod def node_rect(pos: IVec2, height: int) -> Rect: + """ + Returns the rectangle corresponding to a node's position and height + """ return (pos, pos + IVec2.splat(1 << height)) @staticmethod def node_starts(pos: IVec2, height: int) -> tuple4[IVec2]: + """ + Return the start of each sub-node of a node + """ dim = 1 << (height - 1) x = IVec2(dim, 0) y = IVec2(0, dim) @@ -208,12 +265,18 @@ class Tree: @staticmethod def node_neg(node: MaybeNode) -> MaybeNode: + """ + Inverts a node + """ if isinstance(node, bool): return not node return map4(Tree.node_neg, node) @staticmethod def node_or(a: MaybeNode, b: MaybeNode) -> MaybeNode: + """ + Applies a boolean or between two nodes + """ match (a, b): case (True, _) | (_, True): return True @@ -228,6 +291,9 @@ class Tree: @staticmethod def node_and(a: MaybeNode, b: MaybeNode) -> MaybeNode: + """ + Applies a boolean and between two nodes + """ match (a, b): case (False, _) | (_, False): return False @@ -242,6 +308,9 @@ class Tree: @staticmethod def node_sub(a: MaybeNode, b: MaybeNode) -> MaybeNode: + """ + Substracts another node from a first + """ match (a, b): case (False, _) | (_, True): return False diff --git a/mazegen/utils/randset.py b/mazegen/utils/randset.py index 6989f38..b168d88 100644 --- a/mazegen/utils/randset.py +++ b/mazegen/utils/randset.py @@ -3,6 +3,11 @@ from typing import cast, overload class Randset[T](MutableSequence[T], MutableSet[T]): + """ + A simple datastructure that acts as a set but also allows allows random + popping and indexing + """ + def __init__(self) -> None: self.__elems: list[T] = [] self.__idx_map: dict[T, int] = {} -- 2.53.0