As the world of Empires and Trips grows, the demands on background algorithms become more complex. The pathfinding algorithm, for example, determines the shortest path of a unit from point A to point B. The more units on the road in the world, the more search queries there are and the higher the computing effort. Until now, path calculation has been solved using the classical A* algorithm. Advantage: relatively straightforward programming (good for me). Disadvantage: with longer paths the algorithm consumes more and more computing time. Simply put, A* calculates all the most promising routes to reach your goal.
From the starting point, it moves forward in small steps towards the goal, bypasses obstacles, compares all possibilities to reach the goal and looks for the shortest way out. With the length of the path, however, the possibilities to reach the goal increase immeasurably and thus also the computing power. This is where a relatively new approach of the so-called jump point search, or JPS+, comes into play. A wonderful explanation by Steve Rabin on the subject can be found here: https://www.gdcvault.com/play/1022094/JPS-Over-100x-Faster-than The JPS+ algorithm searches for the most likely routes to the destination just like A*, but also uses the possibility to skip certain routes.
For example, if we want to cross a large free area, we don't have to calculate every single point, but can jump straight from point A to point B, because we know that the area is free. Well, we know that... That is the crux of the system. The crucial point for JPS+ is to calculate the environment in advance and save all parameters such as obstacles, distances to the next obstacle, etc.. Sounds great in the idea, but the problem is that we can't change the environment dynamically. But that's exactly what we need in Empires and Tribes when we build a new wall, for example. So I spent the last few weeks writing an update function for JPS+ to do all the necessary precalculations in the fastest possible time. Whew! 10-20ms needs the update now, but I think that should be acceptable. After I have done a few re-calculations, I hope that I will be able to present a stress test of the system in the next update.