Spaces:
Sleeping
Sleeping
| 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] |