The code implements the Breadth First Search algorithm to find the shortest path between two nodes in a graph.

bfs.py

class Node:
    def __init__(self, x, y, is_wall=False):
        self.x = x
        self.y = y
        self.is_wall = is_wall
        self.visited = False
        self.parent = None  # added attribute to store the parent node


class Graph:
    def __init__(self, width, height):
        self.width = width
        self.height = height
        self.nodes = [[Node(x, y) for y in range(height)] for x in range(width)]

    def add_node(self, node, is_wall=False):
        """Add a new node to the graph at the specified coordinates"""
        self.nodes[node.x][node.y] = Node(node.x, node.y, is_wall)

    def add_wall(self, node):
        """Add a new wall node to the graph at the specified coordinates"""
        self.add_node(node, is_wall=True)

    def breadth_first_search(self, start_node, end_node):
        start_node = self.nodes[start_node.x][start_node.y]
        end_node = self.nodes[end_node.x][end_node.y]
        queue = [start_node]
        start_node.visited = True

        while queue:
            current_node = queue.pop(0)

            if current_node == end_node:
                return self.get_path(end_node)

            neighbours = self.get_neighbours(current_node)
            for neighbour in neighbours:
                if not neighbour.visited and not neighbour.is_wall:
                    neighbour.visited = True
                    neighbour.parent = current_node
                    queue.append(neighbour)
        return None

    def get_neighbours(self, node):
        neighbours = []
        if node.x > 0:
            neighbours.append(self.nodes[node.x - 1][node.y])
        if node.x < self.width - 1:
            neighbours.append(self.nodes[node.x + 1][node.y])
        if node.y > 0:
            neighbours.append(self.nodes[node.x][node.y - 1])
        if node.y < self.height - 1:
            neighbours.append(self.nodes[node.x][node.y + 1])
        return neighbours

    def get_path(self, end_node):
        path = []
        current_node = end_node
        while current_node is not None:
            path.append((current_node.x, current_node.y))
            current_node = current_node.parent
        return path[::-1]


if __name__ == "__main__":
    # example usage
    graph = Graph(5, 5)
    start_node = Node(0, 0)
    end_node = Node(4, 3)
    graph.add_wall(Node(1, 1))
    graph.add_wall(Node(2, 2))
    graph.add_wall(Node(3, 3))
    path = graph.breadth_first_search(start_node, end_node)
    print(path)  # [(0, 0), (1, 0), (2, 0), (3, 0), (4, 0), (4, 1), (4, 2), (4, 3)]