Maze solver
The maze-routing algorithm is a low overhead method to find the way between any two locations of the maze. The algorithm is initially proposed for chip multiprocessor (CMPs) domain and guarantees to work for any grid-based maze. In addition to finding paths between two location of the grid (maze), the algorithm can detect when there is no path between the source and destination. Also, the algorithm is to be used by an inside traveler with no prior knowledge of the maze with fixed memory complexity regardless of the maze size; requiring 4 variables in total for finding the path and detecting the unreachable locations. Nevertheless, the algorithm is not to find the shortest path.
My name's Happy khatun. I am a student of city university. This blog is the easiest way to learn python programming in Bangladesh. This course is conducted in City University by our most honorable teacher Nuruzzaman Faruqui.
In here we will explain a problem with maze solver. Here is a maze given below:
Here is an initial state named A and a goal state named B. We have to reach the goal state in order to solving this problem.
we will solve this problem by sing DFS (Depth First Search). The code and explanation regarding to solve this problem is given below:
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)
To get a graphical image of our solution we will use the python imaging library PILLOW with Image
This image is the graphical representation of our maze. The yellow color represents the directory to reach our goal state. That red mark defines start state A and the green one represents goal state B.
In this blog we discuss every single line for your better understanding. For its explanation simplicity it becomes the easiest way to learn python programming in Bangladesh.
No comments:
Post a Comment