Preamble

These numbers were generated from the FlyingNavBenchmark project, available on GitHub.

Path Configuration

Theta* Path Overview

Path with Octree Visualisation

All algorithms are CPU based, and were run on an Intel Core i7 4930K @ 3.9GHz in Windows 10. The project was packaged up in a Shipping build, so this should be running optimised code. The octree generation is multithreaded; the pathfinding and raycasting are singlethreaded.

The tables are designed to illustrate the impact of the various optimisation options for pathfinding. Here we test the HeuristicScale, Use Unit Cost and Use Node Compensation options, testing for A*, Lazy Theta* and Theta* algorithms. Details of these can be found in the Usage section. I have also tested the octree raycast algorithm, and compared it to the standard Physics Line Trace.

I have used Time (in milliseconds), Number of Iterations and Distance Proportion to measure performance and accuracy. The pathfinding algorithm explores one node per iteration. The iterations for Theta* and Lazy Theta* take longer than A* due to the line-of-sight check. The distance proportion is a measure of how accurate the path is; these optimisation options take shortcuts and therefore aren't guaranteed to find the shortest path. The benchmark will compare the optimal path (Theta* with no optimisation) to the found path, calculating the value with the formula:

int Distance = (FoundPathLength / OptimalPathLength) * 100%

It should be noted that the time column is not a useful measure for comparisons between tables, as I could not get consistent results between runs. I used FPlatformTime::GetSeconds() for benchmarking the runtime, which calls QueryPerformanceCounter() on Windows (which is apparently accurate), so I don't know why the time fluctuates as it does.
You will notice this by the fact that fewer iterations does not necessarily mean smaller runtime between tables, and theoretically the generation time should be identical. Therefore, I will be using the Iterations counter to compare performance, and the time column should only be used as an estimate.

Pathfinding Benchmarks

Remarks

The test scene was designed to be a worst-case scenario for A* style algorithms, in which most of the search space would need to be explored to complete the path. It should be noted that even on the lowest resolution, a perfectly acceptable path can be found for most flying agents, so it really isn't necessary to crank up the number of layers as much as one might think.

With only bUseUnitCost = true, we see almost a halving in iterations across the board (around 1.6-1.7x better) with a consistent 10% increase in path distance for the any-angle algorithms. It's 20-40% for A*, but I believe this is because the extra steps in the path from the optimisation are not smoothed out by the line-of-sight check. For the 4 layers case, this is pretty much the end of the story. No other optimisations improved on that score.

As the number of layers increase, the other optimisations come into play. With bUseNodeCompensation = true, we get a similar improvement (1.7x) in the 9 layers case, but no improvement with 4 layers. However, when using both options, we get a comfortable one third of the original number of iterations for 9 layers. The middle layers fall proportionally between these examples.

Interestingly, the heuristic scale does not make much of a difference or even hinder the performance when both of these options are turned on, but that could be due to the nature of the test scene. The heuristic is not very useful for most of the path journey, but in real scenes in fairly open spaces the heuristic would come into its own. Complicated mazes such as this don't have as much of a benefit from increasing the heuristic from 1.0.

As you can see, increasing the number of layers drastically increases the pathfinding and generation time. You can get away with this by using asynchronous pathfinding, but this is not supported with behaviour trees at the moment. Check out the Usage page for more information. However, asynchronous processing is still using resources, so a larger max detail size is a better solution.

Raycast Benchmarks

Remarks

The Physics Line Trace obviously doesn't depend on the octree while the raycasting does. The octree raycast is used for the line-of-sight checks in the pathfinding algorithm. I wasn't able to get the raycast time to increase as expected with the layer count, so everything past 5 layers is within the margin of error. It's clear that the algorithm is very efficient, consistently being 3x faster than a physics line trace. It should be noted however that both are very fast and that the Physics Line Trace is more flexible.