Navmesh Pathfinding
During the first year at TGA, we were given a optional assignment to create a pathfinding algorithm that caught my interest. Most games are depended on this and so were our upcoming game projects. This was simply a must have for me!
Pathfinding 1.0
- TGE (school's engine)
After doing some reading about the Funnel Algoritm I did my own take on it. During the implementation process and debugging I got really tired of trying to locate where things went wrong. Adding text with ID's on triangles and indices helped me to keep track of where the algorithm failed.
After getting it to work I wanted to see it how it would look visually, so I added some debug lines with delay to visualize how the algoritm worked it's way thru the navmesh. The result is shown in the video!
Pathfinding 2.0
- Kitty Engine (own)
Later in our Game projects we used Navmesh exported from Unity with more complex triangulation than shown in the previous video.
My algorithm was clearly not ready for this and after some debugging I realized that my implementation had to many edge-case saves. Whenever I fixed one failure from point A to B, another failure appeared from A to C.
The hard part about String pulling algorithms is that it has to work everywhere. If it fails in one place, there's gonna be more and if it fails it will probably be game breaking which we cannot have!
This led me to think of new ways to do the implementation and after all it evolved in a complete new algorithm that worked very well!
The result is shown in the video, where the character handles increased triangulation complexity!
Optimization
The problem
Having a few characters in a small test scene running the algorithm was all fine. But when we had 100+ characters on a huge game level, all running the algorithm every frame it clearly became an issue.
This led me to profile the algorithm to determine were I could gain performance and the results were quite obvious.
The algorithm went thru every single triangle on the Navmesh to determine our start and target triangle.
The Solution
In order to drastically reduce the number of triangles to go thru, I implemented a 2D Grid where each cell held a list of pointers to the triangles overlapping the cell.
The performance gain was immense!
Pathfinding 3.0
- Kitty Engine (own)
The algorithm I had at this point generated a path in 2D space, (as if you looked on the level from above).
The height position of each character was then calculated separately every frame to handle slopes.
I felt like this was not "user-friendly", having to manage height on the side and I was also curious if there was "another way". Ultimately, I wanted my algorithm to generate 3D positions. The Pathfinder should solve the whole Navigation Puzzle!
In order to handle height, I knew that the algorithm had to generate waypoints on every triangle edge shared between two triangles, all the way from start to target position. Shown in the video!
This led me to add more calculations to an already quite complex algorithm which was harder than I thought.
Though this was only used by our Player and not our AI's due to other requirements in their movement behaviours.
In the end I learned a whole lot from all this and I still have more to explore within the topic!
