Hello and welcome to another openage devlog. This month, we have introduced a few more pathfinder updates that make it work better with the game simulation. We are now getting to the point where the pathfinding looks and performs okay enough that we can include it in the next release version!

Propagating Line-of-sight through Portals

As described in our April devlog, the pathfinder uses line-of-sight (LOS) optimization to improve pathing close to the target cell. To put it simply: When a cell on the grid is flagged as LOS,
there exists a direct (non-obstructed) path from this cell to the target. In practice, this means that any game entity at the position of this cell can move to the target position in a straight line. This makes pathing look much more natural and smooth. If we would only use the direction vectors of the flow field right until the end, we would be limited to their eight possible directions.

In our initial implementation, LOS optimization was confined to the target sector, i.e., cells outside the target sector were never flagged as LOS. However, this meant that a lot of paths that could have been a straight line but crossed a sector boundary looked noticeably weird. Instead of bee-lining straight towards the target when there are no obstructions, game entities would have to move to the edge of the target sector first
before they would reach an LOS cell:





You can almost see where the sector boundary is as the game entity is turning very sharply towards the target as it reaches the first LOS-flagged cell in the target sector.

This behavior has been fixed by propagating the LOS integration through sector portals. Essentially, LOS flags are passed from one side of the portal (in the entry sector) to the other (in the exit sector). LOS integration then continues in the exit sector using the passed LOS-flagged
cells as the starting point. As a result, paths look much better when they cross multiple sectors:





Optimizing Field Generation

The topic of performance came up in a Reddit comment before, so we thought it might be interesting to pick it up again. Performance is a big factor in the feasibility of flow fields since pathfinding should not stall gameplay operations. Flow fields do have some benefits for the quality of paths, but the added complexity can come with a hefty performance price tag. Thus, we have to ensure that the pathfinding is still as performant as possible.

Over the last month, we have applied several optimization strategies:

Simplified Code

We removed a lot of redundant code from the design phase of the pathfinder. This includes things like redundant sanity checks, debug code, or flags that were only relevant for the pathfinding demos that you've seen in our monthly devlogs.

CPU-friendly datastructures

To increase throughput for field generation on the CPU, we replaced most occurrences of data structures that are known to be slow (e.g. std::unordered_map, std::deque, std::unordered_set) with vectorized data types (std::vector and std::array). These data types utilize the CPU's L1-L3 caches much better, which means that the CPU has to spend less time fetching data from RAM and has more
time for running calculations.

Flow Field Caching

Generated flow fields are now cached and reused for subsequent path requests if possible. In practice, caching can be done for all flow fields on the high-level path where the target is a portal cell (i.e., any sector that is not the target sector). Since field generation is deterministic, building two flow fields with the same target cell results in them being equal. Therefore, if a high-level path uses the same portal as a previous
path request, the previously generated flow field can be reused. The overall result of our optimizations is that pathfinding is now about 2x-4x faster than in our first iteration. Technically, there are no benchmarks yet, so you have to trust our numbers for now. On our test machines, a path request can take between 0.3ms and 2ms for paths of roughly the same length, depending on the number of fields that have to be built and how many obstructions there are per sector. Flow field and integration field generation in the low-level pathfinding stage is now so fast that the A* calculations of the high-level pathfinder are becoming the bottleneck with ~50% runtime usage.

What's next?

That was definitely enough pathfinding for a while. There is probably still a lot to improve, but other parts of the engine need attention, too.

Next month, we will focus more on game entity interactions. That means we will make them do things to each other, like damage or healing or whatever we can think about that's fun (and not too complicated).