Python: Shortest Path in Maze

1. Introduction

Finding the shortest path in a maze is a classic problem of computer science. The problem can be solved using various algorithms, but one of the most intuitive methods is the Breadth-First Search (BFS). In this tutorial, we will use BFS to find the shortest path in a maze represented as a 2D matrix.

2. Program Overview

Our Python program will:

1. Represent the maze as a 2D list where 0 is an open path and 1 represents a wall.

2. Implement BFS to find the shortest path from a given start point to an endpoint.

3. Return the shortest path or notify if no path exists.

3. Code Program

from collections import deque

def is_valid_move(maze, visited, x, y):
    """Check if a move is valid."""
    return 0 <= x < len(maze) and 0 <= y < len(maze[0]) and not maze[x][y] and not visited[x][y]

def shortest_path_in_maze(maze, start, end):
    """Find the shortest path in the maze using BFS."""
    if not maze or not maze[0]:
        return None

    rows, cols = len(maze), len(maze[0])
    visited = [[False for _ in range(cols)] for _ in range(rows)]

    # Each element in the queue will be a tuple containing cell coordinates and its distance from the start
    queue = deque([(start, 0)])
    visited[start[0]][start[1]] = True

    # Possible moves in the maze: Up, Down, Left, Right
    moves = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    while queue:
        (x, y), dist = queue.popleft()

        # If this point is the end, return the distance (shortest path length)
        if (x, y) == end:
            return dist

        # Check all possible moves
        for dx, dy in moves:
            new_x, new_y = x + dx, y + dy
            if is_valid_move(maze, visited, new_x, new_y):
                visited[new_x][new_y] = True
                queue.append(((new_x, new_y), dist + 1))

    return None

# Sample maze: 0 is open path, 1 is wall
maze = [
    [0, 1, 0, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 1, 0],
    [0, 1, 1, 1, 0],
    [0, 0, 0, 0, 0]
]
start_point = (0, 0)
end_point = (4, 4)
print(f"Shortest path length: {shortest_path_in_maze(maze, start_point, end_point)}")

Output:

Shortest path length: 8

4. Step By Step Explanation

1. We start by defining a helper function is_valid_move that checks if a move is valid given the maze and visited nodes.

2. The main function shortest_path_in_maze initializes a visited matrix and sets up the BFS using a queue.

3. BFS works by exploring all possible moves at a current level before moving on to the next level. Thus, the first time we encounter the endpoint, we are guaranteed to have found the shortest path.

4. For each point, we check all potential moves (up, down, left, right). If the move is valid and leads to a solution, the function returns the length of the shortest path.

5. If there is no solution, the function will return None.

This approach ensures that we find the shortest path in the maze if it exists. Otherwise, we'll know that no solution is possible.