MARS_PathFinder

Navigate the Mars Curiosity Rover using various pathfinding algorithms, visualize routes found, add checkpoints, mazes along the way to reach its base and drag checkpoints and endpoints in real time.

Comment

Inspiration

As engineering undergraduates starting off with graph theory algorithms and path planning techniques, we chanced upon this amazing web app built by Clement Mihailescu and explained on his YouTube channel. https://clementmihailescu.github.io/Pathfinding-Visualizer/# https://github.com/qiao/PathFinding.js We have always been inspired by space explorations and voyages, and how unmanned vehicles are able to plan their way on a foreign planet with little human intervention, avoiding obstacles along the way and responding fast to changing environmental conditions. Hence to improve our understanding of Path Planning algorithms and to give some shape to our childhood dream of operating an actual Rover on Mars, we put together this project.

What it does

This application finds the shortest path from the rover's initial node to its destination node using various shortest distance algorithms like A*, Dijkstra, etc. It lets the operator specify control parameters like avoid corners, allow diagonal movement etc. depending on the Rover's design. It also allows the operator to set checkpoints through which the Rover must pass to reach the destination. Other features such as maze generation using random and recursive algorithms have been implemented. The control buttons are dynamics and message bot TARS guides the user through the app. Our app also supports the dynamic dragging of checkpoints and start/endpoints and as well as dynamic addition, removal of checkpoints.

Path planning algorithms incorporated:

- AStarFinder
- BestFirstFinder
- BreadthFirstFinder
- DijkstraFinder
- IDAStarFinder.js
- JumpPointFinder
- OrthogonalJumpPointFinder
- BiAStarFinder
- BiBestFirstFinder
- BiBreadthFirstFinder
- BiDijkstraFinder
- CollaborativeLearningAgentsFinder

Features built:

Multiple Destinations

- Ctrl+ Click on grid cells to add checkpoints.
- The agent covers the checkpoints in the shortest path order and reaches the destination.
- Rendering using Travelling salesman algorithm.
- Dynamic Rendering of path through just drag and drop The shortest path is dynamically visible if the user even after search is over drags the nodes.
- Removal and addition of checkpoints by Ctrl+Click on them, and instant path re-rerouting.
- Music loop in-game
- Interactive Guide using SweetAlert
- TARS bot to provide instructions to the user

How I built it

The UI is built using Raphael.js library and basic HTML, CSS, and Js, and our web app has been tested on four browsers: Firefox, Google Chrome, Safari, and MS Edge. The path-finding algorithms, maze algorithms are implemented using JS following the OOP programming paradigm, the multiple destination routing is handled using the Travelling Salesman approach to make sure the shortest possible path is found reaching every checkpoint and the final endpoint, and the instructions are displayed using SweetAlert. The compiling and bundling of the application are handled by Gulp and Npm and for version control, we have used Git and BitBucket.

Challenges I ran into

We ran into issues implementing the Path-Finding algorithms using Javascript and quite a few of the concepts were derived from research papers and articles, so understanding them and implementing each of them took a lot of effort. Besides, as our goal was to make the user experience smooth and fun, we had to come up with innovative ideas to convey the app's functionality to the user using guides, Messagebot, etc. Besides, implementing TSP, which is believed to be one of the most intriguing problems in the CS domain, and handling the complexity of our implementation was an algorithmic challenge that prompted us to read papers and refer to quite a few courses to clear our concepts of Graph Theory.

Accomplishments that I'm proud of

We are proud that we were able to work as a team and create an easily operable app with aesthetic designs. The real-time rendering of dragging is one of the highlights for us. We are also proud of creating a user-friendly app by introducing the message bot TARS. Not only did we consider the coding and implementation part of the project, but we also considered a good user experience.

What I learned

We used the OOP programming paradigm to create this app. We learned how to build and add features using good coding practices. We also learned the various algorithms used to find the shortest path from starting point to destination, and how they work under specific conditions (for example, allowing diagonals or not). We also learned how states (ready, start, pause, clear, etc) can be used to set the viable controls appropriately. This allows easy and systematic addition of features.

What's next for MARS_PathFinder

We plan to add obstacles of various types like bombs etc. as well as rewards like fuel, coins to improve the user experience. Further, we plan to build a game out of this project, where multiple users can play against each other to choose the controls that can give the shortest path in the least possible time collecting the maximum amount of rewards.

Share this project:

Updates