eniallator

Maze generation algorithms

Dec 8th, 2025
117
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 3.75 KB | None | 0 0
  1. from random import sample
  2. from typing import List, Tuple
  3.  
  4.  
  5. # A generated maze will have walls surrounding the pathways, so + 2 to the size,
  6. #   and then the walls themselves will be 1 thick, so the size is doubled.
  7.  
  8. # False for if there's a wall/if you cannot go through the current cell,
  9. #   True for if it is a valid pathway.
  10. type MazeCell = bool
  11.  
  12. # Making a type alias for readability
  13. type Position = Tuple[int, int]
  14.  
  15.  
  16. # ---------- UTILITY DEFINITIONS ----------
  17.  
  18.  
  19. # Setting a cell to be True, aka explored
  20. def set_explored(maze: List[List[MazeCell]], pos: Position) -> None:
  21.     maze[pos[0] * 2 + 1][pos[1] * 2 + 1] = True
  22.  
  23.  
  24. # Checking that a cell is a valid pathway
  25. def in_bounds(maze: List[List[MazeCell]], pos: Position) -> bool:
  26.     return 0 < pos[0] * 2 + 1 < len(maze) and 0 < pos[1] * 2 + 1 < len(maze[0])
  27.  
  28.  
  29. # Checking that a cell is False in the maze, aka unexplored
  30. def unexplored(maze: List[List[MazeCell]], pos: Position) -> bool:
  31.     return not maze[pos[0] * 2 + 1][pos[1] * 2 + 1]
  32.  
  33.  
  34. # Setting the cell between 2 positions to be True, aka explored
  35. def remove_wall_between(
  36.     maze: List[List[MazeCell]], pos_a: Position, pos_b: Position
  37. ) -> None:
  38.     between_pos = (pos_a[0] + pos_b[0] + 1, pos_a[1] + pos_b[1] + 1)
  39.     maze[between_pos[0]][between_pos[1]] = True
  40.  
  41.  
  42. neighbour_offsets: list[Position] = [(0, 1), (0, -1), (1, 0), (-1, 0)]
  43.  
  44.  
  45. # ---------- MAZE ALGORITHMS ----------
  46.  
  47.  
  48. def generate_maze_recursive(
  49.     maze: List[List[MazeCell]], curr_pos: Position
  50. ) -> None:
  51.     # Sets the current cell to be explored
  52.     set_explored(maze, curr_pos)
  53.     # Randomly shuffles the neighbour_offsets, so that the maze generator will go in random directions
  54.     for offset in sample(neighbour_offsets, k=len(neighbour_offsets)):
  55.         # Calculating the neighbour's position
  56.         neighbour_pos: Position = (
  57.             curr_pos[0] + offset[0],
  58.             curr_pos[1] + offset[1],
  59.         )
  60.         if in_bounds(maze, neighbour_pos) and unexplored(maze, neighbour_pos):
  61.             remove_wall_between(maze, curr_pos, neighbour_pos)
  62.             generate_maze_recursive(maze, neighbour_pos)
  63.  
  64.  
  65. def generate_maze_iterative(
  66.     maze: List[List[MazeCell]], starting_pos: Position
  67. ) -> None:
  68.     # A stack based approach, where the below keeps track of where the generator _was_,
  69.     #   and then also where it currently _is_
  70.     explore_stack: List[Tuple[Position | None, Position]] = [
  71.         # Initialized with None in the previous position
  72.         (None, starting_pos)
  73.     ]
  74.     while len(explore_stack) > 0:
  75.         prev_pos, curr_pos = explore_stack.pop()
  76.         # Need to check that the current position is _still_ unexplored,
  77.         #   as it could've been explored in the meantime.
  78.         if not unexplored(maze, curr_pos):
  79.             continue
  80.         elif prev_pos is not None:
  81.             remove_wall_between(maze, prev_pos, curr_pos)
  82.         set_explored(maze, curr_pos)
  83.         for offset in sample(neighbour_offsets, k=len(neighbour_offsets)):
  84.             # Calculating the neighbour's position
  85.             neighbour_pos: Position = (
  86.                 curr_pos[0] + offset[0],
  87.                 curr_pos[1] + offset[1],
  88.             )
  89.             if in_bounds(maze, neighbour_pos) and unexplored(maze, neighbour_pos):
  90.                 # Instead of recursing, I'm adding to the explore stack
  91.                 explore_stack.append((curr_pos, neighbour_pos))
  92.  
  93.  
  94. # ---------- RUNNING IT ----------
  95.  
  96.  
  97. maze_size = 10
  98.  
  99. maze: List[List[MazeCell]] = [
  100.     [False for _ in range(maze_size * 2 + 1)] for _ in range(maze_size * 2 + 1)
  101. ]
  102.  
  103. # generate_maze_recursive(maze, (0, 0))
  104. generate_maze_iterative(maze, (0, 0))
  105.  
  106. pretty_maze = "\n".join("".join(" " if cell else "x" for cell in row) for row in maze)
  107.  
  108. print(pretty_maze)
Advertisement
Add Comment
Please, Sign In to add comment