ai.py

import sys


class Node():  # Defines a node, that holds a state value, a parent and the action taken to get there.
    def __init__(self, state, parent, action):
        self.state = state
        self.parent = parent
        self.action = action


class StackFrontier():  # The structure used to store nodes and visit them. Uses stack, which means that the last node added is the first one to be removed.
    def __init__(self):
        self.frontier = []  # Initialize the frontier as an empty list.

    def add(self, node):  # Add a node to the frontier.
        self.frontier.append(node)  # Append the node at the end of the list

    def contains_state(self, state):
        return any(node.state == state for node in self.frontier)

    def empty(self):  # Check if the frontier is empty.
        # Return true if len is 0, else return false
        return len(self.frontier) == 0

    def remove(self):  # Remove node
        if self.empty():  # If the frontier is empty
            raise Exception("empty frontier")  # Raise an exception
        else:
            node = self.frontier[-1]  # Take the last node in the list
            # Remove the last node from the list
            self.frontier = self.frontier[:-1]
            return node  # Return the node

class Maze():

    def __init__(self, filename):  # Configuring the maze

        # Read file and set height and width of maze
        with open(filename) as f:
            contents = f.read()

        # Validate start and goal
        if contents.count("A") != 1:  # Checks if maze have only one start
            raise Exception("maze must have exactly one start point")
        if contents.count("B") != 1:  # Checks if maze have only one goal
            raise Exception("maze must have exactly one goal")

        # Determine height and width of maze
        # Python splitlines() method splits the string based on the lines. It breaks the string at line boundaries and returns a list of splitted strings.
        contents = contents.splitlines()
        self.height = len(contents)
        # Returns the length of the longest line in the list of strings.
        self.width = max(len(line) for line in contents)

        # Keep track of walls
        # List of lists, where each inner list is a row in the maze.
        self.walls = []
        for i in range(self.height):  # Loop through the height (rows)
            row = []
            for j in range(self.width):
                try:
                    if contents[i][j] == "A":  # If the char is A, it is the start
                        self.start = (i, j)
                        # False means that the cell is not a wall
                        row.append(False)
                    elif contents[i][j] == "B":  # If the char is B, it is the goal
                        self.goal = (i, j)
                        row.append(False)
                    # If the char is a space, it is a possible path
                    elif contents[i][j] == " ":
                        row.append(False)
                    else:  # Else, it is a wall
                        row.append(True)
                except IndexError:
                    row.append(False)
            self.walls.append(row)  # Append the row to the walls list

        self.solution = None

    def print(self):
        # Sets solution to solution[1] if it is not None, else sets it to None
        solution = self.solution[1] if self.solution is not None else None
        print()  # Prints a new line
        # index i is the row number, row is the row, enumerate is a built-in function that returns a tuple of (index, value)
        for i, row in enumerate(self.walls):
            # index j is the column number, col is the column
            for j, col in enumerate(row):
                if col:  # If the cell is a wall (col == True)
                    print("█", end="")  # Print a wall
                elif (i, j) == self.start:  # If the cell is the start
                    print("A", end="")  # Print a start
                elif (i, j) == self.goal:  # If the cell is the goal
                    print("B", end="")  # Print a goal
                # If solution isnt None and cell is in solution
                elif solution is not None and (i, j) in solution:
                    print("*", end="")  # Print a solution point
                else:
                    # Print a normal space (path possibility)
                    print(" ", end="")
            print()  # in the end of a row, print a new line
        print()

    def neighbors(self, state):  # Returns the neighbors of the state
        row, col = state  # Set row and col to state
        candidates = [  # Set candidates to a list of possible neighbors
            ("up", (row - 1, col)),  # Cell above
            ("down", (row + 1, col)),  # Cell below
            ("left", (row, col - 1)),  # Cell to the left
            ("right", (row, col + 1))  # Cell to the right
        ]

        result = []
        # Loop through the candidates values, action being ('up', 'down' etc) and (r, c) being the coordinates of the cell
        for action, (r, c) in candidates:
            # if r and c are in the maze and not a wall
            if 0 <= r < self.height and 0 <= c < self.width and not self.walls[r][c]:
                # Append the action and coordinates to the result list, which means it is a neighbor
                result.append((action, (r, c)))
        return result

    def solve(self):
        """Finds a solution to maze, if one exists."""

        # Keep track of number of states explored
        self.num_explored = 0

        # Initialize frontier to just the starting position
        start = Node(state=self.start, parent=None, action=None)
        frontier = StackFrontier()
        frontier.add(start)

        # Initialize an empty explored set
        self.explored = set()

        # Keep looping until solution found
        while True:

            # If nothing left in frontier, then no path
            if frontier.empty():
                raise Exception("no solution")

            # Choose a node from the frontier
            node = frontier.remove()  # remove returns a node
            self.num_explored += 1  # node was explored, so keep track of it

            # If node is the goal, then we have a solution
            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()  # reverse the actions list, to get the right order
                cells.reverse()
                # Set the solution to the actions and cells
                self.solution = (actions, cells)
                return

            # Mark node as explored since its not the goal
            self.explored.add(node.state)

            # Add neighbors to frontier
            for action, state in self.neighbors(node.state):
                # if state is not in the frontier and not explored
                if not frontier.contains_state(state) and state not in self.explored:
                    # Create a child node
                    child = Node(state=state, parent=node, action=action)
                    frontier.add(child)  # Add the child to the frontier

    def output_image(self, filename, show_solution=True, show_explored=False):
        from PIL import Image, ImageDraw
        cell_size = 50
        cell_border = 2

        # Create a blank canvas
        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):

                # Walls
                if col:
                    fill = (40, 40, 40)

                # Start
                elif (i, j) == self.start:
                    fill = (255, 0, 0)

                # Goal
                elif (i, j) == self.goal:
                    fill = (0, 171, 28)

                # Solution
                elif solution is not None and show_solution and (i, j) in solution:
                    fill = (220, 235, 113)

                # Explored
                elif solution is not None and show_explored and (i, j) in self.explored:
                    fill = (212, 97, 85)

                # Empty cell
                else:
                    fill = (237, 240, 252)

                # Draw cell
                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("Usage: python maze.py maze.txt")

m = Maze(sys.argv[1])
print("Maze:")
m.print()
print("Solving...")
m.solve()
print("States Explored:", m.num_explored)
print("Solution:")
m.print()
m.output_image("maze.png", show_explored=True)