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.