Hi everyone–it’s Chris again (aka “Scaffold ALL the things”). Stephanie has graciously turned over Desktop Tuesday to me this week — and so of course, I’m going to do a little dive into our new building system that just landed in Alpha 17. If you’ve ever wondered about the deep connections between scaffolding in Stonehearth, and biological protein folding (and really, who hasn’t?) then this article might just be for you.
Stonehearth is pretty unique as city-building games go, as we give you the tools to construct pretty much any kind of voxel-based structure you might imagine, but then delegate the actual building of that structure to your hearthlings — you design, they build, brick-by-brick. Actually figuring out how to build an arbitrary structure in a physically plausible-looking way is a complex problem that, to be blunt, we here at Team Stonehearth have underestimated for a long time. Our new design represents a pretty fundamental re-thinking of the way we do building.
At its core, constructing a building is about making sure hearthlings have access to the places where new blocks are needed. Making sure they have access to those places is all about scaffolding. Thus, building is about scaffolding–where do we place it, and when? The old system was an extremely “optimistic” design, that tried to place scaffolding only when it was time to build that part of the structure. This “just-in-time” placement worked fine for relatively simple structures, but quickly fell on its face when presented with more complex designs.
For example, the above structure could easily confound the old system. If hearthlings happened to build the two outer walls first, the inner wall would have no place for scaffolding to go, and thus would not build. After working on various approaches to the problem for a while, it became clear that we needed an ahead-of-time scaffolding system–in other words, hearthlings need a plan to figure out where and in what order to place the various pieces of scaffolding they need to finish the building.
For an ahead-of-time solution to work, we need to build a dependency graph of the building. This is basically like a big blueprint that says “in order to build the roof, you first need to build the walls. But, in order to build the walls, you first need to build the floor.” It’s a giant ordering of all the structures that the building needs to have built, and the order in which to build them. Some of the ordering comes from the relationships between the objects: roofs sit on walls, so the walls must come first. That roof-on-wall relationship is a spatial relationship. These are pretty easy to calculate.
Once we have the basic spatial shape of the graph, we then go to figure out where to put scaffolding. For each part of the building, we try to place scaffolding around it, in order to ensure that each part can be reached by hearthlings (and therefore built). We look at the area surrounding the building part, and see if it is clear of any structures, so that we can place scaffolding there. If we can, great! We’re done with the structure, and we move on to the next part. Generally, though, something is there–either in the way of the scaffolding, or something that the scaffolding needs to sit on. This is where things get interesting.
In both of those cases, we have to update our dependency graph. If the scaffolding is going to sit on a piece of the building, then we need to make sure that that piece of the building is built first; this means that we need the current part to depend on that other part, so that when we go to build the scaffolding, that part is already there. In the case where the scaffolding is in the way of that other building part, we try to make sure that we get built first, and that our scaffolding is torn down before that other part gets built, so that we aren’t in the way anymore. This again requires updating the dependency graph to ensure that we are a dependency of that other part (and thus get built first), as well as ensuring that our scaffolding gets torn down enough not to be in the way of that other part–our scaffolding is an anti-dependency of that part.
Like I wrote: interesting.
You’ll notice this a lot in the new system: hearthlings build up scaffolding, build a structure, and then tear-down parts of the scaffolding to make way for other structures. Planning for the future isn’t just for fiscally-responsible humans….
All this dependency-graph stuff comes with a very big caveat: you must never add a dependency that creates a cycle. A cycle is like a Catch-22 for graphs, and they are Very Bad. It would be like saying “you can’t build the floor until you’re done the stairs, but you can’t build the stairs until you’re done the floor.” Neither the floor nor the stairs could ever be built, and that means unbuildable buildings.
Sometimes, we find that no matter what, we can’t find a place to put scaffolding without introducing a cycle. In these rare cases, we cheat 🙂 Once that part of the building is ready to build, we just *POOF* pop it into existence. You have to be watching closely to notice this happen, and as I wrote, it is rare, but right now it’s the best way to deal with very complex structures.
You might be wondering, why is this so hard? Humans can put up scaffolding just fine for the buildings we make, what makes this such a difficult problem for computers to handle? The real trick is to find a “nice” traversal of our building graph; that is, one that doesn’t result in any unbuildable structures. A naive algorithm (try every possible traversal!) is exponential in the size of the graph: you might have to wait many millions of years to find an optimal traversal for even a modestly-sized building. As it turns out, trying to ensure that our building graph is both “nice” and free of those dreaded cycles is an NP-Complete problem. This is a fascinating topic for computer scientists to discuss, but perhaps a little out of the depth for this little article. Suffice it to say, a simple graph-based approach that is also efficient is likely impossible. I suspect that more thinking about the geometry of the building will lead to better and better graph traversals, in turn leading to completely buildable dependency graphs; this will be an ongoing exploration for myself.
So, is building done? Not even close! Many, many more buildings now build (most should, in fact), but there are lots of bugs to clean up (hearthlings can get themselves trapped in enclosed spaces, for example), and of course, more UX improvements to add. Expect more fixes and improvements to building as we continue to develop Stonehearth.
Join Us For Our 200th Twitch Stream!
As previously noted, our stream schedule this week is a bit different. There is no stream today (Tuesday); Allie will be on at the usual time Wednesday (8.30 am Pacific).
And then… (insert drumroll here) it’s our 200th Twitch stream on Thursday!
Join Team Stonehearth for the big celebration Thursday at 5 pm Pacific (please note the earlier start time) on twitch.tv/stonehearth
We’ll be showing off some awesome community builds and mods (seriously, you’ll want to see these), take a walk down memory lane with early Alphas, dive deep into the Art and Music of Stonehearth, take a look at what’s next… and (as always) answer your questions. We’ll save time for one or two surprises as well!
Finally, there will be NO streams at all the week of July 25 as the entire team will be away at a company conference. We’ll be back with Stream 201 on Tuesday, August 2… and Chris will be joining us on stream that week! So start saving all your building questions for him….