Scribd
Upload
3 views1 page

BFS Shortest Path in Maze Algorithm

This document outlines an algorithm to find the shortest path in a maze using Breadth-First Search (BFS). The maze is represented as a 2D array with open and wall cells, and the algorithm explores possible moves level by level. The final path is visualized with 'P' marking the cells on the path from start to goal.

Uploaded by

uff9945
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
3 views1 page

BFS Shortest Path in Maze Algorithm

This document outlines an algorithm to find the shortest path in a maze using Breadth-First Search (BFS). The maze is represented as a 2D array with open and wall cells, and the algorithm explores possible moves level by level. The final path is visualized with 'P' marking the cells on the path from start to goal.

Uploaded by

uff9945
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

# Algorithm (high-level)

1. Read grid dimensions (rows, columns).


2. Read the maze as a 2D array maze where 0 = open, 1 = wall.
3. Read start and goal coordinates (tuples).
4. Run Breadth-First Search (BFS) from start to find the shortest path (in steps) to
goal:
o Maintain a queue of paths (each path is a list of coordinates). Initialize with
[[start]].
o Maintain a visited set to avoid revisiting cells.
o While the queue is not empty:
 Pop the leftmost path; let (x,y) be its last cell.
 If (x,y) == goal, return that path.
 For each of the four neighbors (up, down, left, right) that are inside
bounds and maze[nx][ny] == 0 and not yet visited:
 Mark visited, append neighbor to a new path, and push that
path to the queue.
o If queue empties without finding goal, return None.
5. Print the path (or None) and visualize the maze; mark cells on the path with P.

This program uses Breadth-First Search (BFS) to find the shortest path in a maze from a
start to a goal position.
The maze is represented as a grid where 0 = open and 1 = wall.
BFS explores all possible moves level by level using a queue, ensuring the first path found is
the shortest.
The final path is displayed visually using P for the path.

You might also like