Python - Maze Example - Dot Net Perls

Maze. For simple mazes, a Python program can be used to navigate from a start to an endpoint. Some algorithms are advanced, but this is not always needed.

With a simple pathfinding algorithm, we can find a path from one point to another while avoiding obstacles (walls). Our intelligent agent can keep trying moves until it reaches its goal.

Example program. Here is the example maze-solving program. It is divided into a few methods. The maze string uses characters to indicate walls, a start, line separators, and an end.

Start We introduce get_maze_lists to parse in a string into a list of lists. With int arrays we can process the maze easier.

Info Display() prints the maze_lists in a character format. It is used to show our agent's progress.

Detail When we try to move to a new square, we want to ensure the square is on the map—here valid_pos will tell us.

Detail Modify_path takes the current data and moves the agent in one possible direction. It returns a value that indicates what happened.

# The maze string, use "x" for a wall, 1 for start. maze = """ xxx1. x x . x2x x. xxx . x x . x xx"""; def get_maze_lists(maze): # Split on period. lines_raw = maze.split(".") # Remove newlines. lines_stripped = list(map(lambda line: line.strip("\n"), lines_raw)) # Result 2D array. result = [] for line in lines_stripped: # Create row. row = [] for char in line: if char == "x": row.append(-1) elif char == "1": row.append(1) elif char == "2": row.append(-3) else: row.append(0) # Add row to result. result.append(row) return result def display(maze_lists): # Display current maze progress. for row in maze_lists: line = "" for column in row: if column == -1: line += "x" elif column == 1: line += "1" elif column == -3: line += "2" elif column == 0: line += " " else: line += "." print(line) def valid_pos(maze_lists, row, new_row, new_column): # Determines if coordinates are within range. if new_row < 0: return False if new_column < 0: return False if new_row >= len(maze_lists): return False if new_column >= len(maze_lists[row]): return False return True def modify_path(maze_lists): # All possible moves. moves = [[-1, 0], [0, -1], [0, 1], [1, 0]] # Loop over rows and columns. for row in range(len(maze_lists)): for column in range(len(maze_lists[row])): value = maze_lists[row][column] if value == -1: # Do nothing on wall. pass elif value == -3: # Do nothing on endpoint. pass elif value >= 1: # For a reached square, add a step number. for move in moves: new_row = row + move[0] new_column = column + move[1] # Ensure in range. if valid_pos(maze_lists, row, new_row, new_column): test_value = maze_lists[new_row][new_column] # Set move integer in new square. if test_value == 0: maze_lists[new_row][new_column] = value + 1 # A move was made. return 0 elif test_value == -3: # We are done if we can move to the endpoint. return 1 # Nothing can be done. return -1 # Initialize maze lists from string. data = get_maze_lists(maze) # Display initial map. display(data) # Walk through maze. count = 0 while True: value = input() result = modify_path(data) if result == 1: print("DONE:", count, "moves") break elif result == -1: print("FAIL:", count, "moves") break else: display(data) count += 1

xxx1 x x x2x x xxx x x x xx xxx1 x x . x2x x xxx x x x xx xxx1 x x .. x2x x xxx x x x xx xxx1 x x... x2x x xxx x x x xx xxx1 x x... x2x. x xxx x x x xx xxx1 x x... x2x..x xxx x x x xx xxx1 x x... x2x..x xxx. x x x xx xxx1 x x... x2x..x xxx.. x x x xx xxx1 x x... x2x..x xxx.. x .x x xx xxx1 x x... x2x..x xxx... x .x x xx xxx1 x x... x2x..x xxx... x .x. x xx xxx1 x x... x2x..x xxx... x ..x. x xx xxx1 x x... x2x..x xxx... x...x. x xx xxx1 x x... x2x..x xxx... x...x. .x xx xxx1 x x... x2x..x xxx... x...x. .x.xx xxx1 x x... x2x..x xxx... x...x. ..x.xx xxx1 x x... x2x..x xxx... x...x. ...x.xx xxx1 x x... x2x..x xxx... .x...x. ...x.xx xxx1 x x... x2x..x .xxx... .x...x. ...x.xx xxx1 x x... .x2x..x .xxx... .x...x. ...x.xx xxx1 .x x... .x2x..x .xxx... .x...x. ...x.xx . xxx1 .x x... .x2x..x .xxx... .x...x. ...x.xx .. xxx1 .x x... .x2x..x .xxx... .x...x. ...x.xx ...xxx1 .x x... .x2x..x .xxx... .x...x. ...x.xx ...xxx1 .x.x... .x2x..x .xxx... .x...x. ...x.xx DONE: 24 moves

Optimal example. We add recursion here to find an optimal path through any maze. The list of maze data must be copied on each recursive call—data corruption would occur otherwise.

Info Make_move() copies the maze and then plays a move. It records the lowest count of moves when the endpoint is reached.

Detail This is the optimal solution. I verified it by counting characters (more than once).

maze = """ xxx1. x x . x2x x. xxx . x x . x xx"""; def get_maze_lists(maze): lines_raw = maze.split(".") lines_stripped = list(map(lambda line: line.strip("\n"), lines_raw)) result = [] for line in lines_stripped: row = [] for char in line: if char == "x": row.append(-1) elif char == "1": row.append(1) elif char == "2": row.append(-3) else: row.append(0) result.append(row) return result def valid_pos(maze_lists, row, new_row, new_column): if new_row < 0: return False if new_column < 0: return False if new_row >= len(maze_lists): return False if new_column >= len(maze_lists[row]): return False return True def make_move(maze_lists_temp, row, column, move_count, lowest): # This method copies the lists, and uses recursion to find paths. moves = [[-1, 0], [0, -1], [0, 1], [1, 0]] # Create new list and copy each exist in grow into it. maze_lists = [] for row_temp in maze_lists_temp: maze_lists.append(row_temp[:]) value = maze_lists[row][column] if value >= 1: for move in moves: new_row = row + move[0] new_column = column + move[1] if valid_pos(maze_lists, row, new_row, new_column): test_value = maze_lists[new_row][new_column] if test_value == 0: maze_lists[new_row][new_column] = value + 1 # Make new move. make_move(maze_lists, new_row, new_column, move_count + 1, lowest) elif test_value == -3: # See if lowest move. if move_count + 1 < lowest[0]: lowest[0] = move_count + 1 return -1 # Initialize. data = get_maze_lists(maze) # Find start square. for i in range(len(data)): row = data[i] for x in range(len(row)): # See if start square. if row[x] == 1: lowest = [1000] make_move(data, i, x, 0, lowest) # Print optimal move count. print("Optimal moves:", lowest[0])

Optimal moves: 20

Notes, utility function. In artificial intelligence, a "utility function" tells us an agent's happiness. Our agent in the example has no utility function other than "endpoint reached."

And If we could figure out some way to estimate our progress, the agent could reach its goal with fewer steps.

Notes, stalemate. If nothing can be done, the maze-solving algorithm will end early. It also counts the number of evaluations needed to reach its endpoint.

A summary. In artificial intelligence great emphasis is given to pathfinding. This is complex. And if you want to study this, good for you. This maze program is simple but entertaining.