Project Name: NAVIGATE THE MARS ROVER
Team Name: Mangalprani
Task : Help the Mars Curiosity Rover find the shortest path between two points while avoiding obstacles on the way.
NOTE: This project is not suitable for mobiles or older versions of browsers. Google Chrome or Safari work best. Implementing on full screen is recommended(preferably 13"-15").
To view the project, click this link: https://shortestpathfindingrover.herokuapp.com/
INTRODUCTION :
• What is Pathfinding Visulaizer? - It is called a Pathfinding Visualizer, aptly because it does what it says, it finds a path from a source to a destination. This project is based on graph theory.
• Pathfinding Visulaizer is a visualizing tool that shows how different pathfinding algorithms work. The program's objective is to go from the start cell to the end cell using a pathfinding algorithm. You can draw walls by clicking or holding down the mouse over cells. Then select the Algorithm by "Path Algorithm" tab. Once the algorithm has found the start cell, the optimal path will be illuminated in yellow. Additionally, mazes can be generated by selecting an algorithm from the "Mazes Algorithm" tab.
• Build application for visualizing pathfinding and maze-generation algorithms .
• Implemented 5 DIFFERENT ALGORITHMS to find the shortest path between the start and the end while avoiding obstacles on the way .
• Currently there are 5 path-finders bundled in this library, namely:
- Dijikstra
- Breadth First Search - Normal
- Breadth First Search - Bidirectional
- A* Algorithm
- Best First Serach - Normal
• INSTRUCTIONS :
- CLEAR BOARD: To clear all walls, paths and put the start point and End point to their original Position.
- MAZE ALGORITHMS: Choose any maze algorithm to generate a maze.
- NODE ACTIONS: Choose any node action to add or delete the mid node (second destination point).
- PATH ALGORITHMS: Choose any path algorithm to find the shortest path between start point and destination point.
- SHOW TIME AND DISTANCE: To show the time taken to find the shortest path, and the distance between start point and destination point .
- After finding the shortest path we can move the start point and end point in order to know the various shortest paths for the same algorithm but different positions of the start point and end points.
Meet the Algorithms-->
1. A*Search A* (pronounced as "A star") is a computer algorithm that is widely used in pathfinding and traversal. The algorithm efficiently plots a walkable path between multiple nodes, or points, on the graph. On a map with many obstacles, pathfinding from points AA to BB can be difficult. A robot, for instance, without getting much other direction, will continue until it encounters an obstacle, as in the path-finding example to the left below. However, the A* algorithm introduces a heuristic into a regular graph-searching algorithm, essentially planning ahead at each step so a more optimal decision is made. With A*, a robot would instead find a path in a way similar to the diagram on the right below. A Search* (weighted): arguably the best pathfinding algorithm; uses heuristics to guarantee the shortest path much faster than Dijkstra's Algorithm
2. Breadth -First Search (BFS)
BFS is a unweighted graph traversal algorithm that starts the traversal from the source node and explores all the neighbouring nodes. It follows the principle of level order traversal, where it selects the nearest node and explore all the unexplored nodes. It is a great algorithm which is simple to implement using Queue. It also guarantees the shortest path from source to destination, if exists. The Space Complexity of the BFS algorithm is b^d (branching factor raised to the depth of the graph).
3. Dijkstra's Algorithm (weighted): the father of pathfinding algorithms; guarantees the shortest path. Dijkstra’s algorithm finds a shortest path tree from a single source node, by building a set of nodes that have minimum distance from the source.
4. Depth-First Search (DFS) DFS is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the source node and explores as far as possible along each branch before it backtracks and follows the remaining edges of a node. It is very inefficient algorithm for path-finding and it does not guarantee shortest path. It includes exhaustive searches of all the nodes by going ahead, if possible, else by backtracking. It uses Stack for its implementation. It can get stuck in an infinite loop, which is why it is not "Complete". The Space Complexity of the DFS algorithm is O(log(d)) where is 'd' is the depth of the graph.
5. Greedy Best-First Search It is a suboptimal best-first search algorithm which works on the principle of A* Algorithm and always priorities the node with the lowest heuristic value without any consideration of the cost to get to that node. While this greedy GBFS algorithm can be effective in practice, it can be misled by an arbitrary amount if th heuristic is wrong. Hence, it does not gurantee shortest path.
On top of the pathfinding algorithms listed above, I implemented a Recursive Division Maze Generation algorithms. the Maze Generation has been implemented using DFS Algorithm.
The graph has the following: • vertices, or nodes, denoted in the algorithm by vv or uu; • weighted edges that connect two nodes: (u,vu,v) denotes an edge, and w(u,v)w(u,v) denotes its weight. In the diagram on the right, the weight for each edge is written in gray.
This project was bootstrapped with Create React App.
In the project directory, you can run:
Runs the app in the development mode.
Open https://shortestpathfindingrover.herokuapp.com/ to view it in the browser.
The page will reload if you make edits.
You will also see any lint errors in the console.
Launches the test runner in the interactive watch mode.
See the section about running tests for more information.
Builds the app for production to the build folder.
It correctly bundles React in production mode and optimizes the build for the best performance.
The build is minified and the filenames include the hashes.
Your app is ready to be deployed!
See the section about deployment for more information.
Note: this is a one-way operation. Once you eject, you can’t go back!
If you aren’t satisfied with the build tool and configuration choices, you can eject at any time. This command will remove the single build dependency from your project.
Instead, it will copy all the configuration files and the transitive dependencies (webpack, Babel, ESLint, etc) right into your project so you have full control over them. All of the commands except eject will still work, but they will point to the copied scripts so you can tweak them. At this point you’re on your own.
You don’t have to ever use eject. The curated feature set is suitable for small and middle deployments, and you shouldn’t feel obligated to use this feature. However we understand that this tool wouldn’t be useful if you couldn’t customize it when you are ready for it.
You can learn more in the Create React App documentation.
To learn React, check out the React documentation.
This section has moved here: https://facebook.github.io/create-react-app/docs/code-splitting
This section has moved here: https://facebook.github.io/create-react-app/docs/analyzing-the-bundle-size
This section has moved here: https://facebook.github.io/create-react-app/docs/making-a-progressive-web-app
This section has moved here: https://facebook.github.io/create-react-app/docs/advanced-configuration
This section has moved here: https://facebook.github.io/create-react-app/docs/deployment
This section has moved here: https://facebook.github.io/create-react-app/docs/troubleshooting#npm-run-build-fails-to-minify