Welcome to my portfolio site. Feel free the take a look around.

A* Path Finding Algorithm

Desktop Applications May 2013

Recently I have been looking through some old work I did during my time at college (while undertaking my HND in Computer Science). I came across an assignment that I completed as part of a software engineering module within the course, whereby we have to implement the A* path finding algorithm using C++. At the time, this was a very difficult challenge for me, as I was new to C++. I remember being very proud of the work back then and I’m still proud now, so I decided to publish it to my online portfolio. Below is a section taken from the report I submitted as part of this assignment.

The A* algorithm is a path finding algorithm which is used to calculate the shortest path between two nodes. It requires the terrain to be split into blocks. Once this has been done, each block can be assigned 3 different values. These are known as G, H and F.

The G value is assigned depending on the move from the parent block. For example, if you have to move diagonally from the parent block then the G score will be 14, however if you move horizontally from the parent block then it will be 10. The H score is an estimate of the distance from the current node to the goal node. This calculation does not take into account walls and other inaccessible areas. The F value is simply the addition of the G and H valves. Using these values the system is able to correctly locate the shortest path.

This application is to be implemented using objects and classes as well as making use of the linked list data structure as a means of storing the required information about each of the nodes.

This content has been taken from the assessment documentation created as part of this module.

This was part of my Computer Vision and Robotics module for year 4 for my Masters of Computing (MCOMP) degree with The University of Lincoln. If you would like a copy any documentation (including the corresponding report), then please contact me using the facilities on this website.

 

Gallery

Browse portfolio

Client

  • Lincoln College

Skills