Description

In this project, my team and I created a maze exploration software. We generated a random maze (sized according to user's choice), and solved it for the simulated robotic agent. The agent is taking discrete steps on a grid in the maze, while trying to navigate to a goal.

Take a look at the project on my GitHub page.

Solving 31x11 maze

Overview

Core Tasks

In this project, we had 5 core tasks:

1. Maze generation
2. Maze state
3. Solve the maze
4. Display the maze
5. Maze interface

Maze generation

Generate a maze by implementing the randomized Prim's maze generation algorithm.

The pseudocode for this algorithm:

Maze generation pseudocode

Maze state

Track the state of the maze and determine if a grid square is wall/free, or is it the goal/start point. Be able to find the 1-hop and 2-hop neighbors of a cell (for maze generation and exploration).

Solve the maze

Implement the "Wavefront Planner" maze solving algorithms.

The pseudocode for Wavefront Planner algorithm:

1. Breadth-first search approach
2. Start at the goal
3. Advance one square in every direction and mark with a 1
4. From each 1, advance to every open square and mark with a 2
5. From each n-1 square advance to every open square and mark with an n
6. Stop when there are no more squares to explore
7. From any starting point, move to the adjacent cell with the lowest number
8. Stop at the goal

The algorithm finds the shortest path to a given goal from every starting point, but it requires full knowledge of the maze.

Maze interface and display

Display the maze's walls, free cells, start position, and goal position. Constantly update the display of the robot position as it moves.

In the following video, the software generates and solves a 20x13 maze:

Solving 20x13 maze