Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- from random import sample
- from typing import List, Tuple
- # A generated maze will have walls surrounding the pathways, so + 2 to the size,
- # and then the walls themselves will be 1 thick, so the size is doubled.
- # False for if there's a wall/if you cannot go through the current cell,
- # True for if it is a valid pathway.
- type MazeCell = bool
- # Making a type alias for readability
- type Position = Tuple[int, int]
- # ---------- UTILITY DEFINITIONS ----------
- # Setting a cell to be True, aka explored
- def set_explored(maze: List[List[MazeCell]], pos: Position) -> None:
- maze[pos[0] * 2 + 1][pos[1] * 2 + 1] = True
- # Checking that a cell is a valid pathway
- def in_bounds(maze: List[List[MazeCell]], pos: Position) -> bool:
- return 0 < pos[0] * 2 + 1 < len(maze) and 0 < pos[1] * 2 + 1 < len(maze[0])
- # Checking that a cell is False in the maze, aka unexplored
- def unexplored(maze: List[List[MazeCell]], pos: Position) -> bool:
- return not maze[pos[0] * 2 + 1][pos[1] * 2 + 1]
- # Setting the cell between 2 positions to be True, aka explored
- def remove_wall_between(
- maze: List[List[MazeCell]], pos_a: Position, pos_b: Position
- ) -> None:
- between_pos = (pos_a[0] + pos_b[0] + 1, pos_a[1] + pos_b[1] + 1)
- maze[between_pos[0]][between_pos[1]] = True
- neighbour_offsets: list[Position] = [(0, 1), (0, -1), (1, 0), (-1, 0)]
- # ---------- MAZE ALGORITHMS ----------
- def generate_maze_recursive(
- maze: List[List[MazeCell]], curr_pos: Position
- ) -> None:
- # Sets the current cell to be explored
- set_explored(maze, curr_pos)
- # Randomly shuffles the neighbour_offsets, so that the maze generator will go in random directions
- for offset in sample(neighbour_offsets, k=len(neighbour_offsets)):
- # Calculating the neighbour's position
- neighbour_pos: Position = (
- curr_pos[0] + offset[0],
- curr_pos[1] + offset[1],
- )
- if in_bounds(maze, neighbour_pos) and unexplored(maze, neighbour_pos):
- remove_wall_between(maze, curr_pos, neighbour_pos)
- generate_maze_recursive(maze, neighbour_pos)
- def generate_maze_iterative(
- maze: List[List[MazeCell]], starting_pos: Position
- ) -> None:
- # A stack based approach, where the below keeps track of where the generator _was_,
- # and then also where it currently _is_
- explore_stack: List[Tuple[Position | None, Position]] = [
- # Initialized with None in the previous position
- (None, starting_pos)
- ]
- while len(explore_stack) > 0:
- prev_pos, curr_pos = explore_stack.pop()
- # Need to check that the current position is _still_ unexplored,
- # as it could've been explored in the meantime.
- if not unexplored(maze, curr_pos):
- continue
- elif prev_pos is not None:
- remove_wall_between(maze, prev_pos, curr_pos)
- set_explored(maze, curr_pos)
- for offset in sample(neighbour_offsets, k=len(neighbour_offsets)):
- # Calculating the neighbour's position
- neighbour_pos: Position = (
- curr_pos[0] + offset[0],
- curr_pos[1] + offset[1],
- )
- if in_bounds(maze, neighbour_pos) and unexplored(maze, neighbour_pos):
- # Instead of recursing, I'm adding to the explore stack
- explore_stack.append((curr_pos, neighbour_pos))
- # ---------- RUNNING IT ----------
- maze_size = 10
- maze: List[List[MazeCell]] = [
- [False for _ in range(maze_size * 2 + 1)] for _ in range(maze_size * 2 + 1)
- ]
- # generate_maze_recursive(maze, (0, 0))
- generate_maze_iterative(maze, (0, 0))
- pretty_maze = "\n".join("".join(" " if cell else "x" for cell in row) for row in maze)
- print(pretty_maze)
Advertisement
Add Comment
Please, Sign In to add comment