http://stonehearth.net/desktop-tuesday-pathfinder-ii-terms-of-enspeedment/
awesomely nerdy glimpse into the pathfinder! 
What we do is we create this subspace representation from the grid-representation using a process known as Binary Space Partitioning, and then we pathfind using those subspaces. This allows A* to easily consider every grid space within a subspace simultaneously, without having to examine each, one-by-one.
4 Likes
this was a very pleasing read for me.
indeed!
2 Likes
Well, it looks like Stonehearth is locked into terraced landscapes now.
This still could probably handle more gradual cliff edges and small stretches of smoother biomes, though, and I’m excited for performance increases. Plus, I’m fine with the terraced style anyways. Good job Team Radiant!
2 Likes
How is the deformation of the terrain dealt with in the BSP? I wouldn’t expect you to be rerunning that code every 30 seconds as once you hit a certain threshold of subspaces it’s going to start taking much longer.
Current Stonehearth maps don’t have a lot of terrain variation, which is why this works well. However, a player can easily make the map end up looking like a white noise map, where you effectively end up with every single grid space being it’s own subspace and you’re back at where you started. It’s not likely to happen, but just saying it could.
4 Likes
Warp engines are easy. Now, reading Klingon… that’s hard.
3 Likes
I was actually pretty worried about this (the speed of the grid-to-subspace decomposition step), especially when lots of Hearthlings are mutating the world by building structures, roads, digging, etc. As it turns out, the cost is really quite small! Barely shows up on the profiler, at least in the tests I’ve done. Worst case, I still have a couple of tricks up my sleeve to make sure this is nice and fast 
Even then, the new pathfinder ought to beat the old one (the old one considered a lot of empty/filled nodes that the new one can process at once). That said, yeah, this is a worst case, but one we’re really not likely to run into.
6 Likes
While I’m glad they’re going to optimize where they can, I’m not sure what they really can do about more complicated terrain. Pathfinding algorithms is not an area of programming I have much experience with, but it’s a very intensive problem usually.
1 Like
And i’m thinking what you guys have is the best overall as well…I mean i’m not a pathfinding guru but what you guys have made sounds like a good overall solution to me! There will always be fringe cases but even then you’ve gotta try to find the best overall solution to make the high end of the bell curve happy!
There can always be “enhancements” made to the core engine 
3 Likes
Cool stuff! Can’t wait for the implementation! GJ to all involved 