a-star path finding algorithm in python

main.py
import heapq

class Node:
    def __init__(self, x, y, reachable):
        self.x = x
        self.y = y
        self.reachable = reachable
        self.parent = None
        self.cost = 0
        self.heuristic = 0
        
    def __lt__(self, other):
        return self.cost + self.heuristic < other.cost + other.heuristic

def astar(maze, start, end):
    """
    maze is a list of lists, where each element in the inner list is either 0 or 1,
    where 0 is a free cell and 1 is a blocked cell
    start is the (x, y) tuple for the starting position
    end is the (x, y) tuple for the ending position
    """
    rows, cols = len(maze), len(maze[0])
    closed = [[0] * cols for _ in range(rows)]
    start_node = Node(start[0], start[1], True)
    end_node = Node(end[0], end[1], True)
    heap = []
    heapq.heappush(heap, start_node)
    
    while heap:
        curr_node = heapq.heappop(heap)
        x, y = curr_node.x, curr_node.y
        if curr_node == end_node:
            path = []
            while curr_node.parent:
                path.append((curr_node.x, curr_node.y))
                curr_node = curr_node.parent
            return path[::-1]
        
        for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            next_x, next_y = x + dx, y + dy
            if next_x < 0 or next_x >= rows or next_y < 0 or next_y >= cols:
                continue
            if closed[next_x][next_y] or not maze[next_x][next_y]:
                continue
                
            next_node = Node(next_x, next_y, True)
            next_node.parent = curr_node
            next_node.cost = curr_node.cost + 1
            next_node.heuristic = abs(end_node.x - next_x) + abs(end_node.y - next_y)
            heapq.heappush(heap, next_node)
            closed[next_x][next_y] = 1
    
    return None
1821 chars
54 lines

main.py
maze = [[0, 1, 1, 0, 0],
        [0, 0, 0, 0, 1],
        [0, 1, 1, 1, 0],
        [0, 0, 0, 0, 0],
        [1, 1, 0, 0, 0]]

start = (0, 0)
end = (4, 4)

path = astar(maze, start, end)
print(path)  # outputs [(0, 0), (0, 1), (1, 1), (2, 1), (3, 1), (4, 1), (4, 2), (4, 3), (4, 4)]
282 chars
12 lines