AI Pathfinding Overhaul

Pathfinding problem in math is almost 100 years old, so you'd expect everything related to it to be perfected by now. Indeed, there are dozens of very efficient algorithms for finding the shortest path from A to B, but what if you don't need the shortest one?

Octohill is a ski resort simulator where my NPCs do enjoy the ride, so they should take longer routes and small detours to get the satisfaction they're looking for. While this sounds like a small addition, this actually makes the problem NP-hard (meaning that's impossible to solve it fast unlike the shortest path thing). These detours are called negative cycles in graph theory and are a real pain to deal with.

My initial approach was to ignore the problem and try to use the classical algorithms hoping it would work, and up to some moment it did (that's how the game version 0.2 makes the pathfinding, or what is still used for vehicles as in the cover image):

But when the ski resort gets big enough AI starts to make some very stupid decisions because of the good (cyclic) paths not being considered, so in the end I've decided to do a major rework.

After some experiments with making this algorithms more complex I realised a fundamental truth: real people don't test millions of paths analyzing all the mountain surface in their head when they decide which piste to try next. They only quickly check the high level touristy trails map (often inaccurate...) and what's right ahead of them.

Now I'm using a more natural approach:

1. Parts of the map are grouped into trails, split by lifts and big crossroads (the green color on the screenshot above is the end of the current trail)
2.  All the (short) possible paths between these trails are tried to find the best one. The computation is limited by 10 trails so for them brute force approach is not a problem
3. Only within the current trail a detailed algorithm is used (as there's no negative cycles inside) which decides specific tiles of interest and paths to them inside the trail

As a result, a resort with about 800 skiers on slopes runs on x5 speed without any delays and the flow looks quite natural without them getting lost. The new pathfinding will be a part of the next major Octohill update which is coming soon, together with the dynamical construction.