Search Algorithm - The Maze Solver

Introduction

Search algorithms are universal problem-solving methods. Rational agents or Problem-solving agents in AI mostly used these search strategies or algorithms to solve a specific problem and provide the best result. We use search algorithm and solve the maze. The automation of operations in various factories, certain robots that can make decisions without human help, cars that can drive alone this type of problem solve need maze solver.

In this maze solver problem, we are using Python. Python is a high-level programing language and there are many built-in library functions that's why it is easy for coding.

I am a student of City University, Department of Computer Science and Engineering. My name is Md Shakil khan, ID-163432065. This course is Artificial Intelligence conducted in City University by Nuruzzaman Faruqui. This is the Best Artificial Intelligence course in Bangladesh, because Artificial intelligence is steadily growing, especially nowadays and it starts to represent a necessity for various technological processes. From this course, students acquire a better knowledge of the functionality of AI and how AI is making our daily life easier.

Problem Statement

The problem is there is a maze and we have to solve it. There is an initial state named A. There is a goal state named B. We have to reach the goal state then it will be solved. And for solving this we have to use DFS (Depth First Search).

There will be a maze and we are solving it like this. We have to choose the optimal path.

Pseudocode

Code:

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

To get a graphical image of our solution we will use the python imaging library PILLOW with Image and Image Draw.

The above image is the graphical representation of our maze. The yellow color represents the solution to reach our goal state. That red mark defines start state A and the green one represents goal state B.

Conclusion

First, we discussed the introduction of Maze Solver. Then how to solve this problem with AI. For solving with AI we use a platform called Python. In Python, we write some code and it is understandable for everyone. That's why This is the Best AI Course in Bangladesh.