Search Algorithm - The Maze Solver
Introduction:
Everybody knows what is a maze. In the maze, there are an initial state and a Final state also. We have to reach the final state from the initial state. When we are solving the maze on paper this is normal, but we are going to solve the maze by using Artificial Intelligent. We give a maze problem to our computer and it will give us a solution. we know that how we solve this and how its works.
To solve this problem we are using the Search Algorithm in Python. We can solve the Search Algorithm by using DFS(Depth-First-Search) and BFS(Breath-First-Search). But today we are using Depth-First-Search.
This is an Artificial Intelligence course conducted in City Universit by Nuruzzaman Faruqui. This is the best course in Bangladesh. Because Sir explained all the necessary things to us well. The problem we are dealing with in lab first, sir gives us a very good idea of the problem by using many examples. After that sir explains about the solutions like how we can solve the problem, how they work. For that, we understand everything very easily.
Problem :
First, we have to know about the problem. The problem is :
· We
have a maze
· We
have an initial state name A
· We
have to reach a goal or the final state name B
· In
this problem we are using Depth-First Search (DFS)
Like,
In this picture, we can see that there an initial state which is A, and a final or goal state name B. We have to reach the goal state.
In this picture, we can see the solution. In the first picture, there was just the problem and the second picture represents how we can reach the goal.
The python code to solve maze problem using DFS.
To solve this problem, we start with a frontier that
contains the initial state and an empty set of explored items. Now we have to know what
is “Frontier”.
Frontier: Frontier is a data structure where we are
going to store all of the data.
For Depth-first search(DFS) we use stack frontier Which is the “Last in
first out ” data type. In order to solve the maze problem, First, we need to
understand what is depth-first search.
Depth-first search (DFS): Depth-first search is a one
kind of search algorithm that always expands the deepest node in the frontier. It 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.
We start with a frontier and repeats the following
actions until we reach the Solution.
We have to repeat,
Repeat:
- If the frontier is empty,
Stop.
There is no solution to the problem.
- Remove a node from the frontier.
This is the node that will be considered.
- If the node contains the goal
state,
Return
the solution. Stop.
- Else,
- Expand
the node (find all the new nodes that could be reached from this node),
and add resulting nodes to the frontier.
- Add
the current node to the explored set.
class Node():
def __init__(self, state, parent, action):
self.state = state
self.parent = parent
self.action = action
# In this class we are creating stack frontier
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) #we read the maze
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)")
# From there are are study the sturcture of maze and find the height, width and the walls
contents = contents.splitlines()
self.height = len(contents)
self.width = max(len(line) for line in contents)
# We are finding 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 #here we are doing one thing which is we are finding the walls and replace it with full blocks
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) # this part is for save the solution in png format .
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 :
After doing this code, If every we find any errors the first need to solve the errors. After fixing the error hopefully, we can run the code and we will gate our expected solution.
To run this code we need to write in the terminal that is " python maze.py maze1.txt".
This is the Problem,
This is the solution,
No comments