Path Finder is a visualization tool to demonstrate how different search algorithms work. I've created it while studying course Intro to Artificial Intelligence (https://classroom.udacity.com/courses/cs271). UI is built on Kivy framework (https://kivy.org/#home).
Install in two steps. Clone the repository and run provided script:
git clone https://github.com/tekian/path-finder.git
cd path-finder
.\pathfinder.bat (Windows)
./pathfinder.sh (Linux)
Provided scripts execute following steps:
- Checks you have Python 3 installed (searches in
PATH) - Installs required dependencies (from requirements.txt)
- Starts the application (by running src/pathfinder.py)
(Nothing else. No need to be paranoid. Read sources here and here.)
Run pathfinder.sh or pathfinder.bat depending on your platform. See Installation.
Application supports two modes of map generation:
- Grid Map – You can provide
X,Yand optionally how much% Edges to keep(edge cost equals 1) - File Spring Map – Red from file (example) & positions generated by Fruchterman-Reingold algorithm (Spring)
It supports following search algorithms:
- A* Search Algorithm – Implementation at a_star_finder.py
- Greedy First Search – Implementation at greedy_finder.py
- Breadth First Search – Implementation at bfs_finder.py
- Dijkstra (Least cost first search) – Implementation at dijkstra.py
(Code wise, these algortihm differ only in calculated cost function. See the code for details.)
You can choose from two playback modes:
- Step – You press
Stepevery time you want to move forward with the search - Continuous – You can control the speed &
Start/Stopthe algorithm
Last but not least, you can control Show options of nodes and edges at any time:
- Show node names - Name appears on top of the node
- Show node costs - Cost appears below the node
- Show edge costs - Cost appears in the middle of edge and below the line
Contributions are welcome. If you have time, passion and idea, go ahead and create a pull request.