Spaces:
Sleeping
Sleeping
| """Triangle-grid maze helpers. | |
| This module implements a simple triangular-grid maze generator (randomized | |
| depth-first search), a BFS solver and a drawing helper that renders the | |
| triangular tiling with walls and optional thin grey outlines for doors. | |
| Maze representation: | |
| dict mapping (x,y) -> list of (dx,dy) neighbor offsets that are open. | |
| Coordinates: | |
| x: column index, 0..w-1 | |
| y: row index, 0..h-1 | |
| Triangle orientation alternates with parity: up when (x+y) % 2 == 0, | |
| otherwise down. | |
| """ | |
| import random | |
| from collections import deque | |
| from .draw import draw_tri_maze as _draw_tri | |
| def _neighbor_offsets(x, y, w, h): | |
| """Return valid neighbor offsets for triangle at (x,y) based on orientation.""" | |
| up = ((x + y) % 2 == 0) | |
| if up: | |
| candidates = [(-1, 0), (1, 0), (0, 1)] | |
| else: | |
| candidates = [(-1, 0), (1, 0), (0, -1)] | |
| valid = [] | |
| for dx, dy in candidates: | |
| nx, ny = x + dx, y + dy | |
| if 0 <= nx < w and 0 <= ny < h: | |
| valid.append((dx, dy)) | |
| return valid | |
| def generate_tri_maze(w, h=None, seed=0): | |
| """Generate a triangular maze using randomized DFS. | |
| Args: | |
| w (int): number of columns. | |
| h (int|None): number of rows (if None, equals w). | |
| Returns: | |
| dict: mapping (x,y) -> list of neighbor offsets (dx,dy) that are open. | |
| """ | |
| if h is None: | |
| h = w | |
| # initialize empty adjacency | |
| maze = {(x, y): [] for x in range(w) for y in range(h)} | |
| rng = random.Random(seed) if seed else None | |
| visited = set() | |
| stack = [(0, 0)] | |
| visited.add((0, 0)) | |
| while stack: | |
| x, y = stack[-1] | |
| offs = _neighbor_offsets(x, y, w, h) | |
| # filter to unvisited neighbours | |
| nbrs = [(dx, dy) for dx, dy in offs if (x + dx, y + dy) not in visited] | |
| if nbrs: | |
| dx, dy = (rng.choice(nbrs) if rng is not None else random.choice(nbrs)) | |
| nx, ny = x + dx, y + dy | |
| # carve passage both ways (store offsets) | |
| maze[(x, y)].append((dx, dy)) | |
| maze[(nx, ny)].append((-dx, -dy)) | |
| visited.add((nx, ny)) | |
| stack.append((nx, ny)) | |
| # occasional extra random connection (10%) to introduce loops and increase difficulty | |
| if (rng.random() if rng is not None else random.random()) < 0.1: | |
| extra_offs = [o for o in offs if o != (dx, dy)] | |
| (rng.shuffle(extra_offs) if rng is not None else random.shuffle(extra_offs)) | |
| for edx, edy in extra_offs: | |
| enx, eny = x + edx, y + edy | |
| # connect only to already visited neighbours to avoid isolating cells | |
| if (enx, eny) in visited and (edx, edy) not in maze.get((x, y), []): | |
| maze[(x, y)].append((edx, edy)) | |
| maze[(enx, eny)].append((-edx, -edy)) | |
| break | |
| else: | |
| stack.pop() | |
| # ensure the starting triangle (0,0) has one additional neighbour offset if possible | |
| start_offs = _neighbor_offsets(0, 0, w, h) | |
| candidates = [o for o in start_offs if o not in maze.get((0, 0), [])] | |
| if candidates: | |
| edx, edy = (rng.choice(candidates) if rng is not None else random.choice(candidates)) | |
| nx, ny = 0 + edx, 0 + edy | |
| if (edx, edy) not in maze.get((0, 0), []): | |
| maze[(0, 0)].append((edx, edy)) | |
| maze[(nx, ny)].append((-edx, -edy)) | |
| return maze | |
| def generate_tri_maze_iterative(w, h=None, seed=0): | |
| """Alias for generate_tri_maze; generation is already iterative. | |
| Kept for API symmetry with other generators. | |
| """ | |
| return generate_tri_maze(w, h, seed=seed) | |
| def solve_tri_maze(maze): | |
| """Solve a triangular maze returning a path from start to end. | |
| Start is assumed at (0,0). End is chosen as the cell with the maximum | |
| x+y (bottom-right-like) so it aligns with the drawing and CLI examples. | |
| Returns: | |
| list[(x,y)]: path from start to end (inclusive) or empty list if none. | |
| """ | |
| if not maze: | |
| return [] | |
| start = (0, 0) | |
| end = max(maze, key=lambda p: p[0] + p[1]) | |
| q = deque([start]) | |
| parent = {start: None} | |
| while q: | |
| cur = q.popleft() | |
| if cur == end: | |
| break | |
| x, y = cur | |
| for dx, dy in maze.get((x, y), []): | |
| nx, ny = x + dx, y + dy | |
| if (nx, ny) not in parent: | |
| parent[(nx, ny)] = (x, y) | |
| q.append((nx, ny)) | |
| if end not in parent: | |
| return [] | |
| # reconstruct path | |
| path = [] | |
| at = end | |
| while at is not None: | |
| path.append(at) | |
| at = parent.get(at) | |
| return path[::-1] | |