Programming Blog 15 – Pathfinding Solutions

Hi, it’s Stephanie here and today I’m going to talk about our pathfinding! (It was supposed to be Bean, but he forgot his password!)

The monsters in our game use a custom pathfinding solution to navigate the ship, allowing it to take the dynamic layout of the ship and a multitude of obstacles in to account. The pathfinding can sometimes take a short while to calculate, especially if it is from one side of the ship to the other with lots of twists and corridors in the way. The delay between starting the calculation and getting the path can cause issues with the monster – the monster will be following its old path whilst the new one is being calculated, so when it starts following the new one, the start of the path might not be at the monster’s feet. At best, the monster still lies on the new path. This usually happens during a chase. The worst case scenario is the monster is ‘far away’ from any part of the path, which can happen if the monster goes in one direction and the new path goes in another. We resolved this before by simply assuming the monster couldn’t get too far off the path in the time and making it follow the closest node on the new path. However, we wanted to correct this assumption, to ensure this wouldn’t cause a problem, and to fix the odd occasion the monster would turn around mid-chase when this didn’t quite work.

To explain how we improved this issue, an understanding of the pathfinding process is necessary. The current procedure is as follows:

Find a Path → String-Pull → Improve Path

The first step is to find a path. We are not concerned with this right now. Step 2 can be described in layman’s terms as placing a string along the path from the start to the end, and pulling until it is taut. In code, it actually just removes any nodes where the two nodes on either side can see each other, creating a similar effect. Step 3 is a collection of other algorithms that operate on the path to make it suitable for the monster and make the path better for following.

In order to reduce the problem stated, the game inserts a path back to the start node at the beginning the calculated path, just before the string-pull step. It does this by recording the monster’s position whilst calculating the path, instead of doing actual pathfinding. By inserting the extra path at this point in the process, it piggy-backs off the remaining pathfinding functions and undergoes the same algorithms as the calculated path. This means the string-pulling removes any surplus nodes from the extra path and ensures the path ends up heading in the right direction.

I hope this technique might be useful to someone for solving the same issue!