Navigating a Maze with the A* Algorithm in Python

3 min readJust now

Hey there, adventurous coder! 🚀 Today, we’re going to tackle one of the most popular and powerful path finding algorithms out there: the A* (A-star) algorithm. We’ll use it to navigate through a maze, finding the shortest path from start to finish. If you’re new to pathfinding algorithms, no worries — I’ll walk you through it step-by-step, and by the end, you’ll have a solid understanding of how A* works.

What is the A* Algorithm?

The A* algorithm is a widely used pathfinding and graph traversal algorithm. It’s popular because it finds the shortest path efficiently by combining elements of both Dijkstra’s algorithm and a greedy best-first search.

Here’s how it works:

- It uses a heuristic to estimate the cost from any point to the goal.
- It keeps track of two costs:
— g(n): The exact cost from the start node to any node `n`.
— h(n): The estimated cost from node `n` to the goal.
- The total cost, f(n) = g(n) + h(n), guides the algorithm to expand the most promising path first.

Setting Up the Maze

Let’s start by creating a basic maze. We’ll represent it using a 2D grid, where `0` represents a free path and `1` represents a wall.

# Define the maze as a 2D grid (0 = open, 1 = wall)
maze = [
    [0, 1, 0, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 1, 0],
    [0, 1, 1, 1, 0],
    [0, 0, 0, 0, 0]
]

start = (0, 0)  # Starting position (row, column)
end = (4, 4)    # Goal position (row, column)

Heuristic Function

A key part of the A* algorithm is the heuristic function. We’ll use the Manhattan distance (suitable for grid-based movement) to estimate how far we are from the goal:

def heuristic(a, b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])

Implementing the A* Algorithm

Let’s implement the core A* logic! We’ll keep track of nodes to explore with a priority queue, and we’ll record where we’ve been and the costs to get there.

import heapq

def astar(maze, start, end):
    rows, cols = len(maze), len(maze[0])
    open_list = []
    heapq.heappush(open_list, (0, start))
    
    came_from = {}
    g_score = {start: 0}
    f_score = {start: heuristic(start, end)}
    
    while open_list:
        _, current = heapq.heappop(open_list)
        
        if current == end:
            # Reconstruct the path
            path = []
            while current in came_from:
                path.append(current)
                current = came_from[current]
            return path[::-1]
        
        # Explore neighbors
        neighbors = [
            (current[0] + 1, current[1]),
            (current[0] - 1, current[1]),
            (current[0], current[1] + 1),
            (current[0], current[1] - 1)
        ]
        
        for neighbor in neighbors:
            r, c = neighbor
            if 0 <= r < rows and 0 <= c < cols and maze[r][c] == 0:
                tentative_g_score = g_score[current] + 1
                
                if neighbor not in g_score or tentative_g_score < g_score[neighbor]:
                    came_from[neighbor] = current
                    g_score[neighbor] = tentative_g_score
                    f_score[neighbor] = tentative_g_score + heuristic(neighbor, end)
                    if neighbor not in [i[1] for i in open_list]:
                        heapq.heappush(open_list, (f_score[neighbor], neighbor))
    
    return None  # No path found

Running the A* Algorithm

Now let’s run the A* algorithm to find the shortest path through our maze!

path = astar(maze, start, end)

if path:
    print("Path found:", path)
    for step in path:
        maze[step[0]][step[1]] = "*"

    for row in maze:
        print(" ".join(str(cell) for cell in row))
else:
    print("No path found!")

When you run this, you should see a grid with `*` showing the path from start to finish, demonstrating the shortest route through the maze!

Understanding the Output

Here’s what our maze looks like when the path is found:

Why is A* So Awesome?

The A* algorithm is efficient because it narrows down the search area using the heuristic, which makes it much faster than blindly searching every possible path. This makes it perfect for real-world applications like game development, robotics, or GPS navigation.

Wrapping Up

And there you have it! You’ve just implemented a super cool path finding algorithm in Python. 🎉 The A* algorithm is powerful and versatile, and now you have the basics to apply it to more complex problems or even different kinds of mazes!

Feel free to play around with the maze layout, try different heuristics, or challenge yourself by adding diagonal movement!

Happy coding, and may you always find your way out of any maze! 🧩