How Do I Find Shortest Path In Maze With Bfs?

I am trying to find a way to solve a maze. My teacher said I have to use BFS as a way to learn. So I made the algorithm itself, but I don't understand how to get the shortest path

Solution 1:

Since this is a coding assignment I'll leave the code to you and simply explain the general algorithm here.

You have a n by m grid. I am assuming this is is provided to you. You can store this in a two dimensional array.

Step 1) Create a new two dimensional array the same size as the grid and populate each entry with an invalid coordinate (up to you, maybe use None or another value you can use to indicate that a path to that coordinate has not yet been discovered). I will refer to this two dimensional array as your path matrix and the maze as your grid.

Step 2) Enqueue the starting coordinate and update the path matrix at that position (for example, update matrix[1,1] if coordinate (1,1) is your starting position).

Step 3) If not at the final coordinate, dequeue an element from the queue. For each possible direction from the dequeued coordinate, check if it is valid (no walls AND the coordinate does not exist in the matrix yet), and enqueue all valid coordinates.

Step 4) Repeat Step 3.

If there is a path to your final coordinate, you will not only find it with this algorithm but it will also be a shortest path. To backtrack, check your matrix at the location of your final coordinate. This should lead you to another coordinate. Continue this process and backtrack until you arrive at the starting coordinate. If you store this list of backtracked coordinates then you will have a path in reverse.

Solution 2:

The main problem in your code is this line:

self.path.append(self.queue[0])

This will just keep adding to the path while you go in all possible directions in a BFS way. This path will end up getting all coordinates that you visit, which is not really a "path", because with BFS you continually switch to a different branch in the search, and so you end up collecting positions that are quite unrelated.

You need to build the path in a different way. A memory efficient way of doing this is to track where you come from when visiting a node. You can use the visited variable for that, but then make it a dictionary, which for each r,c pair stores the r,c pair from which the cell was visited. It is like building a linked list. From each newly visited cell you'll be able to find back where you came from, all the way back to the starting cell. So when you find the target, you can build the path from this linked list.

Some other less important problems in your code:

• You don't check whether a coordinate is valid. If the grid is bounded completely by # characters, this is not really a problem, but if you would have a gap at the border, you'd get an exception

• There is code repetition for each of the four directions. Try to avoid such repetition, and store recurrent expressions like self.current[1] - 1 in a variable, and create a loop over the four possible directions.

• The variable running makes no sense: it never becomes False. Instead make your loop condition what currently is your next if condition. As long as the queue is not empty, continue. If the queue becomes empty then that means there is no path to the target.

• You store every bit of information in self properties. You should only do that for information that is still relevant after the search. I would instead just create local variables for queue, visited, current, ...etc.

Here is how the code could look:

classMaze():
    def__init__(self, str):
        self.maze = str.splitlines()

    defget_start(self):
        row = next(i for i, line inenumerate(self.maze) if"S"in line)
        col = self.maze[row].index("S")
        return row, col

    defmain(self, r, c):
        queue = [] # use a local variable, not a member
        visited = {} # use a dict, key = coordinate-tuples, value = previous location
        visited[(r, c)] = (-1, -1)
        queue.append((r, c))
        whilelen(queue) > 0: # don't use running as variable# no need to use current; just reuse r and c:
            r, c = queue.pop(0) # you can remove immediately from queueif self.maze[r][c] == 'G':
                # build path from walking backwards through the visited information
                path = []
                while r != -1:
                    path.append((r, c))
                    r, c = visited[(r, c)]
                path.reverse()
                return path
            # avoid repetition of code: make a loopfor dx, dy in ((-1, 0), (0, -1), (1, 0), (0, 1)):
                new_r = r + dy
                new_c = c + dx
                if (0 <= new_r < len(self.maze) and0 <= new_c < len(self.maze[0]) andnot (new_r, new_c) in visited and
                        self.maze[new_r][new_c] != '#'):
                    visited[(new_r, new_c)] = (r, c)
                    queue.append((new_r, new_c))

maze = Maze("""############
# S        #
##### ######
#          #
######## ###
#          #
## ##### ###
#         G#
############""")

path = maze.main(*maze.get_start())
print(path)

See it run on repl.it