maze-solver-robot

A Maze Solver Robot project.
Explore Maze Solver Robot docs »

Report bug · Request feature

Maze solver Robot is a program to drive a robot through a 16x16 maze using Depth First Search as it’s path-planning algorithm. The program is integrated with Micro-mouse simulator a.k.a mms for visualizing the maze and the robot in real-time. The concepts of object-oriented programming, inheritance, and dynamic polymorphism were used to develop this project.

Table of contents

• Pre-Requisites
• Quick start
• Run instructions
• Status
• What’s included
• Documentation
• Bugs and Feature requests
• Creators
• Thanks

Pre-requisites

This app depends on Qt5 libraries. We can setup this up using apt-get package manager (for Debian linux) or conda virtual environment tool.

• setting up using pip installer

  sudo apt-get install qt5-default
  

Quick start

• Clone the repo in terminal using following command:

  git clone https://github.com/Sudharsan10/maze-solver-robot.git
  

  or download github repo as .zip and extract it in the desired location.

• If you would like to use latest micro-mouse simulator and maze files then do the following,

  git clone https://github.com/mackorone/mms.git
  

  git clone git https://github.com/micromouseonline/mazefiles.git
  

  Note: To install and setup anaconda environment follow this link first and visit this section again after successfully setting up the conda environment.

Run instructions

To run the app, first finish the pre-requisites mentioned above, then

• Navigate to the root directory of the cloned repo and start the Micro-Mouse Simulator(mms) using the following command:

  cd mms/src
  

  qmake && make
  

  ../../mms/bin/mms
  

  The last command will fire up the micro-mouse simulator.

If every requirement is fulfilled a window should open as follow,

Status

What’s included

Within the download you’ll find the following directories and files, logically grouping the classes under src directory. mazefiles and mms directories are submodules based out of third party repo. You’ll see something like this:

maze-solver-robot/
├── mazefiles/ ...
├── mms/ ...
├── docs/ ...
├── img/ ...
├── src/
|   ├── Algorithm/ ...
|   ├── API/ ...
|   ├── LandBasedRobot/ ...
|   ├── LandBasedTracked/ ...
|   ├── LandBasedWheeled/ ...
|   └── Maze/ ...
├── main.cpp
├── CMakeLists.txt
└── README.md

Documentation

For documentation related to the code you can refer the one provided under docs directory. A general outline explanantion with the help of flowcharts and images are provided in the following subsections,

Contents:

1. How to use
2. Class Structure
3. Depth First Search flowchart
4. Node Object Data Structure
5. Implementation
6. Project Execution

1 How to use

Enter the initial state of the puzzle and goal state of the puzzle as shown in the fig below.

• Click on the + icon from the config section, you will get a window like this,

• Enter all the fields in the respective locations,

  • Name: Any name of user choice to store the config.
  • Directory: The absolute path to the root directory of the project folder.

  • Build Command: It takes compiler that ‘g++’, ‘-std = c++14’ is the c++ standard we used, then relative path to all the necessary .cpp class files. If you haven’t changed any of the files and project structure you can go ahead and copy paste the following command.

    g++ -std=c++14 main.cpp src/LandBasedRobot/landbasedrobot.cpp src/LandBasedWheeled/landbasedwheeled.cpp 
    src/API/api.cpp src/Algorithm/algorithm.cpp src/LandBasedTracked/landbasedtracked.cpp src/Maze/maze.cpp
    

  • Run Command: use this command.

    ./a.out

  

• Then click, Build button and wait for it to turn green. If the previous step clears out then it will turn green indicating that we can run the simulator.
• To run click the Run and you will see the simulation of the robot exploring in the maze.

2 Class Structure

The following figure explains the class structure for all the classes in the src directory

3 Depth First Search & Ideal Implementation

• Depth first search:
• General Implementation of DFS algorithm flowchart
• Incorporating the DFS algorithm to solve the maze Flowchart

4 Node Object Data Structure

Since the above mentioned DFS algorithm and Solver has lot of redundancy loops like exploring or visiting same trail of path frequently. This is definitely a optimization issue, which has been resolved with the help of our own custom Node data structure and custom dfs and solver implementation algorithm.

• Custom Implementation:

5 Project Execution

Bugs and feature requests

Have a bug or a feature request? Search for existing and closed issues, if your problem or idea is not addressed yet, please open a new issue.

Creators

@Sudharsan : https://www.iamsudharsan.com

Thank you for visiting our Repo!