# Path-Finding

**Repository Path**: bit2atom/Path-Finding

## Basic Information

- **Project Name**: Path-Finding
- **Description**: A visual demonstration of the process undrgone by Dijkstra and A* (A star)
- **Primary Language**: Java
- **License**: MIT
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2020-08-25
- **Last Updated**: 2020-12-19

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# Path Finding

## Description
This program provides a visual demonstration of the process undrgone by Dijkstra and A* (A star)

### [YouTube Video](https://www.youtube.com/watch?v=xGdBwdd_FLc&t)

## Dijkstra
Dijkstra's algorithm works by first adding the starting node to a priority que. It then takes the top node in the priority que and looks at all of the nodes surrounding it. If the nodes are valid positions then they are added to the priority que and the top node in the que is deleted. These nodes that are added to the que also have a knowledge of what node they were explored from (ie. their parent node) This process is continued until a node is discovered with the same location as the finish node. From that node, a path is created by retracing the steps to the starting node. 

![dijkstra](https://user-images.githubusercontent.com/36581610/50039437-a6cd8e80-0000-11e9-865a-1c6062046d4f.gif)

## A*
A* works similarly to dijkstra by creating a priority que of nodes and then adding new nodes to the que by exploring the top node on the que. However in A* the nodes are placed into the que with a heuristic of distance to the finish node. This means that the node at the top of the que is always the node closest to the finish node.

![astar](https://user-images.githubusercontent.com/36581610/50039438-af25c980-0000-11e9-9fda-f96a2ee6cb2e.gif)

## Draw a maze
![drawmaze](https://user-images.githubusercontent.com/36581610/51815322-197f8a00-228e-11e9-80c9-b088d76b3ba2.gif)