Created
February 14, 2024 18:17
-
-
Save toaster-code/a2fdcee99e5b1279b579a58f8d813156 to your computer and use it in GitHub Desktop.
A maze-builder script made in python
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| """ A maze builder algorithm. | |
| Based on accepted answer at this post from stackoverflow: | |
| https://stackoverflow.com/questions/29739751/implementing-a-randomly-generated-maze-using-prims-algorithm/29758926#29758926 | |
| The main logic is in the dig method in the class Maze. Once provided with a list of `fronts` to explore, the algorithm will | |
| dig a maze in 2 steps movement (avoiding creating open rooms). | |
| Assumptions: | |
| - A frontier is a cell chosen to explore for its neighbours, digging from it until there are no move moves available. | |
| - The algorithm does not intersect an existing tunnel. It shall continue digging avoiding passage areas. | |
| It works as follows: | |
| 1 - Pick a random cell from `front` list to explore (call it `current_cell`) | |
| 2 - Check current_cell's valid neighbors. This way, two situations can happen: | |
| A - current_cell has no valid neighbors | |
| B - current_cell has valid neighbors | |
| Case A: | |
| 3 - current_cell has no valid neighbors, so remove it from `frontiers` list. | |
| 4 - Repeat from 1 until there are no more frontiers to explore. | |
| Case B: | |
| 3 - current_cell has valid neighbors, so random pick one and call it `new_cell`. | |
| 4 - Mark the new_cell (which is 2 steps away from current cell) | |
| 5 - Mark the cell between current_cell and new_cell, creating a passage. | |
| 6 - Add new_cell to the `frontiers` list (so it shall be explored again in the future). | |
| Repeat from 1 until there are no more frontiers to explore. | |
| Notes: Cells are marked as a passage before adding them to frontiers list. | |
| So each time a new frontier is selected to explore the maze, there is no need to paint it again. | |
| This assures that when looking for a new neighbor, the rejected neighbor cells does not reappears in the frontiers list. | |
| It is a simple way to avoid adding the same cell to the frontiers list multiple times. | |
| It also avoids adding cells that are already part of the maze. | |
| """ | |
| from matplotlib import pyplot as plt | |
| import random | |
| rng = random.Random() | |
| # rng.seed(55) | |
| class Cell: | |
| Wall = 1 | |
| Passage = 0 | |
| class Maze: | |
| def __init__(self, width, height, verbose=False, debug_plot=False): | |
| self.width = width | |
| self.height = height | |
| self.grid = [[Cell.Wall for _ in range(width)] for _ in range(height)] # Initialize grid with all walls | |
| self.verbose = verbose # Set to True to print the dig process | |
| self.debug_plot = debug_plot # Set to True to plot the maze dig process | |
| def is_legal(self, x, y): | |
| """ Check if the coordinates are within the maze. | |
| A cell is legal when within 1 cell from the border. | |
| """ | |
| return (0 < x < self.width - 1) and (0 < y < self.height - 1) | |
| def is_wall(self, x, y): | |
| return self.grid[y][x] == Cell.Wall | |
| def filter_neighbors(self, x, y): | |
| """Get the valid neighbor cells to the x, y coordinates. | |
| Valid neighbors are 2 cells away, whithin valid maze area, and are marked as wall. | |
| Note: This 2 cells away check allows exploring walls. It does not Interconnect tunnels. | |
| So the maze has only one solution to the end. | |
| """ | |
| validator = filter( | |
| lambda xy: self.is_legal(*xy) and self.is_wall(*xy), | |
| [(x - 2, y), (x + 2, y), (x, y - 2), (x, y + 2)] | |
| ) | |
| return list(validator) | |
| def neighbor(self, x, y): | |
| return [(x - 2, y), (x + 2, y), (x, y - 2), (x, y + 2)] | |
| def get_random_cell(self): | |
| """Get a random cell within the maze. | |
| This cell depends on the size of the maze, and should be pair. | |
| """ | |
| return rng.randint(0, (self.width - 1)//2)*2, rng.randint(0, (self.height - 1)//2)*2 | |
| def create_passage(self, p1, p2): | |
| """ Mark the destination and the cell between p1, p2. They should be spaced by 2 cells. | |
| It does not mark the current cell. | |
| """ | |
| dx = p2[0] - p1[0] | |
| dy = p2[1] - p1[1] | |
| if (dx == 2 and dy == 0) or (dx == -2 and dy == 0) or (dx == 0 and dy == 2) or (dx == 0 and dy == -2): | |
| x = p1[0] + dx // 2 | |
| y = p1[1] + dy // 2 | |
| self.grid[y][x] = Cell.Passage # Mark the cell between p1, p2 as passage | |
| self.grid[p2[1]][p2[0]] = Cell.Passage # Mark the destination cell as passage | |
| else: | |
| raise ValueError("Invalid path") | |
| def dig(self, frontiers:list): | |
| """ | |
| Dig the maze. | |
| Once provided with a list of fronts to explore. This function will dig the maze. | |
| A frontier is a new cell to explore for its neighbours. | |
| The algorithm works as follows: | |
| 1 - Pick a random cell from `front` list to explore (call it `current_cell`) | |
| 2 - Check current_cell's valid neighbors. Two situations can happen: | |
| 2.A - current_cell has no valid neighbors: | |
| Remove current_cell from `frontiers` list. | |
| 2.B - current_cell has valid neighbors: | |
| 2.B.1 - Random pick one of the neighbors (new_cell). | |
| 2.B.2 - Mark the new_cell and the passage between current_cell and new_cell (creating a passage) | |
| 2.B.3 - Add new_cell to the `frontiers` list | |
| Repeat until there are no more frontiers to explore. | |
| Notes: This code assumes that cells are marked as passage before adding them to frontiers list. | |
| This assures that when looking for a new neighbor, the rejected neighbor cells are not in the frontiers list. | |
| This is a simple way to avoid adding the same cell to the frontiers list multiple times. It also avoids | |
| adding cells that are already part of the maze to the frontiers list. | |
| """ | |
| while frontiers: # No frontier cells left to connect to the maze | |
| picked_index = rng.randint(0, len(frontiers) - 1) # Pick a random frontier cell to explore | |
| current_cell = frontiers[picked_index] # Get the coordinates of the picked frontier cell | |
| neighbors = self.filter_neighbors(*current_cell) # Get valid neighbors of the picked frontier cell | |
| if not neighbors: # If there are no valid neighbors | |
| frontiers.pop(picked_index) # Remove it from the frontier list | |
| else: | |
| new_cell = neighbors[rng.randint(0, len(neighbors) - 1)] # Pick a random neighbor | |
| xn, yn = new_cell | |
| if 0 <= xn <= self.width-1 and 0 <= yn <= self.height-1: # check if new_cell coordinates are within the maze | |
| self.create_passage(current_cell, new_cell) # Dig a passage between the current cell and the neighbor | |
| frontiers += [new_cell] # Add new_cell to the frontier list | |
| if self.debug_plot: | |
| plt.imshow(self.grid, cmap='gray_r', origin='lower') | |
| if self.verbose: | |
| print(f"current_cell: {current_cell}; new_cell: {new_cell}; frontiers no: {len(frontiers)}") | |
| # close border: | |
| for y in range(self.height-1): | |
| self.grid[y][0] = Cell.Wall | |
| self.grid[y][self.width-1] = Cell.Wall | |
| def generate_maze(width, height, verbose=False): | |
| maze = Maze(width, height, verbose=verbose) | |
| cell = maze.get_random_cell() | |
| maze.grid[cell[1]][cell[0]] = Cell.Passage | |
| maze.dig([cell]) | |
| return maze.grid | |
| if __name__ == "__main__": | |
| maze = generate_maze(31, 31, verbose=False) | |
| plt.imshow(maze, cmap='gray_r', origin='lower') | |
| plt.show() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment