DT: Pathfinder Optimizations

Hey everyone! This week, the team continues to power through A21 features. As usual, this includes work on both gameplay items like new traits for your hearthlings, as well as ongoing features aimed at improving usability and performance. One of these is Chris’s brand new Topology Service, which enables the game to keep track of regions that are accessible to each other. This produces giant performance improvements for the pathfinder, and dramatically cuts down on lag and stuttering produced by wandering monsters and stuck hearthlings.

Pathfinder Optimizations

Recap from the video:

  • So, how many of you have ever completely walled off your town, and then had a bunch of monsters spawn outside? Or asked your hearthlings to pick up loot that is for some reason, now inaccessible?
  • Eventually, both of these situations lead to massive game slowdowns and stuttering, especially in combination with a lot of mining and building.
  • Each moving entity–hearthling, monster, etc–in the game has some A* pathfinder code associated with it. When an entity has a goal, like running in to investigate your town or challenge your knights or take all your stuff, that pathfinder code searches the world for a way in. The larger and more complex the world is, the more time this search takes up on your CPU, because it has to check all the possibilities before it can assure itself that there’s no way to get there right now.
  • If the hearthlings cannot get onto a plateau/pit/etc that contains a restockable item, their pathfinders still use CPU as they try to find a way to that item. You can see this in the astar section of the CPU performance bar in the lower right coner of the screen.
  • Every time I add a log to the plateau, all the pathfinders run again, even though the new log is right beside the old log that they should already know they can’t get to.
  • Worse yet, once the pathfinders have exhausted their search, your CPU goes back to normal–for a little while. But the world of Stonehearth is deformable: adding a ladder or mining a block of terrain might in fact, suddenly create a path between two inaccessible regions.
  • Pathfinders on entities wait for changes to the terrain, and then all run again. If we didn’t do this, there would be a chance that a path does open up, but you would just see your hearthlings stand around doing nothing.
  • So in Alpha 20, if you have a bunch of outstanding pathfinders waiting for a path to get to an inaccessible log, and you build a large building or mine a region, those pathfinders run over and over and over again, ever single time the terrain changes, bringing your game to its knees.
  • In Alpha 21, Chris has written a new topology service to solve this exact issue. As the pathfinders run, he calculates which regions are accessible to which other regions. Each of these regions is then assigned a color.
  • In the example in the video, this cliff area would be calculated as inaccessible to all the hearthlings who have embarked in this plain down here. When any subsequent pathfinder runs, it checks to see if the target location is in the same color area as the entity that is trying to run there. If it is not, the pathfinder doesn’t even run at all, saving your CPU a ton of time, and making your game much less laggy.
  • When I drop more logs, the pathfinder doesn’t run at all. When the terrain is deformed, or when we build ladders, this coloring is updated. Though this update can still happen quite often, it only happens once per deformation, instead of once per-deformation for every hearthling and monster and pet with a pathfinder.
  • In short: less random and horrible stuttering in situations where objects are inaccessible, and in builds with lots of complex buildings!

Other Announcements

There will NOT be a stream this Thursday, 2/16 as the team is traveling down to LA to give a Stonehearth update to the rest of Riot Games. We’ve made a lot of good progress this year, so we’re really looking forward to showing them all the things we’ve made together with you. 🙂

There’s a bunch of other personal and work-related travel coming up for all of us, so here’s the DT and stream schedule for the next few weeks:

Week of 2/13 – No stream on Thursday, 2/16.
Week of 2/20 and 2/27 – No Desktop Tuesdays, but streams should happen on Thursday 2/23, and 3/2
Week of 3/6 – Neither Desktop Tuesday nor Stream, as the team is heading to Boston for PAX East
Week of 3/13 – No Desktop Tuesday, but stream should happen as usual on 3/16

With any luck, DT and streams should resume as usual on the week of 3/20.