Maze Solver

Maze Solver solves the maze generated by Maze Generator - see the previous post. Maze solver also adds an info display and a slow mode for viewing the operation in a more step-by-step fashion. In effect, it generates a maze using the Maze Generator, and then solves a route from any cell A to any other cell B within it, marking the attempted route by yellow color, and, when finding the goal, the correct passage by red color.

You can find the Python code in my GitHub repository. 

Problem Worth Solving

The maze is, by default, solved by starting from the bottom right corner cell and going to the top left corner cell. These cells can be changed using the mouse to solve the same maze again, but for a different route, or a new maze can be generated. By changing the cell size (using cursor keys) the maze can be made harder (smaller cell size) or easier (bigger cell size).

The algorithm to solve the maze is rather simple. First, I set us (cell) in the starting position, and define the directions available:

        cell = np.copy(self.start_pos)
        previous = np.copy(cell)

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

Then, looping until we find the end position, I mark the current cell as visited (2) and find its valid neighbors. A valid neighbor is a maze corridor cell next to the current cell but not yet visited (0). I am also storing the "main distance" to the goal to each neighbor. While a "true distance" would have been easy enough to calculate (sqrt(x^2 + y^2)) there is a small time saving in avoiding those calculations, and the simpler solution achieves the same.

        while self.running and not np.array_equal(cell, self.end_pos):

            self.blocks[cell[0], cell[1]] = 2  # mark as visited, prevents from turning back.
            # define target direction
            # get the four neighbors for current cell and the "main distance" to indicate preferable direction
            cell_neighbors = np.hstack((
                cell + directions,
                np.sum((self.end_pos - cell) * directions, axis=1)[:, None]
                ))
            # pick the ones which are corridors and not visited yet
            valid_neighbors = cell_neighbors[(self.blocks[cell_neighbors[:, 0], cell_neighbors[:, 1]] == 0)]
            vn_count = np.shape(valid_neighbors)[0]

vn_count stores the number of valid neighbors found. If there are more than one, we have come to a junction where it is possible to select from two or three directions. (We never go back. Never.) In that case,

            if vn_count > 1:
                # multiple directions available - add the cell to the junctions stack
                # if there are three valid neighbors, not to worry - the third one will be taken care of if this junction is returned to
                self.junction_nr += 1
                # make sure there is enough stack
                if self.junction_nr >= np.shape(self.junctions)[0]:
                    self.junctions = np.resize(self.junctions, (self.junction_nr + 100, 6))
                # junction: store data on cell location and its distance to the end_pos
                self.junctions[self.junction_nr, 0:2] = cell      # cell location
                self.junctions[self.junction_nr, 2:4] = previous  # previous location - needed when retracing the solution
                self.junctions[self.junction_nr, 4] = int(np.sqrt(np.sum((self.end_pos - cell) ** 2)))  # distance to end_pos
                self.junctions[self.junction_nr, 5] = vn_count    # nr of directions (valid neighbors) available

I store the junction location, with information about where we came to it from, how far it is from the goal, and how many directions it had available, to a self.junctions array. For large mazes, the array can grow quite large, so at some interval (100) I resize it to make sure there's room for more. The distance to the goal is here calculated properly, although it is stored as an integer, as all the other array items are integers anyway. The minor loss in accuracy has no significance.

Then it's time to decide where to go next. 

            if vn_count == 1:
                # one direction available, take it. Store previous cell to use when coming to a junction.
                previous = np.copy(cell)
                cell = valid_neighbors[0, 0:2]
                self.draw_cell(cell, previous, self.path_color)
            else:
                # either a dead end (vn_count = 0) or a junction (vn_count > 1): pick the junction with the shortest distance to end_pos with valid neighbors
                closest = np.argmin(self.junctions[:self.junction_nr + 1, 4])
                self.junctions[closest, 5] -= 1  # this junction now has one less valid neighbors left
                if self.junctions[closest, 5] == 0:
                    self.junctions[closest, 4] = 32767  # junction fully used - make it look like it is far away
                if np.array_equal(cell, self.junctions[closest, 0:2]):
                    # continuing from current junction = cell
                    previous = np.copy(cell)
                else:
                    # switched to a closer junction - get the valid neighbors for it
                    previous = np.copy(self.junctions[closest, 0:2])  # start from it
                    # get the four neighbors for current cell and the "main distance" to indicate preferable direction
                    cell_neighbors = np.hstack((
                        previous + directions,
                        np.sum((self.end_pos - previous) * directions, axis=1)[:, None]
                        ))
                    # pick the ones which are corridors and not visited yet
                    valid_neighbors = cell_neighbors[(self.blocks[cell_neighbors[:, 0], cell_neighbors[:, 1]] == 0)]
                # select the "best route" i.e. simply the one that takes us towards the end_pos most
                cell = valid_neighbors[np.argmax(valid_neighbors[:, 2]), 0:2]
                self.draw_cell(cell, previous, self.path_color)

If vn_count == 1, there's only one way to go, the one valid neighbor. However, if vn_count != 1, there are two options: if it is zero, we are at a dead end, with nowhere to go; if it is greater than one, we are at a junction with many possibilities. But it does not matter. Here, I always move to the junction closest to the goal, by picking the one with minimum distance to it. This seeks to ensure that we do not stray too far on corridors leading to the wrong direction.

When the junction to continue from has been selected, I check if there's only one direction left in it to take; if so, I mark it "fully used" by setting its distance to the goal very high, thus preventing it from ever being the minimum distance junction again. 

It may be the case that the closest junction was the one we were already in. But if not, we need to pick another set of valid neighbors. Then, I just select the best route by picking the neighbor (direction) that takes us best towards the goal.

To reiterate, the algorithm is simple:

• if in a corridor, continue forward;
• if a junction is found, store its data;
• if in a dead end or a junction, pick the junction not fully used and closest to the goal, and move to the corridor that best takes us closer to the goal.

Marking the Path

Now we have found the goal, but all we have is an array of junctions and knowledge of all the cells visited while searching for the route. Finding our way back to the starting position using the shortest route, i.e. the solution to the maze, goes as follows:

        previous = np.copy(cell)
        while self.running and not np.array_equal(cell, self.start_pos):
            self.blocks[cell[0], cell[1]] = 4  # mark as the correct route
            # find the way back. While this takes time it avoids storing all paths in memory.
            cell_neighbors = cell + directions
            valid_neighbors = cell_neighbors[(self.blocks[cell_neighbors[:, 0], cell_neighbors[:, 1]] == 2)]
            if np.shape(valid_neighbors)[0] == 1:
                # one way to go only
                cell = valid_neighbors[0, 0:2]
            else:
                # a junction. Find it in junctions to select direction (the "previous cell" stored in the junction - now returning to it).
                cell = self.junctions[:self.junction_nr + 1, 2:4][(self.junctions[:self.junction_nr + 1, 0] == previous[0]) &
                                                                  (self.junctions[:self.junction_nr + 1, 1] == previous[1])][0]
            self.draw_cell(cell, previous, self.solution_color)
            previous = np.copy(cell)

We are at the goal cell, to looping until we are back at start, I simply select valid_neighbors again, this time being the ones we visited when finding our way. If there are more than one, we are at a junction, and then the way to go is the cell we originally came to that junction from, and it can be found in the self.junctions array (where it was stored in the first place).

There's a difference between knowing the path and walking the path

Now, there are many algorithms out there to build and solve such mazes. The ones I have looked at mostly seem to use cell-type classes to store data in stack-like structures. As it is in any case required to have the maze (walls and corridors) stored in memory somehow, I found it easier and more efficient to store the data on progress (visited cells, solution) by changing the corridor type directly, and only the junctions as a stack-like data set. Hopping to the closest-to-goal junction every time another junction or a dead end is reached might not be what you could do when running in a garden maze, but it is definitely quicker here than retracing your footsteps from each dead end and/or always continuing from the last junction found.

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