Space Science Blog

Bringing You The Future Of Science and Technology

PYTHON MAZE EXPLORER


In this tutorial we will explore the world of artificial intelligence programming using the popular Python programing language and the popular A* (a star) pathfinding routine, which uses greedy searching to find the best route through the maze.

Artificial Intelligence | DIY Electronics Projects | Game Design Workshop | Gallery | Random Generators | Planetary Science | Rocket Science


Categories

Art and Web Design

Contact me for information about rates and availability.


Latest Articles

 Python Maze Explorer


Python Maze Explorer
In this tutorial we will explore the world of artificial intelligence programming using the popular Python programing language. This tutorial is based on one of the examples given in Artificial Intelligence with Python by Prateek Joshi (Prackt Publishing). In this tutorial we will learn about greedy searching, which allows the AI to make the best local choice at each stage of the problem, in order to ultimately find the global optimal solution to the problem.

This tutorial will show you how to use the popular A* (astar) pathfinding algorithm to naviate your AI through a maze. Pathfinding is one of the basic problems in game AI and autonomous vehicles. Poor pathfinding can make game character's seem brainless and artificial, and when it comes to driverless car's it can transform vehicle into a lethal weapon. A* is the most popular pathfinding algorithm in game development today.

For this tutorial, we will need to install the SimpleAI package, which we will use to solve a simple maze, which we will build ourselves. SimpleAI contains various routines (including A*) which may be useful for building optimal solutions to complex problems using heuristic seach techniques.

SimpleAI can be downloaded from https://github.com/simpleai-team/simpleai. Before we can use this library, we need to make a few changes to the source code in order for it to work in Python3. You will need to download a file from Packt Publishing called simpleai.zip and unzip the contents into the simpleai folder on your computer's hard drive. By placing the contents of this file in the same folder as your code, you will be able to run the application smoothly.

To install SimpleAI using pip (works on Windows and Linux), simply enter:

$ pip install simpleai

When constructing the maze, we will use the # symbol to indicate obstacles, which the AI must navigate around to escape the maze. We will use o to indicate the starting position and an x to indicate the end point. Our goal in this puzzle is to use Python to find the shortest path from o to x.

First, create a new Python file, name it maze_explorer.py and import the following packages:
import math
from simpleai.search import astar, SearchProblem

Create a new class, containing the following methods:
# Class containing the methods to solve the maze
class MazeSolver(SearchProblem):

Next, we will define the initializer method:

    # Initialize the class
    def __init__(self, board):
        self.board = board
        self.goal = (0, 0)

We need to extract the initial and final positions for the game AI:

        for y in range(len(self.board)):
            for x in range(len(self.board[y])):
                if self.board[y][x].lower() == "o":
                    self.initial = (x, y)
                elif self.board[y][x].lower() == "x":
                    self.goal = (x, y)

        super(MazeSolver, self).__init__(initial_state=self.initial)

For each step of the way, we must calculate the cost of moving to an adjacent cell and then append all possible movements. For this to work correctly, we will need to check to see if the neighboring cells are blocked, and if not, that cell can be considered as a step towards the final destination. Here we override the actions method.
 
    # Define the method that takes actions to arrive at the solution
    def actions(self, state):
        actions = []
        for action in COSTS.keys():
            newx, newy = self.result(state, action)
            if self.board[newy][newx] != "#":
                actions.append(action)

        return actions

Based on the current state and input action, we can now update the current location using x and y coordinates. Here we override the result method.

    # Update the state based on the action
    def result(self, state, action):
        x, y = state

        if action.count("up"):
            y -= 1
        if action.count("down"):
            y += 1
        if action.count("left"):
            x -= 1
        if action.count("right"):
            x += 1

        new_state = (x, y)

        return new_state

Have we arrived at our goal?

    # Check if we have reached the goal
    def is_goal(self, state):
        return state == self.goal

Before our AI can move from the initial to final locations we must define the cost of moving to a neighboring cell. The cost of moving to a vertical, horizontal or diagonal cell is different. This is the cost function.

    # Compute the cost of taking action
    def cost(self, state, action, state2):
        return COSTS[action]

Here we will define the heuristic to use Euclidian distance when moving:

    # Heuristic that we use to arrive at the solution
    def heuristic(self, state):
        x, y = state
        gx, gy = self.goal

        return math.sqrt((x - gx) ** 2 + (y - gy) **2)

Now we will define the main function and define the map using the # symbol, as discussed above.

if __name__=="__main__":
    # Define the map
    MAP = """
    ################################
    #    #      #     #      #     #
    # #  #  #      #      #  #  #  #
    # ####  ###############  #  #  #
    #   o#  #      #         #  #  #
    #  ###     #####  ########  #  #
    #    #  ####      #         #  #
    ###  #     ########  ########  #
    #    #  #  #     #   #   x#    #    
    #       #  # #       # ####    #
    #  ####### # #  ######      #  #
    #  #     # # #  #    ########  #
    #     #      #    #         #  #
    ################################
    """

Convert the above map into a list:

    # Convert the map to a list
    print(MAP)
    MAP = [list(x) for x in MAP.split("\n") if x]

Now for the actual cost of moving around the map. Notice that diagonal movements are more expensive than vertical or horizontal moves.

    # Define cost of moving around the map
    cost_regular = 1.0
    cost_diagonal = 1.7

We can now assign the costs to their corresponding movements to a dictionary.

    # Create the cost dictionary
    COSTS = {
        "up": cost_regular,
        "down": cost_regular,
        "left": cost_regular,
        "right": cost_regular,
        "up left": cost_diagonal,
        "up right": cost_diagonal,
        "down left": cost_diagonal,
        "down_right": cost_diagonal,
    }

Create a solver object based on the MazeSolver class created above:

    # Create maze solver object
    problem = MazeSolver(MAP)

In this step we will run the solver on the map and the extract the results:

    # Run the solver
    result = astar(problem, graph_search=True)

    # Extract the path
    path = [x[1] for x in result.path()]

Lastly, we will print the output, which includes the unsolved puzzle along with the solved version.

    # Print the result
    print()
    for y in range(len(MAP)):
        for x in range(len(MAP[y])):
            if (x, y) == problem.initial:
                print('o', end='')
            elif (x, y) == problem.goal:
                print('x', end='')
            elif (x, y) in path:
                print('ยท', end='')
            else:
                print(MAP[y][x], end='')
        print()

Johnathan Nicolosi - 20 Sep 2018