idle2

Desktop Tuesday: Idle Musings

If you’ve played Stonehearth long enough, you have no doubt run into what we’ve come to term “The Idle Hearthling” problem.

Even though there’s lots and lots of work to do in your settlement, your hearthlings just seem to stare out into space: they won’t work, they won’t eat, sometimes they won’t even sleep!  They just gaze emptily and sometimes wander around.  The Idle Hearthling problem usually doesn’t kick in until you’ve acquired a number of additional citizens to your town.  It can be extremely frustrating, and fixing the Idle Hearthling problem is by far our biggest priority right now.

It turns out the more powerful your computer, the less susceptible it is to running into the problem.  If you have a very meager i3 computer; you may hit it as soon as 11 or 12 hearthlings.  Those of you with a super beefy i7 may not hit it until 30 hearthlings or more, if ever!  This is really good news: it means the Idle Hearthling bug is almost entirely a performance problem, and that fixing it is just a matter of making the game run more efficiently.  Furthermore, one maxim in software development is to avoid premature optimization.  In a nutshell, this basically means that you should not focus too much on optimizing the performance of your program early in its development lifetime.  There’s lots of room to speed up Stonehearth, and we’re well on our way to making some big strides in Alpha 12 and beyond.

Measuring Performance

One of the last things we did before polishing off Alpha 1 was to add a performance monitor to the game.  The performance monitor is displayed in the bottom right corner of the UI.  It shows which parts of the game are using the most amount of your CPU at a given time.  The bars are color coded.  You can get a breakdown of what each bar means and the exact percentage of your CPU dedicated to teach task by clicking the bar.

yellowAndBlue

If you’re running into the Idle Hearthling problem, your bar is probably either entirely yellow, entirely blue, or a combination of both.  The yellow represents the time spent pathfinding, and blue is time spent running Lua code.  After extensive profiling, we’ve determined that most of the time spent in Lua is in the AI code.  Since these are (by far) the biggest CPU hogs in the game, we have the most to gain by focusing on making those two parts of the system go faster. So that’s where we’re focusing.

Pathfinder Performance

The pathfinder is the part of the system which figures out how to get from one place to another.  It’s used extensively by everything in the system which needs to move around: hearthlings, goblins — even fluffy, cuddly rabbits use the pathfinder to navigate the world.  At any given time, there may be 50 or 100 pathfinders simultaneously all trying to navigate their way around the world, so the pathfinding code is written in C++ for maximum speed.

The pathfinder in Alpha 11 basically the A* algorithm navigating a navigation grid.  To find a path from one point to another, the algorithm steps voxel by voxel vaguely in the direction of destination using a heuristic (a “best guess”) of the right direction to step at any one time.  This is actually really fast, but has quite a few downsides.  The biggest, by far, is that it may take many, many steps to find a path when the geometry of the world gets complex.  This is one of the reasons why building many complicated (usually custom) structures increases the likelihood of encountering the Idle Hearthling problem.  If you’ve ever had a game that was going pretty well, except no one was working on roofs, this is probably why!

To help speed up the pathfinder, we will very soon be switching to a navigation mesh instead of a grid.  We will still use A*, but instead of stepping voxel-by-voxel the pathfinder will step in big, meaty chunks.  In most cases, we estimate the pathfinder will eat up ground between 5 and over 200 times faster than previous one, which should dramatically improve performance!

Constructing a navigation mesh in real time in a highly dynamic world like Stonehearth is a really hard problem, and Chris has been hard at work on it for several months.  We are almost finished with it though, and a beta-version has been checked into Alpha 12 on the Steam unstable branch.  You can switch from the old pathfinder to the new by setting the simulation.use_subspace_pathfinder key in your user_settings.json file to true.  Be warned! There are still a few bugs that we’re working out with the new pathfinder, so turning it on might lead to unexpected results.  We hope to have all of the bugs squashed in time to turn on the new pathfinder for the Alpha 12 release.  If not by then, then certainly by Alpha 13.

AI Performance

AI performance is a trickier problem, as the goalposts keep moving.  As we add features to the game, design decisions which seemed perfectly reasonable at the time are suddenly no longer appropriate to solve the problem at hand.  This is by no means unique to Stonehearth: all software projects encounter this problem to some degree.  The biggest problem we ran into for Stonehearth, however, revolves around the issue of storage.

stuffEverywhere

Through Alpha 10, the only way players had to organize their town was the stockpile.  Unfortunately, the poor stockpile just wasn’t holding up from either an organizational or gameplay perspective.  Towns with lots of stockpiles ended looking like hoarder camps, and there was rarely enough space on the ground to actually store all the stuff your crafters and farmers were generating.  Advanced players were even building multi-level storage facilities so they could stack their stockpiles vertically (clever!).

Having only stockpiles as a storage solution was clearly not enough, so in Alpha 11 we introduced small and large chests.  These greatly increased both the density that the player could store resources (win!) and made towns look much much nicer (double win!), but they put a lot more stress on the AI system.  When the AI started to get too overloaded, players would often see what we dubbed the Hearthling OCD problem:  the AI had just enough CPU to find resources which needed to be put into crates, but not enough to actually find a place to put them off in.  Players would routinely see their hearthlings fill their backpacks with items that needed to be stored, only to put them all back on the ground seconds later.  It was maddening!

idleHearthlings

I’m happy to report that we’ve changed the way restocking happens in Alpha 12 to be much more efficient, so you shouldn’t see that behavior anymore  (hooray!).

We also spent quite a bit of time looking at where the AI system was slow.   It turns out that there are a handful of pieces of the AI infrastructure that were taking up almost all the CPU time.  Furthermore, these pieces had almost nothing to do with gameplay: they basically represent a hearthling’s brainstem and spinal column: not responsible for higher-order intelligence, but critical parts of nervous system nonetheless.  For the past few months, I’ve been working on re-writing those parts of the AI system in C++ to greatly speed them up.  The parts responsible for higher-order thinking, prioritization, etc. will still be written in Lua, but these generally don’t use as much CPU as the parts being re-written in C++.  The payoff is that the AI system should get much faster without sacrificing anything in terms of moddability.

The AI to C++ rewrite (codename: cppai) is also checked into Alpha 12 on the unstable branch, and is also off by default until we can do more internal testing.  If you’d like to kick the tires, you can manually set the mods.stonehearth.enable_cpp_ai flag to true in your user_settings.json.  Like the new pathfinder, cppai should be turned on by default in Alpha 12 or 13.

One last thing.

Sometimes even when your hearthlings are not idle, they’re still not exactly doing exactly what you want.  For example, if there are towers to be built and wood to be put into a stockpile, which would you like to have done first?  Usually this is a matter of taste (personally, I can’t stand seeing stuff outside stockpiles, so I’d like everyone to clean up please!), or priority (if the goblins are coming, you might want to finish those city walls!).  Either way, the AI system can’t always automatically pick the “right thing” for everyone’s playstyle.

Our solution, which probably won’t come till Alpha 13, is to give you very coarse-grained control over what your hearthlings are doing at any given time. Here’s a sneak peek at what’s in store:

 

work_orders_screenshot

(Cool, eh?)

Finally, thanks to everyone who has shared their save files with us and helped us to diagnose better exactly what was going on. Your assistance has been invaluable.

And hang in there — winter relief is coming. Upgrades to pathfinding and AI are both on the horizon. You can expect to see Alpha 12 later this month!