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).

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)

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 : 

• The development of a Graphical User Interface (GUI) to select parameters at program launch.

• The integration of the value of the boxes and the implementation of the Dijkstra algorithm.

• The ability to select multiple start and end boxes.

Skills developed during this project