Maze Solver for Micromouse

Highly Efficient Flood-Fill Algorithm Based Maze Solver for a Simulator.

This project contains the source code for a maze-solving algorithm designed for a Micromouse competition. The algorithm is implemented in C++ and is structured to navigate a 16x16 maze, find the optimal path, and perform a high-speed run from the start to the goal.

Table of Contents

• Project Overview
• Features
• Getting Started
  • Prerequisites
  • Compilation
• Usage
• Algorithm
  • Exploration Phase
  • Speed Run Phase
• File Descriptions

Project Overview

The Micromouse challenge involves a small robotic "mouse" that must find its way from a designated starting corner to the center of a maze. This project provides the control software for such a mouse. The code is written in C++ and is designed to be compiled and run within a Micromouse simulation environment.

The core of the project is a two-phase algorithm: first, an exploration phase to discover the maze layout and find a path to the goal, and second, a speed run phase to traverse the known path as quickly as possible.

Features

• Maze Exploration: The mouse systematically explores the maze, mapping walls as it goes.
• Pathfinding: Implements a flood-fill-based algorithm (using Manhattan distance) to continuously calculate the shortest path to the goal from any point in the explored maze.
• Path Compression: Optimizes the found path to remove unnecessary turns and movements for a faster speed run.
• Two-Phase Operation: Includes distinct modes for exploration and high-speed execution of the optimized path.
• API-driven: Designed to interact with a Micromouse simulator or hardware via a simple API.

Getting Started

Prerequisites

To compile and run this project, you will need a C++ compiler that supports C++17. The following compilers are supported:

• GCC
• Clang

Compilation

A Makefile is provided for easy compilation. You can build the project using the following commands:

• Build all versions (optimized and unoptimized with GCC and Clang):

  make all

• Build with GCC (unoptimized):

  make gcc_unoptimized

• Build with GCC (optimized):

  make gcc_optimized

• Build with Clang (unoptimized):

  make clang_unoptimized

• Build with Clang (optimized):

  make clang_optimized

• Clean up build files:

  make clean

The compiled executables will be created in the root directory of the project.

Usage

This program is intended to be run within a Micromouse simulation environment that provides the necessary API implementation. The main function in src/Main.cpp contains the main loop that controls the mouse's behavior.

The mouse starts in the EXPLORATION_TO_GOAL phase. Once the goal is found, it will (based on the commented-out code) switch to a series of speed run phases to return to the start and then race to the goal.

This is how you can use it:

• Clone/Download the Repository in your Local Device.
• Download the Simulator from Github:mackorone/mms Github Repository based on your Operating System.
• Then you can invoke the C++ files from src/ in the Simulator to Build and Run the Simulation.

Algorithm

The core of this maze solver is the Flood Fill algorithm, also known as the Manhattan Distance Transform. This algorithm is used to efficiently find the shortest path from any point in the maze to the goal. The overall process is divided into two main phases: exploration and speed run.

Core Algorithm: Flood Fill

The Flood Fill algorithm is the primary method used for pathfinding in this project. It works by assigning a value to each cell in the maze, representing the distance from that cell to the goal.

1. Initialization: The goal cells (the center of the maze) are assigned a value of 0. All other cells are initialized with a high value (infinity).
2. Flooding: The algorithm "floods" the maze from the goal cells. In each step, it looks at the neighbors of the cells with a certain distance value and assigns them a value of distance + 1, as long as there is no wall between them.
3. Pathfinding: The mouse then simply navigates from its current cell to an adjacent cell with a lower distance value. This guarantees that the mouse is always moving along the shortest path to the goal based on the currently known maze layout.

Why Flood Fill?

The Flood Fill algorithm is particularly well-suited for the Micromouse problem for several reasons:

• Guaranteed Shortest Path: For an unweighted grid like a maze, Flood Fill (which is a form of Breadth-First Search) is guaranteed to find the shortest path.
• Efficiency: The algorithm is computationally lightweight and requires minimal memory, making it ideal for resource-constrained microcontrollers typically used in Micromouse robots.
• Dynamic Updates: As the mouse explores and discovers new walls, the Flood Fill algorithm can be re-run to quickly update the distance values and find a new shortest path based on the new information. This is crucial for the exploration phase.
• Simplicity: The logic is relatively simple to implement and debug compared to more complex pathfinding algorithms.

Exploration Phase

1. The mouse starts at the corner (15, 0) and faces North.
2. It uses its sensors (via the API) to detect walls in front, to the left, and to the right.
3. The detected walls are recorded, and the Flood Fill algorithm is re-run to update the pathfinding data.
4. The mouse then moves to the adjacent cell with the lowest value according to the Flood Fill map. It prioritizes unexplored cells to ensure the entire maze is eventually mapped.
5. This process continues until the mouse reaches the goal area in the center of the maze.

Speed Run Phase

1. Once the exploration path is found, it is compressed to create a more optimal path for the speed run. The compression removes redundant sequences like turning back on the same path.
2. The mouse returns to the starting position.
3. The mouse then executes the compressed path at high speed to reach the goal as quickly as possible.

File Descriptions

• src/Main.cpp: The main entry point of the application. It contains the main loop that switches between different phases of the maze-solving process.
• src/API.h: Defines the Application Programming Interface (API) for interacting with the Micromouse hardware or simulator. This includes functions for moving the mouse, detecting walls, and getting maze dimensions.
• src/API.cpp: The implementation of the API. This file is empty as it is expected to be provided by the simulation environment.
• src/Handler.h: Contains the high-level logic for handling the different phases of the maze-solving process (exploration and speed runs).
• src/Util.h: A utility header file containing core data structures, maze-solving algorithms (flood-fill, pathfinding), and helper functions.
• src/Example_Path.txt: Contains examples of explored and compressed paths.
• Makefile: The makefile for compiling the project with various options.
• LICENSE: The license for the project.
• .gitignore: Specifies which files and directories to ignore in a Git repository.

---

Contact

Facebook   Instagram   Linkedin   X