Module moog.maze_lib.maze_generators

This file contains functions to randomly generate mazes.

The main function in this file is generate_random_maze_matrix(), which generates a maze with no dead ends and no open squares.

Functions

def generate_random_maze_matrix(size, ambient_size=None)

Expand source code

def generate_random_maze_matrix(size, ambient_size=None):
    """Generate a random maze matrix.

    The maze matrix generated has no open points (e.g. no four open cells
    sharing a vertex), no dead ends (e.g. each open point has at least two open
    neighbors), and is one connected component.

    The way this generator works is it starts will a single open cell (all other
    cells are walls). Then it iteratively adds closed neighbors, as long as
    opening them doesn't open up a block. Once there are no more such neighbors,
    it iteratively fills in all dead ends. The result is the final maze matrix
    (unless it is all walls, in which case the function recurses to try again).

    Args:
        size: Int. Size (height and width) of the maze.
        ambient_size: Size of the final maze matrix. This can be larger than
            `size` to add some visible wall border around the maze. If None, no
            wall border around the maze is produced.
    """
    maze = np.ones((size, size))

    # Start from a random point and recursively open points
    closed_neighbors = []  # Closed points that are neighbors of open points
    
    def _open_point(point):
        # Open a point and add its neighbors to closed_neighbors
        for p in _get_neighbors(size, point):
            if maze[p[0], p[1]] and p not in closed_neighbors:
                closed_neighbors.append(p)
        maze[point[0], point[1]] = 0

    def _find_and_open_new_point():
        # Find a closed neighbor that can be opened without creating an open
        # block, open it, and return True. If no such point exists, return
        # False.
        np.random.shuffle(closed_neighbors)
        for new_point in closed_neighbors:
            if not maze[new_point[0], new_point[1]]:
                continue
            will_make_open_block = any([
                np.sum(maze[i: i + 2, j: j + 2]) <= 1
                for i, j in _get_containing_blocks(size, new_point)
            ])
            if not will_make_open_block:
                _open_point(new_point)
                return True
        return False

    # Seed the maze and iteratively open points
    _open_point(tuple(np.random.randint(0, size, size=(2,))))
    points_to_add = True
    while points_to_add:
        points_to_add = _find_and_open_new_point()

    # Remove dead ends
    _remove_dead_ends(maze)
    
    # If maze has no open points, recurse to generate a new one
    if np.sum(1 - maze) == 0:
        return generate_random_maze_matrix(size, ambient_size=ambient_size)

    # Add wall border if necessary
    if ambient_size is not None and ambient_size > size:
        maze_with_border = np.ones((ambient_size, ambient_size))
        start_index = (ambient_size - size) // 2
        maze_with_border[start_index: start_index + size,
                         start_index: start_index + size] = maze
        maze = maze_with_border

    return maze

Generate a random maze matrix.

The maze matrix generated has no open points (e.g. no four open cells sharing a vertex), no dead ends (e.g. each open point has at least two open neighbors), and is one connected component.

The way this generator works is it starts will a single open cell (all other cells are walls). Then it iteratively adds closed neighbors, as long as opening them doesn't open up a block. Once there are no more such neighbors, it iteratively fills in all dead ends. The result is the final maze matrix (unless it is all walls, in which case the function recurses to try again).

Args

size

Int. Size (height and width) of the maze.

ambient_size

Size of the final maze matrix. This can be larger than size to add some visible wall border around the maze. If None, no wall border around the maze is produced.

def get_connected_open_blob(maze, num_points)

Expand source code

def get_connected_open_blob(maze, num_points):
    """Generate an open connected blob of `num_points` points in the maze.
    
    Args:
        maze: Instance of .maze.Maze.
        num_points: Int. Number of connected points to have in the blob.

    Returns:
        blob_matrix: Binary matrix of same size as maze. Ones correspond to
            points in the connected open blob.
    """
    valid_blob = False
    count = 0
    while not valid_blob:
        count += 1
        if count > _MAX_ITERS:
            raise ValueError('Could not generate an open connected blob.')
        
        blob_matrix = _generate_open_blob(maze, num_points)
        if not isinstance(blob_matrix, bool):
            valid_blob = True
    
    return blob_matrix

Generate an open connected blob of num_points points in the maze.

Args

maze

Instance of .maze.Maze.

num_points

Int. Number of connected points to have in the blob.

Returns

blob_matrix

Binary matrix of same size as maze. Ones correspond to points in the connected open blob.