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

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

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:

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

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):

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

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:

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

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.

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

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.

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

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):

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

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.

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

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.

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

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

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

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).

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

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.

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

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:

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

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.

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

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:

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

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:

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

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:

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

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:

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

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!

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

FAQs

How to solve maze puzzle in Python? ›

To solve the maze, we use the breadth-first search (BFS) algorithm. Unlike DFS, which goes as deep as possible into the maze before backtracking, BFS explores all neighbors of the current cell before moving on. This guarantees that it will find the shortest path from the starting point to the target.

What is the a * search algorithm for maze? ›

A* search algorithm will find the path between source and destination. Source and destination location must be selected. Then select one of the three elements that can move on the map (amphibious, ground, or water). Maze solving is considering the image as black and white image.

How to do a star algorithm in Python? ›

How A* Search Algo works?
  1. Select the node with the lowest f value from the open list. This node is the current node.
  2. If the current node is the goal node, the path has been found; reconstruct the path and return it.
  3. Move the current node to the closed list.
  4. For each neighbor of the current node:
Apr 17, 2024

How to solve a maze using BFS in Python? ›

Here's how you can implement BFS in Python to solve a maze: from collections import deque def bfs(maze, start, end): # Directions: up, right, down, left directions = [(-1, 0), (0, 1), (1, 0), (0, -1)] queue = deque([start]) # Queue for BFS visited = set(start) # Keep track of visited cells while queue: current = queue.

How do you solve a maze easily? ›

It's possible to escape many mazes by walking round them keeping one hand in constant contact with the wall. But some mazes are designed to defeat this technique, and need Tremaux's Rule: at each junction, choose any route, back-tracking only if it leads to a dead end or a junction you've already visited.

What is the easiest maze algorithm? ›

Fractal Tessellation algorithm

This is a simple and fast way to generate a maze. On each iteration, this algorithm creates a maze twice the size by copying itself 3 times. At the end of each iteration, 3 paths are opened between the 4 smaller mazes.

What is a * search in AI? ›

A* Search Algorithm is a simple and efficient search algorithm that can be used to find the optimal path between two nodes in a graph. It will be used for the shortest path finding. It is an extension of Dijkstra's shortest path algorithm (Dijkstra's Algorithm).

How does the A * algorithm work? ›

The A* algorithm ensures that the path found is the shortest by combining the actual distance from the start node with the estimated distance to the goal node, guiding the search towards the goal efficiently.

What is the algorithm for maze puzzles? ›

One such algorithm finds the shortest path by implementing a breadth-first search, while another, the A* algorithm, uses a heuristic technique. The breadth-first search algorithm uses a queue to visit cells in increasing distance order from the start until the finish is reached.

How does maze solver work? ›

This robot is equipped with three ultrasonic sensors to check the path for right, left, and straight direction. The robot is able to move automatically in many mazes, find the shortest path between two points, calculate the traveled distance, and be able to solve the same maze in the second round in a shorter time.

What is the algorithm for traversing a maze? ›

Algorithm for traversing a maze
  • Start.
  • If only one path (Left or Right or Straight) is found, follow the path.
  • Else If Multiple path is found: If left path is found, take a left turn. Else if straight path is found, follow straight path. ...
  • Else If Dead End is found, take a 'U' turn. Go To step 2.
  • End.
May 16, 2013

How do you solve a maze puzzle? ›

The technique is simple: when you enter the maze, place your right hand on the wall to your right (or left hand on the wall to the left), and keep it there as you move through the maze. Eventually you should come to the exit. We say should because this theory, while sound, does not work in all mazes.

How to generate a random maze in Python? ›

Build a Maze Solver in Python Using Graphs
  1. Identify the Building Blocks of the Maze.
  2. Assign Roles to Squares.
  3. Create Border Patterns.
  4. Model the Square.
  5. Build the Maze.

What is the algorithm to escape a maze? ›

One well-known maze algorithm is called "Follow the left wall." The idea is to keep your left hand touching a wall. If suddenly your left hand isn't touching a wall, there's a corridor to the left, and in order to keep your hand on the left wall, you turn left and go down the corridor.

Top Articles
Latest Posts
Recommended Articles
Article information

Author: Foster Heidenreich CPA

Last Updated:

Views: 5257

Rating: 4.6 / 5 (56 voted)

Reviews: 95% of readers found this page helpful

Author information

Name: Foster Heidenreich CPA

Birthday: 1995-01-14

Address: 55021 Usha Garden, North Larisa, DE 19209

Phone: +6812240846623

Job: Corporate Healthcare Strategist

Hobby: Singing, Listening to music, Rafting, LARPing, Gardening, Quilting, Rappelling

Introduction: My name is Foster Heidenreich CPA, I am a delightful, quaint, glorious, quaint, faithful, enchanting, fine person who loves writing and wants to share my knowledge and understanding with you.