Internal affairs 1: The Structure of a Structure

An introduction

The reasons for doing an early access release of a game like Trailmakers are of course many and varied, but a primary one is that it provides the opportunity to get qualified feedback from actual users through personal interaction and discussions. The vision is clear: Receiving detailed feedback sufficiently early in the development process will allow developers to act on it and modify various aspects of the game to better suit the actual usage patterns of players. While the vision remains clear though, reality rarely conforms to such clarity, and feedback is often ambiguous and even self-contradictory - while one user enjoys simplicity and argues simplification, another enjoys the freedom in complexity and argues the opposite. Hence such feedback needs to be aggregated and quantified (and such operations need to take into consideration that the early access users may not be statistically representative of the players who would buy and enjoy the end-product) to be usable in practice, which unavoidably and regrettably results in the loss of much of the personal interaction of the original vision.

Considering these deliberations I guess is only natural for an early access developer like myself to be perusing our forums and lurking on discord (some might even say obsessively so). While I may not be able to provide statistically significant data, I can at least form my own impression on which way the winds of the community opinions are blowing - partly in order to relay these impressions at the office and partly to see if there’s any input on areas which are of particular interest to myself and my own work. 

Having done so over the past months I have one pressing matter that I want to express to all of you: Thank you! Trailmakers is currently gathering a very helpful, welcoming and dedicated community. Following discussions is almost always a pleasant experience, and seeing the contraptions being shared is the source of endless amazement to me and my colleagues - more than a few have been downloaded and reverse engineered, simply because we, the developers, had to know how the blazes you’d achieved it. I honestly applaud you, thank you and hope that you keep up being such a nice and dedicated crowd!

During these pleasant excursions I've come to realize something else that is somewhat surprising to me (though in retrospect I don't know why I didn't expect it): There's a rather substantial minority of the vocal part of the early access community who is expressing technical curiosity as to how we solve this or that particular problem in the game, some of you even going so far as to suggest possible solutions or ways to improve the existing implementation - and in extreme cases decompiling and reverse engineering the Trailmakers assemblies. It is very tempting to enter such discussions and more than once I've been on the verge of doing so, but I decided not to for two main reasons. Firstly being a developer means that most people tend to assume that whatever you say is the official standpoint of the company, meaning that you have to choose your words very carefully to not say anything that could be construed a promise without being absolutely certain you can fulfill it - which somewhat hampers your abilities to join a free an open discussion - and secondly because the format of chat messages and even forum posts lends itself badly to the purposes of long technical discussions, especially since in this particular case they would at first be mostly unidirectional. If we are to satisfy the flattering curiosity being exhibited and have fruitful technical discussions, we must perforce start out with a long-read to relay the necessary information about the architecture of Trailmakers which would form the basis of such discussions.

Mulling this over, the solution is really rather obvious: We, the developers, should, are obliged to even, do write ups on the different areas in which interest is expressed. Depending on the wishes from the community this nascent "Internal Affairs" series is an attempt at providing such information on your chosen topics - though the manner of choosing further topics still remains to be decided. Nevertheless the topic of the first article is straightforward in many ways; it's the foundation upon which Trailmakers is built, the core of the system, and the topic which I've most often seen people asking about. It's about structures and welding.

 

The Basics

It should come as no surprise to anyone who’s managed to read this far without falling asleep, that the basic entity, the core and the essence of Trailmakers is the Block. From the very start of development we have been very conscious of what properties we want a block to possess: it's simple and somewhat small, it's atomic and it's strictly limited to at most one functionality. We want every block to be easily recognizable and reasoned about: A player should be able to tell at a glance which block it is and what it does just by looking at an image of it.

All blocks are equipped with what we call connection knobs. These knobs are always placed in a grid on the outward faces of the block and allow the player to combine several blocks into a coherent group. Though all blocks are individually simple and have a limited number of connection knobs, the number if possible permutations over them is almost infinite and provides the gameplay with that most elusive of features: complexity through simplicity. The result of the process of combining blocks into larger entities is what we refer to as a structure or a contraption.

 

The Abstraction

And now we’re finally getting to the interesting part. Considering the amount of possible permutations and combinations of blocks we need a good way to model it to allow a computer to work with the structure in a timely manner. This model - or abstraction - should capture the essence of what the user has created while skipping over all the (to the computer) unimportant little details. In our structural abstraction each block is represented by a node containing all relevant information about the block in question, and whenever two blocks share one or more connection knobs, their respective nodes are connected with an edge. The result is what is commonly referred to in mathematics as a graph - a well-understood and thoroughly researched data structure allowing us to use common algorithms to traverse and do calculations pertaining to the structure.

In order to debug and reason about this graph we’ve created an internal tool to visualize it. The following image is a screendump of the structure graph for the tutorial vehicle - it’s a simple enough structure with only a handful of nodes and edges, but as you can see, 3D representations quickly grow complicated - for reference I’ve included the visualization of the graph of a random complex structure I’ve pulled from our Discord channel.

 Figure 1 - The Structure Graph of the Tutorial Vehicle This simple graph consists of 12 nodes and 11 edges. Each node is depicted by a little dot which grows smaller towards the extremities of the structure while the edges are drawn as lines between the nodes.  

Figure 1 - The Structure Graph of the Tutorial Vehicle
This simple graph consists of 12 nodes and 11 edges. Each node is depicted by a little dot which grows smaller towards the extremities of the structure while the edges are drawn as lines between the nodes.
 

 Figure 2 - An Imperial Walker by Kronogenics As can be seen the graph grows rather complicated at an alarming rate, but even so having the graph makes it a lot easier to reason about such complex structures - this one has more than two hundred blocks.  

Figure 2 - An Imperial Walker by Kronogenics
As can be seen the graph grows rather complicated at an alarming rate, but even so having the graph makes it a lot easier to reason about such complex structures - this one has more than two hundred blocks.
 

driving

Now once the building is done, the player will certainly want to pilot his new contraption experiencing it in all of its physical glory - and this is where things get really complicated. Trailmakers uses the PhysX engine for physics simulation which means that the structure will have to be converted into rigid bodies for the physics engine to cope with, but we want to keep the amount of rigid bodies to a minimum to ease the load on the CPU, and - just as importantly if not more so - to lower the network bandwidth requirements during multiplayer sessions. On the other hand, rigid bodies are exactly that: Rigid. If we use too few of them the glorious new contraption will invariantly end up feeling like it’s made up of one big piece of cardboard instead of being a heavy, massive, impressive thing.

In other words, we need to find a way of grouping together several blocks which can be simulated together as a single rigid body, without the loss of physics fidelity in the resulting structure. The basic problem we need to solve here is to divide the structure graph into groups according to a set of constraints: 

  1. No group should be too small (neither in extents, weight or amount of blocks)
  2. Neither should any group be too large (neither in extents, weight or amount of blocks)
  3. No two groups should differ in size with more than certain factor - 5 to be precise
  4. Two parts able to move independently of each other should be grouped separately
  5. Symmetry needs to be maintained

To expand upon each item: The first constraint is the one we’ve already covered - we want to keep the load on the CPU and the network as light as possible and hence our groups should not be too small. The second constraint has to do with the danger of a cardboard boxy feel - if we make any group too large it will start to feel too rigid and the immersive physical feel is in danger of being lost. The third constraint is a limitation of the PhysX engine itself - if rigid bodies vary too greatly in weight, the physics solvers grow unstable and things like hinges and suspensions start behaving very weirdly. The fourth constraint is quite natural - since rigid bodies are rigid, movable parts need to be kept in seperate groups. And then there’s the fifth one - this one snuck up on us and ended up being both the most difficult and quite possibly the most important of them all. When you build something symmetrical (which you tend to do 9 times out of 10) you want it to be physically symmetrical as well. Even if you make small variations in the symmetry, like equipping you newly crafted robot with a gun in one hand and a club in the other, you expect the symmetry in the body to be reflected in the physics.

Identifying the optimal grouping of the graph is what we refer to as welding, and we’ve developed an algorithm which weighs all of these different constraints against each other and finds the optimal solution. This implies pattern recognition (to identify partial symmetries around various axises) as well as a set of graph algorithmic techniques to identify optimal groupings weighed according to the constraints.

The process of welding is therefore highly CPU intensive and is something we’ve been working on continuously since we’ve started the project, and we probably will never be completely done - it’s always possible to refine and optimize it further. 

One point worthy of note is the interaction of the third and fourth constraint. Moving parts needs to be welded separately but no two groups should vary in size. Well what if, God forbid, the player went and did something crazy like attaching only one block to the end of a hinge? That one block will perforce need to be in it’s own weld group which may then be significantly smaller than the one at the other side of the hinge… you know like the front wheels of the tutorial car.

This particular problem is one we’ve been fighting a constant battle with over the past year - and the current solution leaves something to be desired. After welding is done we do some “mass redistribution” in order to make sure that the result matches the third constraint above. This entails taking some the weight that belongs in the big weldgroup and moving it to the small one, thereby making that one heavier than it really ought to be. This makes the physics behave a lot more nicely, but it does have its side effects. I imagine that even now some of you are leaning back wide-eyed thinking “so THAT’S why that small gokart wheel at the right side of my helicopter threw of the balance so much”. Believe me, you much prefer those drawbacks to the physics we get without mass redistribution, but we still hope to be able to mitigate the side effects somewhat down the line.

 

Examples

The astute reader (observer in this case) will have noticed that the structure graphs printed above are color coded. The colors are actually visualizations of the chosen welding of the structure - all nodes and edges of a particular color are grouped together in the same weld group, while grey edges represent connections between the weld groups themselves - these are the ones that are actually physically represented and simulated. There are also some very special red edges, most often seen in hinges, which are block internal structure edges. I won’t be going into those here as this article is already growing out of hand, but for the purposes of the topics covered here they can be regarded like the grey edges in that they are physically simulated as well.

 Figure 3 - The Flail A classic build, the flail is a rather fun albeit somewhat useless construction. It is constructed by attaching long chains of trailer hinges to form a sort of rope. As can be seen, this forces the welding algorithm to divide the graph into very small groups, which has a significant negative impact on CPU and bandwidth costs.

Figure 3 - The Flail
A classic build, the flail is a rather fun albeit somewhat useless construction. It is constructed by attaching long chains of trailer hinges to form a sort of rope. As can be seen, this forces the welding algorithm to divide the graph into very small groups, which has a significant negative impact on CPU and bandwidth costs.

 Figure 4 - Grocery Cart by Poof (Beefy Weefies) This shopping cart has no moving parts and less than 60 small blocks. The welding algorithm decided that a single weldgroup would be enough for this structure which goes to show that it sometimes may be a bit to aggressive in its choices - two or three groups would probably have resulted in a nice physics feel while having little impact on performance.

Figure 4 - Grocery Cart by Poof (Beefy Weefies)
This shopping cart has no moving parts and less than 60 small blocks. The welding algorithm decided that a single weldgroup would be enough for this structure which goes to show that it sometimes may be a bit to aggressive in its choices - two or three groups would probably have resulted in a nice physics feel while having little impact on performance.

 Figure 5 - The Centurion by ThatOneRandomFox Contrary to the cart on Figure 4, this vehicle has been divided into a myriad of different groups and may turn out to be harder on the CPU than you might expect. The amount of suspensions and extent of the vehicle are the two main factors contributing to the fragmented welding result.

Figure 5 - The Centurion by ThatOneRandomFox
Contrary to the cart on Figure 4, this vehicle has been divided into a myriad of different groups and may turn out to be harder on the CPU than you might expect. The amount of suspensions and extent of the vehicle are the two main factors contributing to the fragmented welding result.

 Figure 6 - Trailmakers man by Ohirunetannpopo This one really takes the welding algorithm through its paces as the Trailmakers man has some symmetries but is asymmetrical in the details. As depicted the algorithm has successfully detected the large scale symmetries and welded accordingly - I’ll leave it as an exercise for the reader to find the other symmetries in there.

Figure 6 - Trailmakers man by Ohirunetannpopo
This one really takes the welding algorithm through its paces as the Trailmakers man has some symmetries but is asymmetrical in the details. As depicted the algorithm has successfully detected the large scale symmetries and welded accordingly - I’ll leave it as an exercise for the reader to find the other symmetries in there.

Destruction

Every game has a gameplay loop for trapping the players (oops, was that an industry secret?), and you’re probably already familiar with the one in Trailmakers: Build it! Drive it! Smash it! (Repeat). The player, having built his ingenious contraption and driven it around for a while will invariably take it to the limits of its capabilities and end up smashing it to smithereens. You shouldn’t feel bad - it really and truly is part of our core game design so it’s hardly your fault. However, in order for Trailmakers to successfully close the game loop, crashing must be an enjoyable experience and it ought to be informational to boot. The latter means that whenever you smash a structure, you should be able to “read” the chaos that ensues and glean information about where the weak points in your structure are. And this means physics. The final problem we’re now facing is of our own making: We’ve carefully welded the structure into larger components which to the physics system are atomic because of performance considerations - but to the player every block should be separable from the rest. If a rock hits the tip of the wing of your plane you expect only the tip to break of, not the entire wing and half the fuselage as well.

In order to solve this we have an internal damage system which kicks in whenever an impact occurs and distributes damage in the structure graph. The physics engine provides us with the force and point of impact and this allows us to do sub-weldgroup damage propagation through our own system and when enough damage has accumulated within a certain timeframe something breaks inside the weld group. This can have a lot of effects but for the purpose of this article it means one thing: We have to recalculate the welding, possibly create new structures from the remains of the old one and reinitialize the physics system with the new reality.

Obviously this is quite expensive to do while running the rest of the game as well, but luckily and just as obviously corners can be cut. Most of the original welding will probably still be valid and should be reused in such cases and only weld groups which have actually changed needs to be recreated, but still, crashing is hard on the CPU. This is why you often experience “lag” in multiplayer whenever somebody crashes - the server is doing a lot of calculations and lags a bit behind.

This particular area is something we’re currently actively working on, and I think I can say that this, at least, will get better as development progresses.

 

Take Aways (TL;DR)

Alright, you’ve made it thus far, so what’s in it for you? Well, now that you know something about the inner workings of the structures and the welding system, you can use that knowledge to build better and more efficient contraptions. You know about the mass ratio problem which induces mass redistribution which in turn may make your construction behave unexpectedly - now you know why and are at least better equipped to handle it. You know about the moving parts being largely unweldable meaning that lots of those degrades the performance of the system - and you know a bit about why. You know that even though welding is employed, the structure can still break into its constituent blocks, and you know this process is expensive due to welding. So impress your friends the next time the game stutters by yelling, not “I HATE LAG” like the rest, but instead “WHO JUST CRASHED, REPAIRED OR EXITED BUILD MODE?”. Bets are, somebody did. And while you’re yelling that, rest assured that we are constantly working hard to improve welding, remove the stutters and improve all of the other parts of the game as well!

  • Trailmakers employs welding - the grouping of individual blocks into co-simulated groups - for increased network and CPU performance

  • Due to constraints in the physics system weld-groups are mass-redistributed which may throw off the balance of a structure

  • Welding must adhere to certain constraints which means that the particular configurations of blocks can lessen or nullify up its efficiency

  • Generally speaking, moving parts like hinges, suspensions and pistons, forces the hands of the welding algorithm

  • To build optimally performance-wise avoid having long chains of such moving parts

  • Even though the structures are welded while driving them, they can still break apart into their original constituents - i.e., down to block level. Only the blocks are truly atomic.

Welding_Infographic_v03.png
rune dittmer