Maze solving with DFS Algorithm in Python
Introduction
In this report, we will look at a problem that has relevance to the expanding world of robotics. How do you find your way out of a maze? If you have a robotic vacuum cleaner for your room, you will wish that you could reprogram it using what you have learned in this report.
The problem we want to solve is to help our AI agent or you can say a robot to find its way out of a virtual maze.
We will implement the Depth First Search algorithm in python to solve this problem.
Background/ Interest
This report is a part of the “ CSE 418: Artificial Intelligence Lab” course at City University, Dhaka, Bangladesh conducted by Nuruzzaman Faruqui (Lecturer, Department of Computer Science & Engineering). This is the best AI course in Bangladesh.
In this course, we learned AI from scratch. We started from Basic python and ended in Natural language processing. We learned theoretical concepts properly and then implemented our knowledge in the Lab. We have done a lot of lab sessions to master the course.
Problem Statement
We have a virtual maze. A is the initial state or starting state. We should help our AI agent to reach destination state or goal state B. The gray boxes are obstacles or walls. The AI agent should go from Initial state A to Goal state B through the black shaded way.
Depth-First Search Algorithm
In our out how to traverse a maze through code, we first need to understand what depth-first search is. Depth-first search is a graph/tree traversal algorithm that follows a path as far as it can until it either reaches the goal or has nowhere else to go. It’s almost like running as far as you can in one direction until you hit a wall.
An example from my course instructor: Take a situation where you are looking for your keys. In a depth-first search approach, if you choose to start with searching in your pants, you’d first go through every single pocket, emptying each pocket and going through the contents carefully. You will stop searching in your pants and start searching elsewhere only once you will have completely exhausted the search in every single pocket of your pants.
Algorithm:
Hopefully, that analogy helps clear up any lingering confusion. You might even be starting to see how we can use Depth-First Search to solve a maze
Create a Maze
Creating a text file as a maze. You can also use your own created file too.
Filename: mze.txt
### #########
# ################### # #
# #### # # # #
# ################### # # # #
# # # # #
##################### # # # #
# ## # # # #
# # ## ### ## ######### # # #
# # # ##B# # # #
# # ## ################ # # #
### ## #### # # #
### ############## ## # # # #
### ## # # # #
###### ######## ####### # # #
###### #### # #
A ######################
The Python Code to Solve Maze Problem using DFS
import sys
class Node():
def __init__(self, state, parent, action):
self.state = state
self.parent = parent
self.action = action
class StackFrontier():
def __init__(self):
self.frontier = []
def add(self, node):
self.frontier.append(node)
def empty(self):
return len(self.frontier) == 0
def remove(self):
if self.empty():
raise Exception("The frontier is empty")
else:
node = self.frontier[-1]
self.frontier = self.frontier[:-1]
return node
def contains_state(self, state):
return any(node.state == state for node in self.frontier)
# Instead of Stack we have to use Queue
class Maze():
def __init__(self, filename):
with open(filename) as f:
contents = f.read()
if contents.count("A") != 1:
raise Exception("The maze doesn't have a starting point")
if contents.count("B") != 1:
raise Exception("The maze doesn't have a exit (exit means goal)")
# Study the structure of the maze (We will start from here)
contents = contents.splitlines()
self.height = len(contents)
self.width = max(len(line) for line in contents)
# We want to track the walls here
self.walls = []
for i in range(self.height):
row = []
for j in range(self.width):
try:
if contents[i][j] == "A":
self.start = (i, j)
row.append(False)
elif contents[i][j] == "B":
self.goal = (i, j)
row.append(False)
elif contents[i][j] == " ":
row.append(False)
else:
row.append(True)
except IndexError:
row.append(False)
self.walls.append(row)
self.solution = None
def print(self):
solution = self.solution[1] if self.solution is not None else None
print()
for i, row in enumerate(self.walls):
for j, col in enumerate(row):
if col:
print("█", end="")
elif (i, j) == self.start:
print("A", end="")
elif (i, j) == self.goal:
print("B", end="")
elif solution is not None and (i, j) in solution:
print("*", end="")
else:
print(" ", end="")
print()
print()
def neighbors(self, state):
row, col = state
candidates = [
("up", (row - 1, col)),
("down", (row + 1, col)),
("left", (row, col-1)),
("right", (row, col+1))
]
result = []
for action, (r, c) in candidates:
if 0 <= r < self.height and 0 <= c < self.width and not self.walls[r][c]:
result.append((action, (r, c)))
return result
def solve(self):
self.num_explored = 0
start = Node(state=self.start, parent=None, action=None)
frontier = StackFrontier()
frontier.add(start)
self.explored = set()
while True:
if frontier.empty():
raise Exception("There is no solution")
node = frontier.remove()
self.num_explored += 1
if node.state == self.goal:
actions = []
cells = []
while node.parent is not None:
actions.append(node.action)
cells.append(node.state)
node = node.parent
actions.reverse()
cells.reverse()
self.solution = (actions, cells)
return
self.explored.add(node.state)
for action, state in self.neighbors(node.state):
if not frontier.contains_state(state) and state not in self.explored:
child = Node(state=state, parent=node, action=action)
frontier.add(child)
def output_image(self, filename, show_solution=True, show_explored=True):
from PIL import Image, ImageDraw
cell_size = 50
cell_border = 2
img = Image.new(
"RGBA",
(self.width * cell_size, self.height * cell_size),
"black"
)
draw = ImageDraw.Draw(img)
solution = self.solution[1] if self.solution is not None else None
for i, row in enumerate(self.walls):
for j, col in enumerate(row):
if col:
fill = (40, 40, 40)
elif(i, j) == self.start:
fill = (255, 0, 0)
elif (i, j) == self.goal:
fill = (0, 171, 28)
elif solution is not None and show_solution and (i, j) in solution:
fill = (220, 235, 113)
elif solution is not None and show_explored and (i, j) in self.explored:
fill = (212, 97, 85)
else:
fill = (237, 240, 252)
draw.rectangle(
([(j * cell_size + cell_border, i * cell_size + cell_border),
((j + 1) * cell_size - cell_border, (i + 1) * cell_size - cell_border)]),
fill = fill
)
img.save(filename)
if len(sys.argv) != 2:
sys.exit("use this command: python maze.py maze1.txt")
m = Maze(sys.argv[1])
print("This is our Maze:")
m.print()
print("Solving the maze ...")
m.solve()
print("Number of explored states: ", m.num_explored)
print("This is the Solution: ")
m.print()
m.output_image("The_Maze.png", show_explored=True)
Result
Before running the code make sure your files are saved in the same directory.
Run “python3 maze.py maze.txt” in the terminal.
You will get the result as below in your terminal.
You will have a Graphical result in your directory too.
Conclusion
By now I’m sure you understand exactly how our search algorithm could generate the path shown in the result section. We learned about some graph theory, depth-first search, the call stack and, how all of it applies to finding a path through a maze. I hope y’all enjoyed reading this report as much as I enjoyed writing it!
You are free to copy the code from here or some other concluding remarks.