Progress Update 2018-01-07

Just stopping by for my usual update. Haven’t got back into things yet but I did a little work on and off over the break.

The topic of the moment is still pathfinding. I’ve made some progress to minimise the amount of turning in paths and also to allow units to move close to a destination they can’t reach, rather than just crashing the game in that scenario. However, to minimise turning I added orientation to the search space and this has significantly increased the number of vertices the pathfinder needs to search through. This makes the pathfinder unacceptably slow in the worst case (when the destination is far or unreachable).

To solve this, I will likely replace the current implementation with a form of jump point search (JPS). JPS is essentially a more intelligent successor selection mechanism for traditional A* on a uniform grid that makes use of properties of the grid to cut down the number of vertices that must be visited. Visiting fewer vertices means that the search goes faster. JPS relies on the grid being largely uniform, i.e. made up of the same kinds of cells. The grid in RWE only has three types of cell – free, near obstacle/rough terrain, and blocked – so jump point search should work well here. Another useful property of JPS is that the paths it generates tend to be reasonably straight, so we can avoid too much turning without needing to explicitly consider turning or orientation in the pathfinder.

Here is a useful resource if you would like to know more:

https://zerowidth.com/2013/05/05/jump-point-search-explained.html