Python Maze Pathfinding Example

Parse a maze from a string and then use pathfinding to solve the maze.

Maze. Life itself is a maze. But for simple mazes, a program can be used to navigate from a start to an end point. 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.

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

Display: This method displays the maze_lists in a character format. It is used to show our agent's progress.

Valid_pos: 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.

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

Python program that navigates maze # 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 end point. 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 end point. 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 Output 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

Notes. Our program solved the maze in just 24 moves. It always tried to go right first, which did not help it in this particular maze.

Important: With this algorithm, a "dead-end" is counted as the total number of moves. So the algorithm counts its total steps.

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 "end point 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 end point.

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.

Make_move: This recursive method copies the maze and then plays a move. It records the lowest count of moves when the end point is reached.

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

Python program that finds optimal path 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]) Output Optimal moves: 20

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.

The Dev Codes

.Net

.NET Array Dictionary List String 2D Async DataTable Dates DateTime Enum File For Foreach Format IEnumerable If IndexOf Lambda LINQ Parse Path Process Property Regex Replace Sort Split Static StringBuilder Substring Switch Tuple

Java

Core Array ArrayList HashMap String 2D Cast Character Console Deque Duplicates File For Format HashSet If IndexOf Lambda Math ParseInt Process Random Regex Replace Sort Split StringBuilder Substring Switch Vector While

TheDeveloperBlog.com

Python Maze Pathfinding Example

Related Links:

.Net

Java

Related Links