Optimized Maze Solver using A*

By: fyvo August 2, 2025 Algorithms

Description

This algorithm uses the A* search algorithm to find the shortest path through a maze represented as a 2D array. It prioritizes cells closer to the target using a heuristic function.

Code Snippet

import heapq

def a_star(maze, start, end):
    queue = [(0, start)]
    came_from = {}
    cost_so_far = {start: 0}

    while queue:
        _, current = heapq.heappop(queue)

        if current == end:
            break

        for next_node in get_neighbors(maze, current):
            new_cost = cost_so_far[current] + 1
            if next_node not in cost_so_far or new_cost < cost_so_far[next_node]:
                cost_so_far[next_node] = new_cost
                priority = new_cost + heuristic(next_node, end)
                heapq.heappush(queue, (priority, next_node))
                came_from[next_node] = current

    path = reconstruct_path(came_from, current)
    return path

def get_neighbors(maze, node):
    row, col = node
    neighbors = []
    for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        new_row, new_col = row + dr, col + dc
        if 0 <= new_row < len(maze) and 0 <= new_col < len(maze[0]) and maze[new_row][new_col] == 0:
            neighbors.append((new_row, new_col))
    return neighbors

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

def reconstruct_path(came_from, current):
    path = [current]
    while current in came_from:
        current = came_from[current]
        path.append(current)
    return path[::-1]

# Example usage:
maze = [
    [0, 0, 0, 0],
    [1, 1, 0, 1],
    [0, 0, 0, 0],
    [1, 1, 1, 0]
]
start = (0, 0)
end = (3, 3)
path = a_star(maze, start, end)
print(path)

Discussion (0)