Spaces:
Sleeping
Sleeping
File size: 4,230 Bytes
737fab6 6d196f1 737fab6 6d196f1 737fab6 6d196f1 737fab6 6d196f1 737fab6 6d196f1 737fab6 d780047 6d196f1 d780047 6d196f1 d780047 737fab6 d780047 6d196f1 d780047 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 | import random
from collections import deque
def generate_hex_maze(radius, seed=0):
"""Backwards-compatible wrapper that uses the iterative implementation."""
return generate_hex_maze_iterative(radius, seed=seed)
def generate_hex_maze_iterative(radius, seed=0):
"""
Generate a hexagonal maze using an explicit stack (iterative DFS) on axial coords.
Args:
radius (int): maximum radius (in hex steps) from the origin to include.
Returns:
dict: mapping (q, r) -> list of (dq, dr) neighbor offsets for open edges.
"""
maze = {}
visited = set()
stack = [(0, 0)]
visited.add((0, 0))
dirs = [(1,0),(0,1),(-1,1),(-1,0),(0,-1),(1,-1)]
rng = random.Random(seed) if seed else None
while stack:
q,r = stack[-1]
directions = dirs[:] # ← fixed: copy before shuffle
(rng.shuffle(directions) if rng is not None else random.shuffle(directions))
moved = False
for dq,dr in directions:
nq,nr = q+dq,r+dr
if (nq,nr) not in visited and max(abs(nq),abs(nr),abs(nq+nr)) <= radius:
visited.add((nq,nr))
stack.append((nq,nr))
maze.setdefault((q,r),[]).append((dq,dr))
maze.setdefault((nq,nr),[]).append((-dq,-dr))
# occasional extra random connection (10%) to introduce loops and increase difficulty
if (rng.random() if rng is not None else random.random()) < 0.1:
# prefer connecting to an already visited neighbor so we create a loop
extra_dirs = [d for d in dirs if d != (dq,dr)]
(rng.shuffle(extra_dirs) if rng is not None else random.shuffle(extra_dirs))
for edq,edr in extra_dirs:
enq,enr = q+edq, r+edr
# only connect to already visited neighbours to avoid creating isolated cells
if (enq,enr) in visited and (edq,edr) not in maze.get((q,r), []):
maze.setdefault((q,r),[]).append((edq,edr))
maze.setdefault((enq,enr),[]).append((-edq,-edr))
break
moved = True
break
if not moved:
stack.pop()
# Ensure the starting hex has two additional neighbor offsets if possible.
# This makes the maze entry/exit from the center more open and increases difficulty.
# (If there are not enough valid neighbours within the radius, add as many as possible.)
if (0, 0) not in maze:
maze.setdefault((0, 0), [])
# choose up to two directions not already open from the start
available = [d for d in dirs if d not in maze.get((0, 0), []) and max(abs(d[0]), abs(d[1]), abs(d[0] + d[1])) <= radius]
(rng.shuffle(available) if rng is not None else random.shuffle(available))
for dq, dr in available[:2]:
nq, nr = dq, dr
# add reciprocal entries even if the neighbour wasn't previously in the maze
if (dq, dr) not in maze.get((0, 0), []):
maze.setdefault((0, 0), []).append((dq, dr))
maze.setdefault((nq, nr), []).append((-dq, -dr))
return maze
def solve_hex_maze(maze):
"""
Solve a hex maze (produced by generate_hex_maze) using breadth-first search.
Args:
maze (dict): mapping (q, r) -> list of (dq, dr) neighbor offsets.
Returns:
list[tuple[int,int]]: sequence of axial coordinates from the origin to the
farthest cell (heuristic goal) in the generated maze. Returns empty list
for an empty maze.
"""
if not maze:
return []
start = (0,0)
end = max(maze, key=lambda p: abs(p[0])+abs(p[1])+abs(p[0]+p[1]))
queue = deque([start])
parent = {start: None}
while queue:
curr = queue.popleft()
if curr == end:
break
for dq,dr in maze.get(curr,[]):
neigh = (curr[0]+dq, curr[1]+dr)
if neigh not in parent:
parent[neigh] = curr
queue.append(neigh)
path = []
at = end
while at:
path.append(at)
at = parent.get(at)
return path[::-1] |