Introduce
In a previous article, I wrote about solutions and algorithms for the mission "Open Labyrinth" on the CheckiO blog. Since then, I've received many requests to learn a little more about schemas and for a more interactive explanation. So, I've put together this more in-depth article with some visual labyrinth algorithm explanations. You can see how BFS, DFS or A* queue or stack and how they find a path for different labyrinths.
All of the examples here are based on the original "Open Labyrinth" mission. In this mission, you are given the map of a maze and your task is to find a path from one corner to another. The maze can be represented as a graph where empty cells are nodes and adjacent cells are connected. Because we don't need to find the shortest path, we can use a variety of graph-traversal algorithms.
Maze to Graph
First I would like to change the representation of the maze. This part is not necessary and we can detect "neighbors" while we search for a path. But for newbies, it will be simpler to decompose the problem and first convert a maze into a 2D array and into a graph as a dictionary.
Our graph will be represented as a dictionary, where keys are node coordinates, values are neighbor node coordinates and directions are how to get to it. Node coordinates are represented as a tuple with two numbers. This way each cell has a unique name. Directions will be useful to write the route when we search for a path inside the maze.
First we collect all of the empty cells and write them as a keys. Then gather information about the neighbours. We could do this in one iteration through a matrix with defaultdict, but I want to try a simpler method better suited for Python newbies. For each cell we only look at the "south" and "east" neighbours and add them as "connections". And with these directions we add the reverse "N" and "W" connection for neighbouring cells. This way we skip duplicate operations. Don't forget to check for edge cases. Below you can see the simple code for it.
def maze2graph(maze):
height = len(maze)
width = len(maze[0]) if height else 0
graph = {(i, j): [] for j in range(width) for i in range(height) if not maze[i][j]}
for row, col in graph.keys():
if row < height - 1 and not maze[row + 1][col]:
graph[(row, col)].append(("S", (row + 1, col)))
graph[(row + 1, col)].append(("N", (row, col)))
if col < width - 1 and not maze[row][col + 1]:
graph[(row, col)].append(("E", (row, col + 1)))
graph[(row, col + 1)].append(("W", (row, col)))
return graph
In these animations, you can see how the recent function checks the neighbors. But it's little difficult in a Python realization because py dictionaries are unordered. This animation should show you how the maze changes to a "skeleton" form.
Breadth First Search
Breadth-first searching (BFS) is an algorithm for traversing or searching a path in a graph. It starts at some arbitrary node of the graph and explores the neighboring nodes first, before moving to the next level neighbors. For BFS we are using a queue to store the nodes which will be exploring. This way we check the closest nodes first. It should look like we go level by level and before we move on to look at the next level, we should check all nodes in the current level. For a graph search, it's very important to write all of the visited nodes, or we can get ourselves into a loop.
BFS is optimal and is guaranteed to find the best solution that exists. Time complexity for BFS (worst case) is O(|V|+|E|), where |V| is a number of nodes and |E| is a number of edges in the graph.
In Python, we can use "deque" as a queue, or even a simple list (but it's slower). We put the initial node into the queue. Then repeat this procedure until visiting the goal node or visit all available nodes: take the first from the queue, check if it was visited or not, check if it's the goal, put all neighbors at the end of the queue, repeat. For each step, we track not only the nodes but directions and the path for the current node too.
from collections import deque
def find_path_bfs(maze):
start, goal = (1, 1), (len(maze) - 2, len(maze[0]) - 2)
queue = deque([("", start)])
visited = set()
graph = maze2graph(maze)
while queue:
path, current = queue.popleft()
if current == goal:
return path
if current in visited:
continue
visited.add(current)
for direction, neighbour in graph[current]:
queue.append((path + direction, neighbour))
return "NO WAY!"
In the next animation, you can see how BFS traverse through a maze. Numbered cells are nodes in the queue (we take with the lowest number). Grey cells are visited. Orange cells show the resulting route.
Depth First Search
Depth-first search (DFS) is an algorithm similar to BFS. It starts at some arbitrary node of the graph like BFS, but explores as far as possible along each branch. For a DFS non-recursive implementation, we are using a stack instead of a queue to store nodes which will be exploring. This way we check the nodes first which were last added to the stack.
DFS is not optimal and it is not guaranteed to find the best solution. This means DFS is not good choice to find a path in a maze, but it has other applications in finding connected components or maze generation.
The Python code for DFS has only a couple differences from BFS. We've renamed "queue" to "stack" for readability and "popleft()" to "pop()".
from collections import deque
def find_path_dfs(maze):
start, goal = (1, 1), (len(maze) - 2, len(maze[0]) - 2)
stack = deque([("", start)])
visited = set()
graph = maze2graph(maze)
while stack:
path, current = stack.pop()
if current == goal:
return path
if current in visited:
continue
visited.add(current)
for direction, neighbour in graph[current]:
stack.append((path + direction, neighbour))
return "NO WAY!"
In the next animation, you can see how DFS traverse through a maze. As we can see for the empty cell DFS works well, but not for "Snake and Short". Numbered cells are nodes in the queue (we take with the highest number). Grey cells are visited. Orange cells show the resulting route.
A* Search
A* is a widely used pathfinding algorithm and an extension of Edsger Dijkstra's 1959 algorithm. A* uses a greedy search and finds a least-cost path from the given initial node to one goal node out of one or more possibilities. As A* traverses the graph, it follows a path of the lowest expected total cost or distance, keeping a sorted priority queue of alternate path segments along the way. It uses a heuristic cost function of node to determine the order in which the search visits nodes in the graph. For A* we take the first node which has the lowest sum path cost and expected remaining cost. But heuristics must be admissible, that is, it must not overestimate the distance to the goal. The time complexity of A* depends on the heuristic.
For Python, we can use "heapq" module for priority queuing and add the cost part of each element. For a maze, one of the most simple heuristics can be "Manhattan distance".
from heapq import heappop, heappush
def heuristic(cell, goal):
return abs(cell[0] - goal[0]) + abs(cell[1] - goal[1])
def find_path_astar(maze):
start, goal = (1, 1), (len(maze) - 2, len(maze[0]) - 2)
pr_queue = []
heappush(pr_queue, (0 + heuristic(start, goal), 0, "", start))
visited = set()
graph = maze2graph(maze)
while pr_queue:
_, cost, path, current = heappop(pr_queue)
if current == goal:
return path
if current in visited:
continue
visited.add(current)
for direction, neighbour in graph[current]:
heappush(pr_queue, (cost + heuristic(neighbour, goal), cost + 1,
path + direction, neighbour))
return "NO WAY!"
In this animation, you can see how A\* traverse through a maze. As we can see, this algorithm finds the shortest path and uses fewer cells than BFS. Numbered cells are nodes in the priority queue (as they were added, but not as will be taken). Grey cells are visited. Orange cells show the resulting route.
Useful reading
Here is the list of the books which can be useful for learning Python, Algorithms and AI for GameDev:
These are Amazon affiliate links, so if decide to buy something from those books then the author of this page will be grateful.
