Utils: maze

Maze generation and analysis helpers.

Utility routines for producing and querying grid mazes used in sample levels or procedural content generation. The algorithms favor clarity and deterministic reproducibility via an injected random.Random instance.

Functions

generate_perfect_maze: Depth-first backtracking perfect maze generator (no cycles, single path between any two open cells) with optional edge opening to guarantee exit accessibility on borders.

bfs_path

Breadth-first search shortest path (unweighted) between two open cells.

all_required_path_positions

Computes the union of waypoints' shortest paths ensuring all required positions are visited in sequence.

adjust_maze_wall_percentage

Post-processes a perfect maze to tune overall wall density by randomly opening a proportion of remaining walls, enabling difficulty scaling or aesthetic variation.

adjust_maze_wall_percentage(maze, wall_percentage, rng)

Returns a new MazeGrid with wall percentage controlled. wall_percentage=0.0: fully open grid; 1.0: perfect maze (original).

all_required_path_positions(maze, start, required_positions, goal)

Returns all positions along the shortest paths from start -> required_position1 -> required_position2 -> ... -> goal.

bfs_path(maze, start, goal)

Finds the shortest path from start to goal using BFS. Only traverses open/floor cells. Returns the path as a list of coordinates (including both start and goal), or [] if unreachable.

generate_perfect_maze(width, height, rng, open_edge=True)

Generates a perfect maze using recursive backtracking. Returns a dict mapping (x, y) -> bool (True is open/floor, False is wall).