Hello everyone, Chris here! Most of the team is still recovering from the recent EVO competition, or chasing down Alpha 11 bugs, so that means I get to talk about some nitty-gritty details in Stonehearth, and showcase some pretty big performance improvements coming for Alpha 12. In particular, we’re gonna delve into the pathfinder, so hold on to your hats (unless you don’t have a hat, in which case, feel free to hold on to your head, but do try to not look silly).
If you’re not familiar with what pathfinding is, it is simply the technique of finding a path between two different locations in some kind of environment. I would also strongly encourage you to play with this really sweet demo. It’s a great demonstration of a couple of different pathfinding algorithms (Stonehearth uses A*).
The pathfinder currently being used by Stonehearth is fairly traditional. The world of Stonehearth consists of a giant grid (much like the demo above), with each space in the grid being either ‘occupied’ or ‘empty’. Our pathfinder uses this information to figure out paths around the world, from one grid location to another. Now, the major complication in this is that the number of grid spaces in the entire world is actually rather big. We’re talking hundreds of millions of them–too many to hold in memory at once. The way we’ve chosen to solve this problem is to break up the world into bigger groups of grid spaces: we call these ‘tiles’. We then store the terrain in a compact geometric form, only convert it from this form into the grid-structure when that tile is needed, and only do this when the pathfinder actually needs to know whether a particular grid space is occupied or not. In this way, we keep the amount of memory relatively low (because we don’t need to keep the entire grid world in memory), but still get the benefits of having this grid structure. Here’s a picture of one of our tiles–the blue border is the border for the tile; blue grid spaces are standable!)
There’s a big problem with this, though: we still do our pathfinding with these individual grid spaces, and as I said, there are a LOT of them–so many, in fact, that pathfinding over long distances quickly becomes an exercise in patience.
What’s a programmer to do? Well, we notice something fairly obvious: many grid spaces are just rectangular stretches, any of which a Hearthling could equivalently stand on; indeed, many entire tiles are just flat, standable plains. Wouldn’t it be nice if we could just treat all of those individual spaces as one giant space, instead of dealing with them one-by-one? Yes, yes it would!
Presenting: The Subspace Pathfinder!
Here’s a schematic of one of our tiles, looking at it from the top. The black-and-grey boxes represent occupied grid spaces–Hearthlings can’t stand inside them. But those big colorful regions with the gray borders? Each of those is a subspace: a subspace is a big rectangular blob of unoccupied tiles, and is bordered by other subspaces (or nothing at all–occupied spaces do not form a subspace).
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.
Okay, bottom line: how much faster is this than the current pathfinder? Well, here’s a little trek I took a Hearthling on:
I dropped some wood at the finish, and the Hearthling had to find a path from the stockpile, up two ladders, going back-and-forth across the steppes. In my testing, with the new pathfinder, the Hearthling managed to find a path in under a second. With the old pathfinder…well, I gave up on waiting after two minutes…. So, yeah: it’s a hair faster 🙂
Look for the new-and-improved pathfinder (along with some bonus bugs, I’m sure :P) in Alpha 12!
Tom and Tony are out of town on a much needed post-EVO family vacation, so we are cancelling Tony’s 8:30am PST stream on Wednesday, July 22nd, 2015. However, we will continue to stream on Tuesday (that’s today) and Thursday of this week, at our usual 6:00pm PST. The streams will likely focus on modding, continuing the “getting started” trend from a few weeks ago. If you’ve never modded before, but are interested, you can find the startermod from that stream on our public github account here.