Maze Generator

Maze Generator is a two-dimensional random maze generator. It creates random rectangular mazes (see Wikipedia) which are spanning trees: the maze visits all cells without any loops. In other words, there is always one and only one route from any cell in the maze to any other cell. The maze dimensions can be selected freely, but for a graphical representation it is convenient to define the maze size based on window size and maze block size in pixels.

As usual, the Python code is in my GitHub repository.

Above: Two mazes with image size 1920 x 1080 and block sizes 25 pixels (740 cells) and 8 pixels (7,854 cells).

Algo-rhythm

Many maze generation algorithms rely on stacks to store information on where the process has previously visited on the grid. My algorithm tries to add randomness to the process by not doing that, which may or may not have a processing cost attached. First, I set up NumPy arrays for the maze: 

        # initialize an array of walls filled with ones, data "not visited" + if exists for 2 walls (down and right) per cell.
        self.wall_size = np.array([size_y, size_x], dtype=np.int)
        # add top, bottom, left, and right (ie. + 2 and + 2) to array size so can later work without checking going over its boundaries.
        self.walls = np.ones((self.wall_size[0] + 2, self.wall_size[1] + 2, 3), dtype=np.byte)
        # mark edges as "unusable" (-1)
        self.walls[:, 0, 0] = -1
        self.walls[:, self.wall_size[1] + 1, 0] = -1
        self.walls[0, :, 0] = -1
        self.walls[self.wall_size[0] + 1, :, 0] = -1

        # initialize an array of block data - each passage (0) and wall (1) is a block
        self.block_size = np.array([size_y * 2 + 1, size_x * 2 + 1], dtype=np.int)
        self.blocks = np.ones((self.block_size[0], self.block_size[1]), dtype=np.byte)

There a two variants of the maze grid array: self.walls is of size (y+2, x+2, 3) where the extra two rows and columns are used to mark the edges of the maze as unusable area, i.e. the maze creation will always stay within them, while in the actual process I do not have worry about trying to access data outside of the array. The three data points for each maze cell are cell, down wall, and right wall status, respectively. Only two of the walls are needed, as the other two are held in neighboring cells.

The other way of representing the maze is the array self.blocks, which is of size (y*2+1, x*2+1). This is strictly two-dimensional but contains approximately twice the amount of rows and columns compared to self.walls. Here the information is stored so that all odd blocks (y = 1, 3, 5 ... and x = 1, 3, 5 ...) are maze cells and the blocks between them (y is odd and x is even or vice versa) are walls between them. In the end, half the information is actually wasted, as all maze cells (odd blocks) will be visited anyway and the even blocks are always walls. However, this format is handy for drawing the maze.

Maze generation is based on the self.walls array. First, I set up some variables and randomly pick the starting cell anywhere within the maze:

        # set a random starting cell and mark it as "visited"
        cell = np.array([random.randrange(2, self.wall_size[0]), random.randrange(2, self.wall_size[1])], dtype=np.int)
        self.walls[cell[0], cell[1], 0] = 0

        # a simple definition of the four neighboring cells relative to current cell
        up    = np.array([-1,  0], dtype=np.int)
        down  = np.array([ 1,  0], dtype=np.int)
        left  = np.array([ 0, -1], dtype=np.int)
        right = np.array([ 0,  1], dtype=np.int)

        # preset some variables
        need_cell_range = False
        round_nr = 0
        corridor_start = 0
        if corridor_len <= 4:
            corridor_len = 5  # even this is too small usually

Then, I run a loop:

        while np.size(cell) > 0 and self.running:

            round_nr += 1
            # get the four neighbors for current cell (cell may be an array of cells)
            cell_neighbors = np.vstack((cell + up, cell + left, cell + down, cell + right))
            # valid neighbors are the ones not yet visited
            valid_neighbors = cell_neighbors[self.walls[cell_neighbors[:, 0], cell_neighbors[:, 1], 0] == 1]

As long as cell is not an empty array, I have been able to find the next cell to move into. To get the four neighboring cells is a simple task of adding the directions up, left, down, and right to cell coordinates. Of these cell_neighbors, I pick the valid_neighbors, i.e. neighboring cells that have not been visited yet (their "status byte" = 1). After moving away from the starting cell, there can be 0 to 3 valid neighbors for each cell, as the direction we came from is already used and hence not valid.

If there are valid neighbors, the size of the valid_neighbors array will not be zero:

            if np.size(valid_neighbors) > 0:
                # there is at least one valid neighbor, pick one of them (at random)
                neighbor = valid_neighbors[random.randrange(0, np.shape(valid_neighbors)[0]), :]
                if np.size(cell) > 2:
                    # if cell is an array of cells, pick one cell with this neighbor only, at random
                    cell = cell[np.sum(abs(cell - neighbor), axis=1) == 1]  # cells where distance to neighbor == 1
                    cell = cell[random.randrange(0, np.shape(cell)[0]), :]
                # mark neighbor visited
                self.walls[neighbor[0], neighbor[1], 0] = 0
                # remove the wall between current cell and neighbor. Applied to down and right walls only so may be that of the cell or the neighbor
                self.walls[min(cell[0], neighbor[0]), min(cell[1], neighbor[1]), 1 + abs(neighbor[1] - cell[1])] = 0
                if self.screen is not None:
                    # if screen is set, draw the corridor from cell to neighbor
                    self.draw_cell(cell, neighbor)
                # check if more corridor length is still available
                if round_nr - corridor_start < corridor_len:
                    # continue current corridor: set current cell to neighbor
                    cell = np.array([neighbor[0], neighbor[1]], dtype=np.int)
                else:
                    # maximum corridor length fully used; make a new junction and continue from there
                    need_cell_range = True

As said, there may be many valid neighbor cells. First, I pick one of them in random, in effect making the direction we are moving to random. However, there may also be many cells (an array of cells, not just one cell) used to create those neighbors - see below what happens when a junction is created. If that is the case (np.size(cell) > 2), I pick one of the cells which is a neighbor to the chosen neighbor cell. Then, the neighbor cell is marked as visited.

The wall to be removed between the cell and the neighbor must be a down or right side wall, so depending on the direction we are going to, it may belong to either the cell or the neighbor. This is simply solved by taking the minimum coordinates of the two cells, resulting in the upper (if moving vertically) or leftmost (if moving horizontally) of these two. In a similar fashion, the wall is defined by 1 + abs(neighbor[1] - cell[1]), which is 1 for a vertical move (cell and neighbor x coordinates are the same) and 2 for a horizontal move (x coordinates differ).

Finally, a check will be performed whether the current corridor has reached its maximum length and, if not, the cell pointer will be moved to neighbor just used. If the maximum has been reached, the current corridor will end, and the process will continue from creating a junction. It is not required to set a maximum corridor length - it is by default 999 - but using a small value will cause more junctions to be used and hence a somewhat different maze structure.

On the other hand, if there are no valid neighbors for the cell:

            else:
                # no valid neighbors for this cell
                if np.size(cell) > 2:
                    # if cell already contains an array of cells, no more valid neighbors are available at all
                    cell = np.zeros((0, 0))  # this will end the while loop, the maze is finished.
                    if self.screen is not None:
                        # if screen is set, make sure it is updated as the maze is now finished.
                        pygame.display.flip()
                else:
                    # a dead end; make a new junction and continue from there
                    need_cell_range = True

I test if there were multiple cells we tried to find a valid neighbor for. If there were, that means it is no longer possible to find any valid neighbors, and cell is set to an empty array, which will cause an exit from the while loop.

If there was only single cell we were looking for valid neighbors for, and none were found, we are at a dead end. This can easily happen e.g. if a corridor turns back to where it came from and enters a loop it has created, with no exits. Then we call for a junction to be created: 

            if need_cell_range:
                # get all visited cells (=0) not marked as "no neighbors" (=-1), start a new corridor from one of these (make a junction)
                cell = np.transpose(np.nonzero(self.walls[1:-1, 1:-1, 0] == 0)) + 1  # not checking the edge cells, hence needs the "+ 1"
                # check these for valid neighbors (any adjacent cell with "1" as visited status (ie. not visited) is sufficient, hence MAX)
                valid_neighbor_exists = np.array([self.walls[cell[:, 0] - 1, cell[:, 1], 0],
                                                  self.walls[cell[:, 0] + 1, cell[:, 1], 0],
                                                  self.walls[cell[:, 0], cell[:, 1] - 1, 0],
                                                  self.walls[cell[:, 0], cell[:, 1] + 1, 0]
                                                  ]).max(axis=0)
                # get all visited cells with no neighbors
                cell_no_neighbors = cell[valid_neighbor_exists != 1]
                # mark these (-1 = no neighbors) so they will no longer be actively used. This is not required but helps with large mazes.
                self.walls[cell_no_neighbors[:, 0], cell_no_neighbors[:, 1], 0] = -1
                corridor_start = round_nr + 0  # start a new corridor.
                need_cell_range = False

If we ran into a dead end or the maximum length of the corridor had been reached, we need a junction. For this, many algorithms "go back" the corridor to some point they can branch to a new direction; some even start from a random cell not visited to connect to the current maze. I chose to pick any cell we have already visited, which has valid neighbors. Thus, I continue from some random cell already in the maze where a junction can be created. This is achieved by first picking all the visited cells not marked as "no neighbors". To exclude the ones with no neighbors in the future, I take the maximum of their neighboring cells' statuses: status = 1 means not visited, 0 = visited and -1 = no neighbors. Of these the ones with no valid neighbors are then marked.

Note that the array cell still contains also the cells just marked as "no neighbors". I could have removed them, making the array smaller and faster, but that operation does have a cost, and in any case the next step (back at the beginning of the while loop) will drop out the cells with no valid neighbors. All in all, marking the cells as "no neighbors" is not mandatory - but it may with large mazes help by making the array cell smaller.

To get self.blocks I use the same maze generation code above (by calling self.gen_maze_walls), and just convert that data:

    def gen_maze_2D(self, corridor_len=999):

        # converts walls data from gen_maze_walls to a NumPy array size (y * 2 + 1, x * 2 + 1)
        # wall blocks are represented by 1 and corridors by 0.

        self.gen_maze_walls(corridor_len)

        if self.running:
            # use wall data to set final output maze
            self.blocks[1:-1:2, 1:-1:2] = 0  # every cell is visited if correctly generated
            # horizontal walls
            self.blocks[1:-1:2, 2:-2:2] = self.walls[1:-1, 1:-2, 2]  # use the right wall
            # vertical walls
            self.blocks[2:-2:2, 1:-1:2] = self.walls[1:-2, 1:-1, 1]  # use the down wall

Maze generator in 1280 x 720 resolution, running from block size 10 (2,205 cells) to block size 3 (25, 228 cells).

Use It or Lose It

In addition to the actual maze generation, there's a front end which sets up a window and draws the maze as it is generated. Use the following keys to control it:

• Space bar for a new maze
• f to toggle full screen mode on/off
• s to save a PNG image of the maze (to working directory)
• cursor up to create a new maze with a bigger block size 
• cursor down to create a new maze with a smaller block size
• ESC to exit

The program also prints out some statistics about maze size and generation time. While a HD window (1920 x 1080) maze with block size 10 pixels (i.e. 95 x 53 = 5,035 cells) can be generated and drawn in a fraction of a second, a bigger maze (same window but block size 3 i.e. 319 x 179 = 57,101 cells) takes around 10 seconds to generate and draw on my PC, and a few seconds less if just generating and not drawing it.

Coming Up Next: Maze Solver