Building a maze solver
Let's use the A* algorithm to solve a maze. Consider the following figure:
Figure 12: Example of a maze problem
The # symbols indicate obstacles. The symbol o represents the starting point, and x represents the goal. The goal is to find the shortest path from the start to the end point. Let's see how to do it in Python. The following solution is a variant of the solution provided in the simpleai library. Create a new Python file and import the following packages:
import math
from simpleai.search import SearchProblem, astar
Create a class that contains the methods needed to solve the problem:
# Class containing the methods to solve the maze
class MazeSolver(SearchProblem):
Define the initializer method:
# Initialize the class
def __init__(self, board):
self.board = board
self.goal = (0, 0)
Extract the initial and final positions:
for y in range(len(self.board)):
...