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

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)

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]

*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

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 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

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)