Skip to content

This is a program to drive a robot through a maze using Depth First Search as it's path-planning algorithm. The program is interfaced with Micromouse simulator 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.

Notifications You must be signed in to change notification settings

Sudharsan10/maze-solver-robot

Repository files navigation

Social-header

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

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,

start-screen

Status

Documentation Status Maintenance Doc Tool made-with-C++ pyqt-version made-with-Markdown contributors Logo Flow-charts

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!

About

This is a program to drive a robot through a maze using Depth First Search as it's path-planning algorithm. The program is interfaced with Micromouse simulator 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.

Topics

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published