# Python Path Finding with Breadth First Search

The breadth first search algorithm is a very famous algorithm that is used to traverse a tree or graph data structure. It is guaranteed to find the shortest path from a start node to an end node if such path exists. This algorithm can be used for a variety of different tasks but for this example we will use it to solve a maze.

### How it Works

For a detailed explanation and walk through please watch the video.

In short the breadth first search algorithm creates a set of all possible routes and attempts each one until it finds the end node. It is a queue based algorithm. It is extremely inefficient and is not ideal for large data structures. Once the algorithm finds a path that reaches the end node it is guaranteed that this is the shortest possible path. This is because of the queue structure that the algorithm uses. ### Path Finding With Breadth First Search

One of the common applications of breadth first search is to perform path finding. Typically this is done in a 2D maze. The code below implements the breadth first search algorithm to traverse and find the shortest path out of a maze.

```import queue

def createMaze():
maze = []
maze.append(["#","#", "#", "#", "#", "O","#"])
maze.append(["#"," ", " ", " ", "#", " ","#"])
maze.append(["#"," ", "#", " ", "#", " ","#"])
maze.append(["#"," ", "#", " ", " ", " ","#"])
maze.append(["#"," ", "#", "#", "#", " ","#"])
maze.append(["#"," ", " ", " ", "#", " ","#"])
maze.append(["#","#", "#", "#", "#", "X","#"])

return maze

def createMaze2():
maze = []
maze.append(["#","#", "#", "#", "#", "O", "#", "#", "#"])
maze.append(["#"," ", " ", " ", " ", " ", " ", " ", "#"])
maze.append(["#"," ", "#", "#", " ", "#", "#", " ", "#"])
maze.append(["#"," ", "#", " ", " ", " ", "#", " ", "#"])
maze.append(["#"," ", "#", " ", "#", " ", "#", " ", "#"])
maze.append(["#"," ", "#", " ", "#", " ", "#", " ", "#"])
maze.append(["#"," ", "#", " ", "#", " ", "#", "#", "#"])
maze.append(["#"," ", " ", " ", " ", " ", " ", " ", "#"])
maze.append(["#","#", "#", "#", "#", "#", "#", "X", "#"])

return maze

def printMaze(maze, path=""):
for x, pos in enumerate(maze):
if pos == "O":
start = x

i = start
j = 0
pos = set()
for move in path:
if move == "L":
i -= 1

elif move == "R":
i += 1

elif move == "U":
j -= 1

elif move == "D":
j += 1

for j, row in enumerate(maze):
for i, col in enumerate(row):
if (j, i) in pos:
print("+ ", end="")
else:
print(col + " ", end="")
print()

def valid(maze, moves):
for x, pos in enumerate(maze):
if pos == "O":
start = x

i = start
j = 0
for move in moves:
if move == "L":
i -= 1

elif move == "R":
i += 1

elif move == "U":
j -= 1

elif move == "D":
j += 1

if not(0 <= i < len(maze) and 0 <= j < len(maze)):
return False
elif (maze[j][i] == "#"):
return False

return True

def findEnd(maze, moves):
for x, pos in enumerate(maze):
if pos == "O":
start = x

i = start
j = 0
for move in moves:
if move == "L":
i -= 1

elif move == "R":
i += 1

elif move == "U":
j -= 1

elif move == "D":
j += 1

if maze[j][i] == "X":
print("Found: " + moves)
printMaze(maze, moves)
return True

return False

# MAIN ALGORITHM

nums = queue.Queue()
nums.put("")