Pathfinding visualization

Project done on my free time to develop my programming skills

I did this project to improve my understanding of shortest path algorithms in graphs as well as my object-oriented programming skills.

The graph is represented here by a grid of boxes containing randomly distributed obstacles where the user chooses the starting box as well as the ending box.

The user can choose between the A-star algorithm (A*) and the Breadth-First Search.

The advantage of the A-star algorithm is its speed. However, the choice of its heuristic is crucial.

For example, in some cases, it may lose time in a maze, or against an obstacle that could simply be bypassed.


The advantage of the Breadth-First Search (BFS) algorithm is that it does not risk losing time in a dead end.

However, the algorithm consumes more memory and further away the goal is, the longer time it will take.

The choice was made to use the BFS rather than Dijkstra, because the designed grid is an unweighted graph. This means that all cells are at equal distance from each other, and therefore the information of interest is the neighborhood of each cell.

In the basic program, the neighbors of each square are: the square on the left (x-1, y); the square on the right (x+1, y); the square on the top (x, y-1) and the square on the bottom (x, y+1).

Breadth-First Search

A Star

In order to improve the computation time, the user also has the choice to include the neighbors located on the diagonal of each cell. (x-1, y-1) ; (x+1, y-1) ; (x-1, y+1) ; (x+1, y+1)

Breadth-First Search

A Star

CONCLUSION


This project allowed me to improve my knowledge of graph traversal algorithms as well as object-oriented programming with the Python language, while realizing a project that was as fun as it was interesting. 

The current parameters allow you to choose the size of the window, the size of the grid, the location of the start and finish box, the number of obstacles to be randomly distributed as well as the A* algorithm or the BFS.

Future improvements are : 

Skills developed during this project


Python programming using libraries: Numpy, Pygame, Collections (for pathfinding) et Time.

Pygame was used to display the project.

Object Oriented Programming by creating the classes: Main, Window, Grid and Case.