# Running Mazey
This program generates a random maze from an initial grid and then Mazey (an A.I. :P) finds the approximate shortest path from top left corner to the bottom right corner of the grid.

## Algorithm Used: A* Search Algorithm

A* is a computer algorithm that is widely used in pathfinding and graph traversal, which is the process of finding a path between multiple points, called "nodes".<br>
Peter Hart, Nils Nilsson and Bertram Raphael of Stanford Research Institute (now SRI International) first published the algorithm in 1968. It can be seen as an extension of Edsger Dijkstra's 1959 algorithm.<br>
A* achieves better performance by using heuristics to guide its search.

## Step 1: Maze Generation
###### source: [Maze generation algorithms](https://en.wikipedia.org/wiki/Maze_generation_algorithm)

<img src="media/mazeGeneration.gif" height=300>

## Step 2: Finding the shortest path from top left corner to bottom right corner
###### source: [A* Search Alogrithm](https://en.wikipedia.org/wiki/A*_search_algorithm)

<img src="media/mazeyRunning.gif" height=300>

## Final path

<img src="media/path.png" height=300>

## Author


<table>
<tr>
<td>
<img src="https://avatars3.githubusercontent.com/u/31174685?s=460&v=4" width="180"/>

Divyanshu N Singh

<p align="center">
<a href = "https://github.com/DNS-404"><img src = "http://www.iconninja.com/files/241/825/211/round-collaboration-social-github-code-circle-network-icon.svg" width="36" height = "36"/></a>
<a href = "https://twitter.com/divyanshunsingh"><img src = "https://www.shareicon.net/download/2016/07/06/107115_media.svg" width="36" height="36"/></a>
<a href = "https://www.linkedin.com/in/divyanshunsingh/"><img src = "http://www.iconninja.com/files/863/607/751/network-linkedin-social-connection-circular-circle-media-icon.svg" width="36" height="36"/></a>
</p>
</td>
</tr> 
</table>
