Path Finding Visualisation using A* Algorithm

Jul 24, 2020
·
3 min read
Featured Image

Personal Project - The goal of undertaking this project was 3 prong. (1) Apply my knowledge in A* Path Finding algorithm,(2) Structure the code with Object Oriented Programming(OOP) technique and (3) Document the process with software architecture design.

The project was built with Python and utilised the Python package PyGame to build the visualisation.

A Star Visualisation Screenshot Screenshot of the A Star Path Finding Algorithm Program Project

Table of Contents:

  1. A* Path Search Algorithm Overview
  2. Usage
  3. Viewing
  4. Files in this Repository
  5. Lessons Learnt and Conclusion
  6. Acknowledgment
.

1. A* Path Search Algorithm Overview

This subsection intends to give a high level overview of the concept of the A* Path Search Algorithm. The goal of the aims A* Path Search Algorithm is to find a path to the given goal node having the smallest cost (least distance travelled, shortest time, etc.).

The visualisation is built with Python using the PyGame package for the generation of the visuals.

The algorithm is made up of two functions: f(n) = g(n) + h(n)
  • Cost Function, g(n)
    • Calculates the cost of the path from the start node to n.
  • Heuristic Function, h(n)
    • Estimates the cost of the cheapest path from n to the goal. In this project, we use Manhattan distance which takes the absolute value of the horizontal and vertical distance between the current and end node.
Wikipedia has an excellent representation of the function of the code through pseudocode linked here.

The image below is the diagramatic flow of how the main function triggers the different functions within the source code(Named: aStarPathFindingAlgo.py). The main(WIN, WIDTH) is the container function which procedurely calls upon the different functions for the algorithm and visualisation to run.
A Star Visualisation Screenshot A* Path Finding Algorithm Diagram Flow
.

2. Usage

The A* Path Search Algorithm Visualisation in this project uses a square grid.
  1. Declare the Start, use the left mouse button to click on desired start node(Orange Block)
  2. Declare the End, use the left mouse button to click on desired end node(Sky Blue Block)
  3. Declare the Barriers, use the left mouse button to click/drag the desired nodes to be the barrier
  4. Start Path Finding Algo, hit space bar button on keyboard
  5. Reset Grid, hit "c" key on keyboard
.

3. Viewing

  • The best way to view this project is to download the source code of the project and run the Python script using Python 3.7.7
  • An alternative way to view this project is through an online Python Shell. Link here, press the run button on the top of the webpage.
.

4. Files in this Repository

  • aStarPathFindingAlgo.py - Source Code for the A* Path Finding Visualisation
.

5. Lessons Learnt and Conclusion

  • Object Oriented Programming (OOP)
    • Having a hands-on experience seeing how objects are interacted through this personal project.
  • PyGame
    • Learning a new Python package which I thought I would never find a use.
  • Software Architecture Design
    • Using LucidCharts web app to design a architecture design with inspiration from UML standards. I believe this new knowledge is essential for project documentaion when referring back in the future.
.

6. Acknowledgment