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 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 do you solve A 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.

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.

What is the a * search algorithm for maze solving? ›

A* search algorithm is directed algorithm which means that it does not blindly search for a path but instead it calculates the best direction to move and then it can backtrack the path. A* will not only find a path between source and destination but it will find the shortest path quickly.

What is the A * algorithm heuristic in Python? ›

The A* algorithm is best suited for pathfinding problems in graphs and grids, where you need to find the shortest path between two points. It combines features of both uniform-cost search and pure heuristic search to efficiently compute optimal solutions. Loop until solution found: Consider current node's neighbors.

What is the A * algorithm in Python pool? ›

A* algorithm incrementally searches all the routes starting from the start node until it finds the shortest path to a goal. Starting with a given node, the algorithm expands the node with the lowest f(x) value. It maintains a set of partial solutions.

What is the trick to solving A maze? ›

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.

How does A star search work? ›

A* is an informed search algorithm, or a best-first search, meaning that it is formulated in terms of weighted graphs: starting from a specific starting node of a graph, it aims to find a path to the given goal node having the smallest cost (least distance travelled, shortest time, etc.).

What is the shortest maze solving algorithm? ›

Shortest path algorithm

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 do you represent A maze on A graph? ›

It is easy to represent the maze problem as a pathfinding problem on a graph. The graph has one node for each white cell in the maze. There is an edge between two nodes if the corresponding white cells are adjacent.

What is the A * algorithm in pathfinding? ›

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

What is the A * search algorithm for dummies? ›

A* is a best-first search algorithm that considers both the cost to reach a node from the start node (g(n)) and the heuristic estimate of the cost from that node to the goal (h(n)). The algorithm maintains two sets, the open set and the closed set, to explore the graph efficiently.

What is the A * search algorithm based on? ›

A* Search Algorithm and Its Basic Concepts

A* algorithm works based on heuristic methods, and this helps achieve optimality. A* is a different form of the best-first algorithm. Optimality empowers an algorithm to find the best possible solution to a problem.

What is the star technique in Python? ›

A star pattern in Python is a graphical representation created using the asterisk (*) symbol in various shapes like lines, triangles, squares, or diamonds. It is a popular exercise for learning and practicing nested loops and control structures in programming.

References

Top Articles
Latest Posts
Recommended Articles
Article information

Author: Kieth Sipes

Last Updated:

Views: 5359

Rating: 4.7 / 5 (67 voted)

Reviews: 82% of readers found this page helpful

Author information

Name: Kieth Sipes

Birthday: 2001-04-14

Address: Suite 492 62479 Champlin Loop, South Catrice, MS 57271

Phone: +9663362133320

Job: District Sales Analyst

Hobby: Digital arts, Dance, Ghost hunting, Worldbuilding, Kayaking, Table tennis, 3D printing

Introduction: My name is Kieth Sipes, I am a zany, rich, courageous, powerful, faithful, jolly, excited person who loves writing and wants to share my knowledge and understanding with you.