Sep 11, 2023

CD 038: v0.5.5, Update 2 teasers, and Techtonica

Captain of Industry - Captain Zuff

Ahoy everyone, Captain Marek speaking, and today I've got some exciting news to share about Update 2 as well as info about the patch v0.5.5 that just landed! But wait, there's more – let me introduce you to Techtonica!

Techtonica + COI bundle

Techto-what? Well, we've teamed up with the folks at Fire Hose Games, the devs behind the recently released title called Techtonica. This game isn't your ordinary factory sim; it's a first-person factory automation full of caverns, machines, conveyor belts, and fully destructible 3D terrain! Plus, there's a good dose of exploration to spice things up.

And here's the best part – we’ve made a discount bundle so that you can get both games at 12% discount! If you're already the proud owner of COI, you can snag Techtonica with this discount through this bundle too. I personally took Techtonica for a spin shortly after its release, and let me tell you, it's fun! So consider giving it a try.

https://store.steampowered.com/bundle/34792/Techtonica__Captain_of_Industry

What’s coming in Update 2

Next, let me show you some new things coming in Update 2. And to give credit where credit is due, these are mostly made by Jeremy, so you know to whom you can address your praises or further requests :)

Custom surfaces

It’s coming ladies and gentlemen, custom surfaces, so that your new steel or nuclear plant does not have to be on a grass field! For now, we have a custom concrete mostly working, but we plan to add more visuals so that you will be able to customize your factory visuals to your liking.

The new concrete surface feature won’t be just visual. We plan to lower vehicles’ maintenance and fuel consumption while they are driving on reinforced ground.

Balancers on pillars

Another feature coming in Update 2 is balancers on pillars. You will be able to build elevated balancers and sorters that are supported by the same pillars as transports. This should simplify the branching and sorting of elevated transport lines. You can also notice that pillars can now be attached to balancers from the top.

Terrain dust particles

In Update 2, every terrain change will emit dust particles, making the terrain mining, dumping, and collapsing more realistic and visually appealing. It’s a relatively small change but it adds a lot to the overall immersion (and helps to hide sudden terrain changes a little).

Patch v0.5.5

We’ve just released patch v0.5.5 and there are some changes I’d like to briefly talk about.

One-line change resulting in 4x terrain physics speedup

Yes, we’ve identified a one-line change that led to 4x terrain physics speedup which resulted in ~30% sim speedup when terrain physics is active. Here it is:

Before

After

public readonly struct Tile2i { [FieldOffset(0)] public readonly int X; [FieldOffset(4)] public readonly int Y; [FieldOffset(0)] public readonly ulong XyPacked; ... public override int GetHashCode() { return XyPacked.GetHashCode(); } }

The next part will get a little technical but let me decipher the code for you. The `Tile2i` is a simple structure for a 2D tile coordinate that has 32-bit X and Y coordinates. We also have a 64-bit field that overlaps the X and Y data so that operations like equality can test one 64-bit value instead of two 32 bit values.

Memory layout of the Tile2i struct.

The `GetHashCode` method is used when a tile is a key in a hash table. I won’t spend much time explaining hash tables here but the gist is that anything can be efficiently looked-up in a hash table using a “hash code” that is some value that represents the underlying data. In C#, hash code is a 32-bit integer so we just called `XyPacked.GetHashCode()` that does the job of figuring out hash code for 64 bit data for us.

One thing you should know is that a hash table organizes values in an array indexed by the hash code (modulo the table size), so when two values have the same hash, it’s called a “collision” and the hash table stores all collided values in a linear list inside of a bucket for the respective hash. So with many collisions, fast lookups turn into slow linear searches.

You probably see where I am going with this. The old implementation caused a lot of collisions. The C# implementation of `GetHashCode` for 64-bit ulong is just XOR of the first 32 bits with the last 32 bits, so that’s identical to `X ^ Y` (the ^ symbol is bitwise XOR). So why were there so many collisions? Let me demonstrate this in an example.

Imagine we’d like to store 100 unique Tile2i values in a hash table of size 100. These values will be all possible coordinates in a rectangle from (1,1) to (10, 10). The first hash can be computed as `(X XOR Y) MOD 100`, here is the resulting table of hashes:

Table of hash values using the `(X xor Y) MOD 100` function, X coordinates are rows and Y coordinates are columns.

As you can see, all of our hash values are in the 0-15 range. This means that we are squeezing 100 values into 16 buckets. For example, the hash 0 has 10 occurrences, hash 3 has 8 occurrences. That’s way too many collisions and the majority of the 100 element hash-table is not even used!

Let’s look at the improved hash function that makes 32-bit hash code by combining 16 bits from X and 16 bits from Y: `(X xor (Y << 16)) MOD 100` (the “<<” is a left bit-shift). When use this function we get:

Table of hash values using the `X xor (Y << 16) MOD 100` function, X coordinates are rows and Y coordinates are columns.

Now look at that! Fairly even spread of numbers between 0 and 99. There are still some collisions, for example hash 45 and 46 appear twice, but that’s totally acceptable and expected. Note that X and Y coordinates in COI are never larger than 16 bits so this new hash function will actually produce a unique hash for every possible coordinate (hash collisions can still happen due to the modulo operation).

So how did we get speedup from this? We store lots of things in hash tables with `Tile2i` as a key. For example, we saw 4x speedup of terrain physics which updates various things on terrain movement. Another example is the data structure keeping track of the tile on which each tree is placed". Overall this resulted in ~30% reduction of sim time.

To prevent issues like this in the future, we are planning to implement some automated detection of excessive hash table collisions so that we can have a piece of mind that there are no more cases like this one ever again.

Transport path-finder improvements

The final thing I’d like to mention today is how we improved transport path-finder’s responsiveness. Transport path-finder is the piece of code that searches for the shortest path for your conveyors and pipes, so given a start and goal, it performs the shortest path search.

Jeremy had this genius idea that when the goal is not selected yet, for example when start was just selected, there are usually a few frames before the player moves the mouse to a new location and we could still do some search in this period.

You might ask, what path could we search for when we don’t know where to go? The answer is simple, just explore all existing paths and keep track of what we saw. When the player’s cursor finally moves and it selects an already explored position, we can instantly present the shortest path to that point! And thanks to the heavy caching, lots of progress is preserved even when the mouse continues to move.

And this is all for today’s post. If you have any questions or comments, let us know on Discord or Steam!

We are hiring!

Still here? Did reading about hash tables and path finding did not make you close this tab? Great, we are hiring! We are looking for a software engineer with specialization for UI & UX. If you or someone you know fits the open position, please get in touch! See details here https://www.captain-of-industry.com/jobs

Full changelog for v0.5.5

Transport path-finder now performs an undirected search when there is no goal set yet, improving response time once mouse cursor moves and goal is set.
Improved internal hashing algorithm for tiles resulting in 4x speedup of terrain physics and around 30% overall simulation speedup when mining/dumping is active.
Slightly reduced font sharpness to make the text more readable.
Trucks with cargo are no longer reported as idle in the vehicles overview.
Paused mine tower no longer affects dumpable products in its area of influence.
Recipe book now shows recipes with mechanical power and other virtual products.
Results of in-game calculations via the search bar are now shown at the left side of the entities menu.
Fixed a rare issue with (auto)save which was not able to be completed in some cases.
Fixed ship fuel checking when navigating to some locations.
Fixed minor rendering issues of some buildings caused by the latest optimizations.