Skip to content

Grid-based visualizing tool for pathfinding algorithms, written in Python with Qt

License

Notifications You must be signed in to change notification settings

TheShepord/pathfinding-visualizer

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

23 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

pathfinding-visualizer

Github license

Grid-based visualizer for popular pathfinding algorithms. Written in Python, with PyQt5 for rendering and UI.

GIF overviewing pathfinding-visualizer's features

Left-click on empty tiles to begin drawing barriers, left-click on barriers to begin erasing them. Left-click on start or goal to drag them around. Select different algorithms and heuristics using the menubar.

Implementation

Algorithms

  • A* Search
    • Searches nodes based on f(n) = cost_so_far(n) + heuristic(n)
    • Weighted, always optimal given an admissible heurisitic
  • Dijkstra's algorithm
    • Searches nodes by progressively moving further from the starting node
    • Weighted, always optimal
  • Greedy Best-First Search
    • At every step, explore the best node according to chosen heuristic
    • Weighted, not always optimal
  • Breadth-First Search
    • Nodes are progressively explored by adding neighbors to a queue
    • Unweighted, always optimal given an unweighted graph
  • Depth-First Search
    • Nodes are progressively explored by pushing neighbors to a stack
    • Unweighted, not always optimal

Heuristics

  • Manhattan: distance between two nodes measured along axes
  • Euclidean: straight-line distance between two nodes
  • Chebyshev: distance between two nodes measured along axes, but diagonal movement costs 1
  • Octile: distance between two nodes measured along axes, diagonal movement costs √2

Usage

$ cd <path of project install> $ python3 pathfinding-visualizer.py

Upcoming Features

  • Support for visualizing and modifying individual cell weights
  • Legend for different node colors
  • In-app display of each algorithm's characteristics
  • Create your own heuristic formulas
  • More algorithm options

About

License: This project is released under the MIT License.

References:

About

Grid-based visualizing tool for pathfinding algorithms, written in Python with Qt

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages