Spaces:
Running on Zero
Running on Zero
File size: 4,650 Bytes
737fab6 6d196f1 737fab6 6d196f1 737fab6 6d196f1 737fab6 d780047 6d196f1 d780047 6d196f1 d780047 737fab6 d780047 6d196f1 d780047 737fab6 6d196f1 737fab6 6d196f1 737fab6 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 | """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]
|