A-Star (A*) Search for Solving a Maze using Python (with visualization) (2024)

A-Star (A*)search algorithm is an intelligent algorithm to solve a graph problem. Contrary to Depth First Search (DFS) and Breadth First Search (BFS), A* is an informed search algorithm which means that it takes into account the position/location of the goal while searching for it and hence it searches quite a few nodes to reach to the goal.

We will develop the A* algorithm in Python to solve the Maze Problem. This is one sample output of the code we will develop:

We will discuss the logic of the A* search algorithm on the following maze:

The way A* works is that it assigns a cost to each of the cells of the maze and the algorithm selects the path with minimum cost. The cost of a cell (n) has two parts and is defined as:

f(n) = g(n)+h(n)

Where f(n) is the total cost to reach the cell n and g(n) and h(n) are defined as:

g(n) → It is the actual cost to reach cell n from the start cell.

h(n) → It is the heuristic cost to reach to the goal cell from cell n. It is the estimated cost to reach the goal cell from cell n.

Let’s see the following case of cell (3,3) for better understanding g(n) and h(n):

The g(n) cost for cell (3,3) is 2 because from the start cell we can reach cell (3,3) in 2 steps. Then h(n) is the estimated cost to reach the goal cell (1,1) from the cell (3,3). We do not know the cost to reach the goal cell so we will simply estimate that. There can be two functions to estimate that cost:

1- Euclidian Distance:

It will be the linear distance between a cell and the goal cell as shown here:

2- Manhattan Distance:

The second option can be the Manhattan Distance between a cell and the goal cell which is the horizontal plus vertical distance between the two cells.

Heuristic Cost is just the estimate of the cost and proper selection of Heuristic Function is one key parameter of the A* Algorithm. We will use the Manhattan Distance as the Heuristic Function.

The Manhattan Distance between cell (3,3) and goal cell is 4 and hence the total cost of the cell (3,3) is:

f(n)=g(n)+h(n)=2+4=6

It is the inclusion of Heuristic Cost in A* algorithm that makes it efficient compared to BFS or DFS because the algorithm selects the cells with minimum cost (actual cost + estimated cost) and hence it will approach towards goal quickly.

Now let's see how A* Algorithm will extend from the start cell until it reaches the goal cell.

This is the starting position of the Maze and the red square shows the current cell we are on at the moment which is the start cell.

Starting from the start cell, the g(n) of the start cell is 0 because cost to reach to start cell from the start cell is obviously zero. And h(n) of the start cell is 6 which is the Manhattan Distance between the start and the goal cell.

For other cell we don’t know the costs; both g(n) and h(n) and hence we will assume those as infinity. This is the cost value of the whole Maze where cost of each cell is shown as two values g(n)+h(n):

Now we will explore the neighbor cells of the current cell. There is just one neighbor cell (3,4) of the current cell and we will calculate the cost of this cell. g(n) of the cell (3,4) will be 1, because we need one step to reach to cell (3,4) from start cell and h(n) is 5.

We are still on the start cell. Now the A* Algorithm will select the cell with the minimum cost, for the next movement which for this case is cell (3,4) and hence it will move there.

There are 3 neighbors of the cell (3,4) and their cost will be calculated as shown here:

The new cost of cells (4,4) is 8 which is higher than the old cost of 6 and hence we will not update that.

It simply means we don’t want the movement from cell (4,4) to cell (3,4) and then from cell (3,4) back to cell (4,4). The cost of other two cells, (2,4) and (3,3) is better than infinity and hence we will update their cost and will not update the cost of cell (4,4).

We are on cell (3,4) and the next cell will be chosen as the one having the minimum cost. We will not consider cell (4,4) since it has already been visited and its cost has not updated after that. That is being indicated as a yellow color bar inside the cell.

Out of other cells the two cells, (3,3) and (2,4) have the lowest cost of 6. Now which one to select? In such scenarios, we should prefer to choose the cell having a lower Heuristic Cost since it indicates that the cell is closer to the goal cell. In the present case, both cells have the same heuristic cost of 4 and hence we can choose any of the two, and let’s say we choose cell (2,4). We will move there and this will be the updated state of the Maze.

The process of calculating the cost of the neighbor cells and then choosing the cell with minimum cost will continue until we reach the goal cell. The next steps are shown in the following figures:

Once we reach the goal cell, there is a way we can select just the highlighted path which is the shortest path from the start cell to the goal cell.

Now let’s see what can be the pseudocode of the A* Search.

Since we have to choose the cell with minimum cost, so we will use the Data Structure Priority Queue to implement A* algorithm. Unlike the Queue that works on the principle of FIFO (First In First Out), the elements in a Priority Queue are taken out on the basis of the priority. The priority can be the value of the element (highest or lowest). In Python, we have the Priority Queue available in the module Queue and the priority is the lowest value, and hence is most suitable for implementing A*.

So this is the pseudocode of A* Search:

The important point to note in above pseudocode is the way we are storing the information of the cost and the cell inside the Priority Queue. It is being stored as a Tuple (f_score(start), h(start), start). The tuples are compared on the basis of the first element inside them and if that is same, the comparison is done on the basis of next element and so on. Therefore, the first value stored is the cost of the cell and second is the Heuristic cost of the cell so that if the cost of two or more cells is same, the comparison will be done on the Heuristic Cost. The third is the value of the cell itself.

To implement this algorithm in Python we will use the pyamaze module. There is a detailed post and a video on the use of this module but you can continue without that detail.

Here the complete code is provided and then is step by step discussion on it:

To create a maze of any size, e.g., a 5x5 maze, we can use the module as shown below.

The above code will generate a random 5x5 Maze. An example shown below:

The Maze arguments you need to know are:

1- rows → m.rows will return the number of rows of the maze. It will be 5 for the above case.

2- cols → m.cols will return the number of columns of the maze. It will be 5 for the above case.

3- grid → m.grid will return a list of all cells of the maze. In the above case, it will be a list of 25 cells, from (1,1) to (5,5).

4- maze_map → m.maze_map will return the information of the opened and closed walls of the maze as a dictionary. The keys will be the cell and value will be another dictionary with the information of four walls in directions East, West, North, and South. For the above case, this will be the output:

{(1, 1): {'E': 0, 'W': 0, 'N': 0, 'S': 1}, (2, 1): {'E': 0, 'W': 0, 'N': 1, 'S': 1}, (3, 1): {'E': 1, 'W': 0, 'N': 1, 'S': 0}, (4, 1): {'E': 1, 'W': 0, 'N': 0, 'S': 1}, (5, 1): {'E': 1, 'W': 0, 'N': 1, 'S': 0}, (1, 2): {'E': 1, 'W': 0, 'N': 0, 'S': 1}, (2, 2): {'E': 1, 'W': 0, 'N': 1, 'S': 0}, (3, 2): {'E': 0, 'W': 1, 'N': 0, 'S': 1}, (4, 2): {'E': 0, 'W': 1, 'N': 1, 'S': 0}, (5, 2): {'E': 1, 'W': 1, 'N': 0, 'S': 0}, (1, 3): {'E': 1, 'W': 1, 'N': 0, 'S': 0}, (2, 3): {'E': 1, 'W': 1, 'N': 0, 'S': 1}, (3, 3): {'E': 0, 'W': 0, 'N': 1, 'S': 1}, (4, 3): {'E': 1, 'W': 0, 'N': 1, 'S': 0}, (5, 3): {'E': 1, 'W': 1, 'N': 0, 'S': 0}, (1, 4): {'E': 1, 'W': 1, 'N': 0, 'S': 0}, (2, 4): {'E': 1, 'W': 1, 'N': 0, 'S': 0}, (3, 4): {'E': 0, 'W': 0, 'N': 0, 'S': 1}, (4, 4): {'E': 0, 'W': 1, 'N': 1, 'S': 0}, (5, 4): {'E': 1, 'W': 1, 'N': 0, 'S': 0}, (1, 5): {'E': 0, 'W': 1, 'N': 0, 'S': 0}, (2, 5): {'E': 0, 'W': 1, 'N': 0, 'S': 1}, (3, 5): {'E': 0, 'W': 0, 'N': 1, 'S': 1}, (4, 5): {'E': 0, 'W': 0, 'N': 1, 'S': 1}, (5, 5): {'E': 0, 'W': 1, 'N': 1, 'S': 0}}

Using the pseudocode presented above, the algorithm can be implemented as:

In the above code, we have just printed the values of g(n) and h(n) but we need the path information from start cell to goal cell. We can store that information as a Dictionary. An obvious way can be storing the information each time a new cell is chosen. On the Maze we considered earlier, the first three key-value pairs of dictionary will be like this:

But in a Dictionary we cannot have the duplicate values against one key so in above case we cannot store the two pairs, (3,4):(2,4) and (3,4):(3,3). The solution is to save the path in reverse order because we can have duplicate values in a Dictionary. So the path will be the reverse path and later we can invert that to get the forward path.

Further, the agent class is used to create an agent and then using the tracePath method of the Maze class, the agent will trace the path calculated by the A* Algorithm.

You can watch the detailed video for further clarification. Also there is another code with a little more visualization of the algorithm in a way that the searching the different maze cells is also simulated.

The module pyamaze is created to facilitate the Maze generation with easy code and then that can be used to code any search algorithm like Breadth First Search, Depth First Search, A*, Dijkstra, or some Genetic or Reinforcement Learning search algorithm. You can watch this playlist for implementation of different search algorithms with pyamaze module.

Thanks!