So I’ve been watching your past broadcasts on twitch and I noticed you guys used the A* pathfinder. I was wondering if you guys had considered modifying your A* pathfinder to use JPS. JPS(Jump Point Search) speeds up the pathfinder by pruning out the chunks/squares it doesn’t need to check effectively “jumping” over them improving performance by orders of magnitude over the default A* pathfinder. 
4 Likes
Doesn’t default JPS not allow for different weights needed for, say, roads? That said, I’ve heard that there are ways to modify JPS for that.
1 Like
Well a lot of people SAY it isn’t good for weights but I don’t see why. All you would have to do would be to modify the code to consider the weighted blocks. Yes, it would slow down the pathfinder BUT it would still be faster than A*
1 Like
They’ve actually developed a solution like that for use in alpha 12. See Desktop Tuesday: Pathfinder II, Terms of Enspeedment for details.
In this sytem they calculate the pathfinding grid whenever the world changes (and very quickly) so that it can be used by all the AI in the game simultaneously. So the optimisation is done once per state of the world and flows through to all the AI as a result. With JPS, there is an optimisation, but you have to do it for each AI and for each path you try and find, so the overheads are much higher overall.
Also, the stonehearth system can handle weighted blocks.
2 Likes
They’ll implement binary space partitioning into the algorithm to speed up pathfinding. Read more here: Binary space partitioning - Wikipedia
2 Likes