A* Pathfinding Algorithm

Engine: Unity 5.6.2

My Role: Everything

Team Size: None

Source Code: Click Here

Description

I implemented my own version of the A* Algorithm in the Unity Engine. I aimed to make it fully work and in a very optimized manner with any agent. This meant as well as creating the complex algorithm, I had to utilize threading and my own custom data structure.

My first Unity game needed a pathfinding system that could work on walls and ceilings and at the time, the Unity Pathfinding Tools did not support this. I had to create my own algorithm for it that is optimized because I needed to implement it in a RTS game. I created the algorithm in Unity since it was a very easy way to test and debug it. After many hours of research and work, I created this slightly different version of the A* Pathfinding Algorithm that can fully work on any surface. The demo video above is shown on a float ground but it works the same way on walls and ceilings if the agents can move in such ways.

The Unity Project that contains source code of my algorithm is in the source code link. Feel free to download it.

Project Technical Aspects

Advanced Algorithm Programming: I created the algorithm from scratch using C# for a fast workflow. I researched the many pathfinding algorithm and how they are used but the A* algorithm was the best solution for what I needed. My version of this algorithm fully works on horizontal and vertical surface and is very optimized by fully utilizing threading and it uses my own custom data structure also created in C#.
Custom Data Structure: The most expensive part of the algorithm is the iterations through all the nodes to find the node with the smallest f-cost. This custom data structure sortes itself everytime a node is added to it and keeps the lowest f-cost node at the top of the heap. The algorithm now only has to remove the first node in the container and the search for it in a large array is no longer needed saving many CPU cycles.
Threading: The calculation of the path is done on a separate thread as to not cause a spike in the performance of the game. It utilizes threading and my own threading manager that deals with mutex and locks shared data to avoid data being accessed by more then one thread. I have used this threading manager in many of my other projects since I initially created it to be reusable. The algorithm class extends from the threading class to allow for its functionality and automatic management of asynchronous processing.