Pathfinding.js in Microsoft Engage
The project done by my team and I in the Mars Colonisation Program, as part of the Microsoft Engage 2020.
If you haven’t read my article on the Mars Colonisation Program With Microsoft, go read that first!
Table of Contents
- Introduction
- Problem Statement
- Evaluation Criteria
- Brainstorming Sessions
- The Example Code
- Our Project
- Low Level Usage
- Online Demo of the Final Project
- Submission
- Future Possibilities
- Important Links
Introduction
This article mainly talks about the overall project implementations we did, the software we used, the algorithms we deployed, and the functionalities we added to our project, in the Mars Colonisation Program, as part of Microsoft Engage 2020, which was held in the months of June-July.
Problem Statement
We could choose any project from the two choices, whose example code was also given -
- Navigate the Mars Rover
Help the Mars Curiosity Rover find the shortest path between two points while avoiding obstacles on the way.
2. Entertain the Crew
Engage your Crew by Using Minmax algorithm to build an unbeatable Tic Tac Toe game powered by AI.
We were allowed to form teams, and my team consisted of 4 members -Nikita, Jagriti, Gauranshi, and I. Since we all had some previous experience with path finding algorithms, we decided to go with the first project, the Mars Rover Navigation one.
Evaluation Criteria
We would be evaluated on a number of criteria -
- Uniqueness of Solution -How did our solution differ from the example code provided to us?
- Technical Achievement -What were the programming approaches we took in our project?
- Code Quality -Did we have optimum size, consistency, structure, and complexity of our code base on GitHub?
- Relevance to Theme -How close did we stay to the problem statement and the overall theme of the project?
Brainstorming Sessions
The team, now named Code_Brewers, did a bunch of brainstorming sessions, where we came up with ideas in sync with the evaluation criteria, discarded them due to infeasibility, or because they were too difficult to implement, or because they were not in accordance with the theme of the project, and came up with even more ideas. We had had to figure out how we were going to incorporate unique code, since the example code was nearly completely optimised and perfect. We sat down over many days, spoke to our mentor, Richa Agarwal, a software engineer at Microsoft, and hashed out a plan of action and deliverables of the project.
The Example Code
The code that was shared with us as an example was a GitHub repository, and was made as a pathfinding library to incorporate into grid based games and the like. It used multiple path finding algorithms to find the shortest path between two points, and also plotted the path found on a virtual grid, with animations. It also allowed for user -input obstacles, which the algorithm would then avoid.
Our Project
The following were the implementations we decided to go ahead with, in order to gain points in the evaluation criteria -
- Introduce multiple possible destination points, where the pathfinder has to find the closest destination and find the shortest path to that point too.
- Introduce stop points, which stand for data collection points on Mars, and the pathfinder has to find the shortest route covering all the points, like a circuit.
- Introduce visitation points, and the pathfinder has to find the shortest path from the start to the end which is the shuttle boarding point, and hence has to be the final point visited, and visit all the points.
- Optimise the code in algorithms by using OOP and data structures that enhance speed (for example, binary heaps in A * algorithm)
Low Level Usage
The algorithms we used in our project -
- Breadth First Search
- A* Search
- Dijkstra Search
- Prim’s Algorithm
We also incorporated the bi-directional approaches of these algorithms, along with diagonal movement of the nodes.
The programming languages we used -
- Javascript
- CSS
- HTML
The existing libraries we used -
- Node.js was used to run the application
- State Machine.js -to process various inputs and states
- Raphael.js -to create the SVG (scalable vector graphics)
Most of the visual part of the project was borrowed from the example code, though a few changes were made on the interaction, design, and ease of usage. The web application was built to run on Microsoft Edge, Safari, Chrome, and Firefox. It was hosted using Git Pages.
Online Demo of the Final Project
The online demo working with visitation and stop points -
Submission
The team was able to successfully implement all our strategies with the supporting documents, and submit the project before the deadline in the last week of July -4 minutes before, to be exact, but who’s counting? ;)
Results were announced in the second week of August, and our team placed 4th amongst all 4-member teams! It came as a delightful surprise, and we felt like all our hard work paid off.
Future Possibilities
Possible functionalities which couldn’t be implemented due to the short duration of the program -
- Weighted points, where the weights stand for the safety of that position on Mars, For example, a crater, or a very hot area will have higher weight, as it is more dangerous for the rover to go over such terrain. An algorithm may then be implemented to optimise for the weighted path, leading to finding the safest path for the rover to follow.
- Treasure points, where rich samples of sand, etc., can be found, but where the rover need not necessarily go. An algorithm can be implemented to maximise the rover’s reward/treasure, while also minimising the distance travelled, basically find an optimum path by varying 2 parameters.
