2021-03-30

Egregoria Devblog #8

Welcome to the 8th Egregoria devblog!

A lot has happened in the last 3 months. To start with, Egregoria has passed the symbolic (to me, at least) barrier of 1000 commits!
I have poured more hours into this project than all the others combined, and it really feels like I'm becoming a better developer.
Rust really helps, as most of the mistakes I make get caught by the compiler, who's become an architectural teacher.

Multiplayer

That's right! I spent a few days refactoring my code to completely separate the simulation logic from the ui/rendering. Then, I used deterministic lockstep to synchronize the game worlds. That's the method used for Factorio and Anno 1800.

The basic idea is that each client sends commands/inputs over the network i.e. "build a house at this particular lot". The server merges those commands and sends them back. The clients then advance the simulation independently by applying the commands to the game world.
If the simulation is perfectly deterministic, then all clients should end up with the same state.

I went a little further and implemented the "catching up" idea from Factorio:
When a player joins the game. The simple way would be to save the game, send it to them, wait for them to be ready and continue.
However if they have a slow connection this blocks everyone for a potentially long time, especially if the world is big.

Instead, everything is asynchronous. When the player joins, the game is serialized in a few hundreds of milliseconds. Then the world is sent while the other players continue to play, and all the commands are remembered by the server.
When the new player has received the entire world, it starts "catching up", receiving all the commands that has happened since he started downloading the world. Eventually, the server decides the client has catched up enough and starts sending the actual real-time merged inputs.
That's it!

So why did I pick this method if I could instead simulate everything server side and "simply" send the state to the clients?

I have a few reasons.

1. Bandwidth
   I want Egregoria to scale quite a bit, 100 thousand population all having a car, a body, a house. Synchronizing thousands of cars over the network at 50 ticks per second is tough.

   Simply sending position+angle using 32 bits floats is 32*3*100000*50=480 Mb/s = 60Mo/s. Now obviously, compression techniques exists, but the baseline is already very high and that's only the cars!

   Deterministic lockstep consumes almost zero bandwidth. It has a bigger latency but city builders usually don't care about 200ms latency.

2. Complexity
   Deterministic lockstep is quite "simple" in terms of networking code. It relies on tough assumptions like, well, determinism across platforms. But the implementation doesn't require predicting anything, replaying anything and having incredibly optimized netcode with zero copies since the bandwidth is very low.

3. Scalability
   Now that the code is there, I will never have to touch it again when adding new features. The code is generic over the Commands type. I "only" have to keep in mind to keep the simulation deterministic.

4. Free replay system
   A replay system can be based on the same ideas very easily, just remember the inputs and replay it on any machine and there you go! This can be very useful for debugging to know exactly what happened before a crash.

The only problem with deterministic lockstep is obviously desyncs! If one machine goes even a tiny bit differently than another one, thanks to the butterfly effect, the worlds will end up in very different states.
Simple example: At an intersection, even a tiny position/velocity difference can mean that one car will pass and another one will stop. From then on, traffic will be completely different.

Economy and content

The economy I presented in the last post is pretty much implemented! Goods companies have recipes, for example 1 Cereal ↦ 1 Flour, and a number of workers. They ask for workers on the job market which associates people living in houses with them. Theses workers then become either a truck driver or a worker.
When the cereal factory orders cereal from the cereal farm to make flour, the cereal farm asks its truck driver to deliver the cereal it produced to the cereal factory. The bakery then buys that flour and makes bread which gets eaten by the population.

The small circle of life.

Although it did an interesting "bug" at first.
See, workers eat 1 bread per day, but the required amount of work to produce 1 bread was bigger than a day. Therefore they would all get hungry, stopping the production of bread and the population would just never get out of their houses since they couldn't buy bread anywhere.
Dying in essence.
To solve this, I lowered the amount of work required to make 1 bread by a factor of 10, and people went on their merry way.

Since this was working pretty well, I started making a goods dependency graph with goods as edges and factories as node. Like this: I've implemented most of them but they are not balanced at all.
They're also not very organized, just a list in the gui. Hard to understand the links beside reading the recipes.

Gridlock detection works!

The gridlock detection I talked about in the previous blogpost is implemented and works very well!

It worked on first try and solves gridlocks seamlessly. Very simple and elegant algorithm. I love it.

Before:

After:

Game or simulation?

Recently, seeing the recent developments, a few people asked me if Egregoria was a game or a simulation? It makes sense, as after rereading the first post, I noticed I said "Egregoria is not meant to become a video game". That was a year ago, and I changed my point of view about this.
Seeing the recent success of NIMBY Rails and NewCity, I think the indie city-builder scene still has a lot to explore.

Egregoria is a simulation game.
I want to get as far as possible in the simulation aspect, but still give the tools to anyone to make their own world.
I'm always making a tradeoff between good UX/gameplay, good graphics and good simulation.
Having the possibility to jump between the three gives me enough space not to demotivate myself as any of the three can be exhausting after too long.

Infinite world

The world is now infinite! It was fun to poke around the procgen code again. I also had to make the tree generation lazy and chunk-based. So now, trees get generated when you zoom enough or you build somewhere.

The small features

• Cars/Pedestrians now reroute if their path gets broken on the way.
• Map overhaul was done to prevent unexpected crashes. Now most map actions will just log an error instead of stopping the game.
• Parking spots and lots are preserved in a best-effort manner when splitting a road.
• Roofs are now generated using the straight skeleton algorithm applied to the roof contour, reimplemented in Rust.
• See turns at intersections using the road edit tool.
• Added a setting to hold the mouse (and not click) to use the bulldozer.
• Trees get removed by buildings.
• Lot brush now directly places houses.
• Allow inspecting buildings to see what's happening.
• World is now zip compressed.
• Textures get reused.
• The procedural world generation is now much faster using noise textures for the fine details.
• Building to be built gets shown under the mouse.
• Fixed lots of bugs (and introduced a lot of them)
• And probably more I didn't think about

A lot of features don't get talked about in theses blog posts because they are too small to deserve a section. Sometimes I feel like I don't have enough content, that the game is progressing slowly, and that's why!
All theses small things take time especially alone since you have to do everything yourself. :-)

What next ?

I want to get the game to a more "playable" state to be able to do some playtesting. This means strengthening the economy, make sure the game doesn't crash on a whim, polish the serialization, and develop the behavior AI a bit.

I'm also starting to think 3D, as it is really hard to interest people with a 2D interface nowadays. I've been thinking about it for a while, but I didn't have the necessary skills back then.

Thank you for reading to the end!

If you ever want to chat about Egregoria, keep in mind there is a discord server.
You can talk about your ideas, city builders or anything else. It's definitely a source of motivation and helps to steer this project in the right direction.