pathfind-visualiser 0.1.3

Description:

pathfindvisualiser 0.1.3

pathfind-visualiser








Description
Pathfinding algorigthms written in Python and visualised with the Pygame library. Also has a couple built-in maze generation algorithms, and gives the user the ability to create their own mazes by hand, so that algorithms can be observed under a variety of different circumstances.
Installation
Using pip (if you're on Windows, replace python3 with just python down below):
python3 -m pip install pathfind-visualiser

Then, launch the program by running the command:
pathfind-visualiser

Note that if the command does not work you may need to configure your system PATH variable (check out some Stack Overflow answers linked below).

Windows
Linux or Mac

Usage

From the main menu, read the instructions and keys sections to familiarise yourself with how to use the interface
In the options section select the number of rows/columns you want and select a maze type (or leave it on none)

Note: Random is it's own maze generating algorithm (defined below)


Click on the algorithm you wish to visualise and the maze should appear
If you wish to view another algorithm (or take another look at the instructions), press the Esc key to return to the main menu

The Algorithms:
1. A* Search Algorithm

Uses a heuristic function (manhattan distance) to guide the pathfinding algorithm via the use of a priority queue
This makes it one of the faster algorithm, but note that this is because you need to know the position of the end point for the heuristic function
Nodes are expanded in the direction of the end node
The shortest path is always guaranteed

2. Breadth-First Search

Uses a simple FIFO queue so nodes are expanded in every direction equally (searches in a circle outwards from the starting node if maze is empty)
The shortest path is always guaranteed

3. Depth-First Search

Uses a LIFO queue, where nodes are added in order of direction (top, right, bottom then left) from expanded nodes
This means that nodes will always be expanded leftwards until there is a barrier, then down, etc.
Therefore, this is a very inefficient algorithm but it is used because it is the way a human might navigate a maze (left-hand rule)
Does not guarantee the shortest path. In fact, in an open maze this could take very long to finish even if the end node is directly beside the start

4. Dijkstra's Shortest Path First

Nodes will be expanded very similarly to breadth-first search, but it is designed to be able to handle paths of different weights
The main difference is the use of a priority queue
Unfortunately this visualiser only uses weights of 1 between each adjacent node so the changes are not visualisable, but feel free to check out the code in algorithms.py (they're different, I promise!)
This always guarantees the shortest possible path

5. Greedy Best-First Search

Uses the manhattan distance heuristic function like the a* algorithm
However, it does not take into account the distance already travelled and just expands the node with the shortest estimated distance next (hence greedy)
Does not guarantee the shortest path but it often does find the shortest path

The Maze Types:

Random - All nodes have a 25% chance of becoming a barrier node
Swirl - Basic swirl pattern which takes up the entire grid
Imperfect - My first attempt at a proper maze generating algorithm. Called imperfect because very small sections of the maze may be sectioned off from the rest of the maze
Simple - Based off of recursive division but slightly different