Pathfinding Performance
NOTE: The content of this article has been reworked completely in April 2024. A lot has changed. The TL;DR: JPS is now the recommended choice for 4-directional movements since it's performance has been increased significantly. It has been removed for 8-directional movements though, since the old version was not giving correct results and the new one is by far the slowest option.
Pathfinding is expensive. Therefore it can quickly cause performance issues. In Grid Engine, every time you are calling findShortestPath, moveTo, or follow, pathfinding will be triggered. In the case of follow, it will even be triggered every time the target moves!
So the first advice is not to use it thoughtless. However, there are more things you can do to improve performance for pathfinding in Grid Engine.
Ignore character layers
Character layers can significantly increase the map size for pathfinding. Only adding a single char layer can double the size of your map. So if you don't need pathfinding to explore different character layers, you can (and should) tell Grid Engine by setting ignoreLayers: [1], [2], [3].
The algorithm will then only consider the character layer of the start position.
Pick the right algorithm
There are currently 4 different pathfinding algorithms that you can use in Grid Engine: Breadth First Search (BFS), Bidirectional Search, A* and Jump Point Search (JPS).
At the beginning, only BFS was supported. Then came Bidirectional Search and then A* and JPS.
So which one should you choose?
If there was a simple answer to this question there would only be a single supported algorithm and that would be chosen by default. However, depending on the structure and size of your map and your paths, each of these algorithms could be the best choice. But that does not mean that there can be no guidance in picking the right algorithm.
If you need path weights/costs (see tile costs), you have to use A*. The other algorithms are not capable of dealing with tile costs. However, if you do not need tile costs A* might not be your first choice due to slower performance.
If you need pathfinding for path widths/heights or characters with a tile height/width of more than 1, you can't use JPS.
I would recommend JPS for most of you, because it has the best results in the benchmarks I ran (for more details on that, check out the benchmark section below). Just keep in mind that you have the flexibility to change the algorithm to see if it works better in your case.
Activate caching
Since version 2.28.0, Grid Engine offers the possibility to activate cacheTileCollisions tile collision cache for pathfinding. It takes advantage of the fact, that tile collisions do not change very often in many cases. Many games do have a tile map that stays more or less the same and only characters move frequently. If you need to change something, you can still update the cache locally using rebuildTileCollisionCache.
If you find yourself frequently updating the cache for the whole map, you might be better off with a disabled cache (or you try to change your logic, so that you don't have to frequently update the cache in the first place).
PathBlockedStrategy and NoPathFoundStrategy
When using moveTo, you can determine what happens if no path was found or the path is suddenly blocked while walking it.
By default, these are set to STOP and WAIT. These settings are already optimal for avoiding unnecessary pathfindings. Just be aware that if you change these settings, there might be additional pathfindings that can slow down your game.
Benchmarks
I chose some benchmarks that are frequently used in research for pathfinding on grids. As you can see in the following plots, the results vary quite a bit depending on the benchmark. The reason is the different structure of the maps. For each benchmark I have plotted the average runtimes of the different algorithms, grouped by the path length. Because the path length can get quite large and many games only contain smaller maps, I have additionaly provided a "zoomed in" version of each plot, which shows only results for path lengths up to 100.
There is one section for 4 direction (up, down, left, right) pathfinding and one for 8 directions.
The absolute runtimes depend on the machine and the browser. More important are the runtimes of the algorithms relative to each other.
The results can be found in the Benchmark Results section.
Conclusion
4 Directions
Even though it is not the fastest in each case, JPS seems to be the best choice overall.
BFS and Bidirectional search are also giving acceptable performance. Especially in mazes with a very small corridor size, they are unbeatable (that is because there are almost no path-symmetries that JPS could leverage). So if you have mazes with corridor sizes of 1 or 2, you should consider whether BFS or Bidirectional Search are better choices than JPS.
It is surprising though, that Bidirectional Search seems to underperform BFS in most cases. It is probably due to its specific implementation in Grid Engine.
A* seems to be quite good on small paths. However, it becomes unacceptably slow for large ones. So JPS seems to be superior to A* in almost every case.
8 Directions
JPS has such a bad performance for 8 directions, that I strongly discourage using it. It remains an open question if the bad performance is due to the implementation in Grid Engine or if the algorithm is generally not performing well on 8 directions with partial obstacles. You should go with BFS or Bidirectional Search if you don't need path weights.