Exploring the Depths: Solving Mazes with A* Search Algorithm
Mazes have captured the human imagination for centuries, from ancient labyrinthine structures to modern video game challenges. Solving mazes programmatically poses an interesting problem in computer science, and one effective solution is the A* search algorithm. In this article, we’ll dive into the A* and explore how it can be applied to navigate through mazes efficiently.
A* (pronounced “A-star”) is a popular pathfinding algorithm widely used in robotics, video games, and artificial intelligence. It efficiently finds the shortest path from a starting point to a goal by combining the strengths of Dijkstra’s algorithm and greedy best-first search. A* uses a heuristic to estimate the cost of reaching the goal from a given state.
Understanding the maze
Mazes are spatial puzzles, and representing them effectively is crucial for implementing algorithms like A* search. A common and intuitive representation is using a 2D grid. We choose a data structure comprensive of walls and passages. The discrete nature of a grid simplifies the modelling of paths and obstacles. It allows for straightforward navigation between adjacent cells.
Mazes can have intricate layouts with dead ends, loops, and alternative paths. A* must navigate through this complexity to find the shortest route.
Each cell in the grid represents both the walls and the steps, so when you move from one cell to another, you skip a cell, and then the actual movement occurs over a distance of two cells in a horizontal or vertical direction.
- Odd cells: represent the cells of the labyrinth (1 represents a wall, 0 represents a passage).
- The even cells: represent the walls between the cells of the labyrinth.
Maze generation
A valid strategy to generate a maze is to start from a full walls grid and move by two step from a random cell.
The algorithm starts with a solid area and proceeds to remove walls randomly, ensuring that all cells are reachable between them. This ensures that there is always a path from a starting cell to a target cell. This idea is a randomized versions of depth-first search algorithm.
The depth-first search is frequently implemented using backtracking and is often implemented by a recursive routine. A disadvantage of this approach is a large depth of recursion — in the worst case, the routine may need to recur on every cell of the area being processed, which may exceed the maximum recursion stack depth in many environments. As a solution, the same backtracking method can be implemented with an explicit stack.
def gen(size: int) -> list[list[int]]:
def get_neighbors(r, c):
_n = []
for dx, dy in [(-2, 0), (2, 0), (0, -2), (0, 2)]:
x, y = r + dx, c + dy
if 0 <= x < size and 0 <= y < size and maze_map[x][y] != MazeBlocks.PASSAGE:
_n.append((x, y))
return _n
size = size * 2 + 1
maze_map = [[MazeBlocks.WALL] * size for _ in range(size)]
stack = [(1, 1)]
maze_map[1][1] = MazeBlocks.PASSAGE
while stack:
i, j = stack[-1]
maze_map[i][j] = MazeBlocks.PASSAGE
neighbors = get_neighbors(i, j)
if neighbors:
neighbor = random.choice(neighbors)
maze_map[(i + neighbor[0]) // 2][(j + neighbor[1]) // 2] = MazeBlocks.PASSAGE
stack.append(neighbor)
else:
stack.pop()
# Create the entrance and the exit
maze_map[0][1] = MazeBlocks.PASSAGE
maze_map[size - 1][size - 2] = MazeBlocks.PASSAGE
return maze_mapThe result is a matrix, but to use it with a generalized version of the A* algorithm, I suggest to converting the 2D vector into an undirected graph.
Graph data structure allows A* to navigate the maze seamlessly. The start and goal locations become nodes in the graph, and the algorithm explores edges to find the optimal path. Each cell becomes a node, and the connections between cells become edges.
Components of A* Search
A* can be seen as an extension of Dijkstra’s algorithm. Both are used to find the shortest path in a graph.
Typical implementations of A* use a priority queue to perform the repeated selection of minimum (estimated) cost nodes to expand. This priority queue is known as the open set, fringe or frontier. At each step of the algorithm, the node with the lowest value is removed from the queue. The algorithm continues until a removed node is a goal node, take a look at his pseudo-code:
function A_Star(start, goal, h)
// The set of discovered nodes that may need to be (re-)expanded.
// Initially, only the start node is known.
// This is usually implemented as a min-heap or priority queue rather than a hash-set.
openSet := {start}
// For node n, cameFrom[n] is the node immediately preceding it on the cheapest path from the start
// to n currently known.
cameFrom := an empty map
// For node n, gScore[n] is the cost of the cheapest path from start to n currently known.
gScore := map with default value of Infinity
gScore[start] := 0
// For node n, fScore[n] := gScore[n] + h(n). fScore[n] represents our current best guess as to
// how cheap a path could be from start to finish if it goes through n.
fScore := map with default value of Infinity
fScore[start] := h(start)
while openSet is not empty
// This operation can occur in O(Log(N)) time if openSet is a min-heap or a priority queue
current := the node in openSet having the lowest fScore[] value
if current = goal
return reconstruct_path(cameFrom, current)
openSet.Remove(current)
for each neighbor of current
// d(current,neighbor) is the weight of the edge from current to neighbor
// tentative_gScore is the distance from start to the neighbor through current
tentative_gScore := gScore[current] + d(current, neighbor)
if tentative_gScore < gScore[neighbor]
// This path to neighbor is better than any previous one. Record it!
cameFrom[neighbor] := current
gScore[neighbor] := tentative_gScore
fScore[neighbor] := tentative_gScore + h(neighbor)
if neighbor not in openSet
openSet.add(neighbor)
// Open set is empty but goal was never reached
return failureThe fundamental component is the cost function f(n) which encapsulates both the actual cost and the heuristic estimate, it determines the priority of a node in the exploration queue (row 18). Nodes with lower total costs are explored first, fostering an efficient search process.
The actual cost g(n) represents the cumulative cost from the starting node to the current node. The heuristic function h(n) estimates the cost from the current node to the goal. It provides an informed guess about the remaining distance.
f(n) = g(n) + h(n)
The effectiveness of A* heavily relies on the choice of heuristic functions. Heuristics must satisfy two crucial properties:
- Admissibility: A heuristic is admissible if it never overestimates the true cost to reach the goal. In other words, h(n) should always be less than or equal to the actual cost.
- Consistency (or the Triangle Inequality): A heuristic is consistent if the estimated cost from the current node to the goal, plus the estimated cost from the current node to a successor, is always greater than or equal to the estimated cost from the current node to that successor.
Choosing an appropriate heuristic is a delicate balance. The right heuristic enhances the efficiency of the algorithm, while an inaccurate or overly optimistic heuristic might lead A* astray.
For our problem a good approach is to calculate the distance from a certain node (cell in the grid) to the goal node, the maze exit. This can be done with various formulas, we choose the Manhattan Distance. Also known as the L1 norm or taxicab distance, is a common heuristic for grid-based mazes. It calculates the distance between two points on a grid by summing the absolute differences in their x and y coordinates:
def heuristic(node: tuple[int, int], goal: tuple[int, int]):
return abs(node[0] - goal[0]) + abs(node[1] - goal[1])Manhattan Distance is a good default choice due to its simplicity and computational efficiency. It’s often beneficial to experiment with different heuristics to determine which one performs best for a given scenario.
Solving maze
The primary challenge is to find the optimal path from the start to the goal. Based on previous pseudocode, a python implementation should be like:
def astar(g: dict, start_node: tuple[int, int], goal_node: tuple[int, int]) -> list | None:
open_set = [(0, start_node)]
came_from = {}
cost_so_far = {start_node: 0}
# A commonly used heuristic for maze-solving is the Manhattan distance
def heuristic(node: tuple[int, int], goal: tuple[int, int]):
return abs(node[0] - goal[0]) + abs(node[1] - goal[1])
def rebuild_path(n):
p = [n]
while n in came_from:
n = came_from[n]
p.append(n)
return p
while len(open_set) > 0:
curr_cost, curr_node = heappop(open_set)
if curr_node == goal_node:
goal_path = rebuild_path(goal_node)
return goal_path
for neighbor in g[curr_node]:
new_cost = cost_so_far.get(curr_node) + 1
if neighbor not in cost_so_far or new_cost < cost_so_far[neighbor]:
cost_so_far[neighbor] = new_cost
priority = new_cost + heuristic(neighbor, goal_node)
heappush(open_set, (priority, neighbor))
came_from[neighbor] = curr_node
return None- g is an adjacency matrix of the undirected graph representing the maze.
- start_node: is coordinates tuple of the starting node (cell).
- goal_node is the goal node tuple.
The algorithm returns the list of nodes that make up the fastest path (with fewer cells) that, starting from the initial cell, reaches the final cell, the exit of the maze.
Visualizing the maze-solving progress can enhance understanding and provide valuable insights. matplotlib, a versatile plotting library in Python, can be employed to create visual representations of the maze, the pathfinding steps, and the algorithm’s progress.
In the following example, the green (and red) dots are the explored cells, and the red dots are the current optimal path found. When the exit is reached, this will turn blue.
Conclusion
Solving mazes with A* search is not just a computational exercise but a journey through the intricacies of navigation algorithms. A* excels in unraveling the mystery of mazes, offering not just a path but the optimal path. As we traverse the corridors and pathways of these mazes, A* stands as a guiding beacon, showcasing the elegance and efficiency of modern pathfinding algorithms.
