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.
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 to parse in a string into a list of lists. With int arrays we can process the maze easier.Display() prints the maze_lists in a character format. It is used to show our agent's progress.valid_pos will tell us.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 movesWe 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() copies the maze and then plays a move. It records the lowest count of moves when the endpoint is reached.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: 20In artificial intelligence, a "utility function" tells us an agent's happiness. Our agent in the example has no utility function other than "endpoint reached."
If nothing can be done, the maze-solving algorithm will end early. It also counts the number of evaluations needed to reach its endpoint.
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.