DevUpdate #3: A world of lootable items.

Hello again!

Join the Discord! to follow updates as they happen and be part of the community.

Technical Update!

Over 50 000 networked, placeable, lootable, destroyable items spread out throughout the game world.

In Peasant simulator, the world will be filled with interactive items. Not only that, but players will be able to place and customize their spaces, potentially creating thousands of props in their villages. This is a technical post that is going to explain how I pulled this off.

These changes will underpin all of the gathering, building, and networking systems throughout Peasant Simulator.

This post is going to have a lot of jargon in it, so I apologize in advance.

Gathering from the world

How hard can cutting a down a tree or picking up an item be, really? You just look at the thing, left click, and either you loot the apple or the tree falls down ... Can't be that hard right? Wrong. Follow along if you wanna find out why.

Problem A - The Internet

You will often hear people comment that making a multiplayer game is hard, and they arn't wrong.

In Peasant simulator, the game world will be littered with interactable items. Players will be able to level forests, pick wild foliage, and place items all throughout their environment in a myriad of ways.

This means a lot of information needs to be sent (replicated) over the network to and from varying computers.

But if you try and replicate a lot of information at once, you hit a hard limit brick wall, and Unreal will crash the program. It does this for the sake of the rest of the gameplay not falling apart, so its a good thing, but if want to replicate a LOT of things to a player, it represents a problem.

Divide and conquer

If you and a friend host a new game and make a bunch of changes to the world, via editing, building, looting, etc, everything is fine. Even for many hours.

But eventually a new player will connect (referred to as a Late Join), and the server will try and tell them about the game world. It is at this point that this bit of assembly code will say hi:

And if you're in the editor, you'll be greeted by this red text:

Congratulations. You just crashed the server.

We can't send it all at once - we have a hard limit of 65536 bytes per packet. If we cant send it all at once, we send it in chunks - Chunked Replication, and it looks something like this:

The Algorithm

1. The player attempts to place an item into the world
2. The game asks the ItemEdits system if any player has ever edited this area before.
3. If no, the system creates an "Edit Chunk", and remembers it
4. The system then stores the edit inside of the this "Edit Chunk", but only if the Edit Chunk doesn't already have too many edits inside of it (otherwise we would defeat the purpose of this whole approach). So, only store an edit if there are <512 existing edits in the chunk, and if not? We create a new chunk and insert them there.
5. Later, the system determines which chunks a connected player needs to know about (whichever ones are close to the edit in the game world.)

   Problem B - What does it mean to be "close"?

   Determining which chunk is closest to a location, in a sea of chunks, is potentially very costly. We cant just check each one, so we need a way of cutting the data set down to a smaller subset of ones more relevant to the problem ... oh would you look at that its our old friend Divide and Conquer again.
   1. Whenever a chunk is created, we snap (quantize) its location to a grid. Like a big checkerboard across the game world.
   2. We then insert the chunk AND this location into a "Spatial Acceleration Structure", known as a "Spatial Hashmap" (other structures exist and they all have their pros and cons, but Spatial Hashmaps are fast enough, and very easy to write.)
   3. Whenever we wish to determine if a chunk is close to a given location (like where you wish to drop an item for example), we take that location, Quantize it to the grid, and ask the Spatial Hashmap if there are any associated with that location. There may be many.
   4. We now iterate over these chunks, and check their changes, finding the one that matches the location we're trying to edit.

6. Once we know which chunks that player needs, we serialize the chunks into binary, ensuring that we always stay below a total serialized amount of 65535 bytes. If we get close to going over 65535, we halt. We will handle the rest later.
   
7. At this point, the system has correctly determined, in this frame, the maximum amount of edits it can hand to a client, for this specific location, without crashing the server! Yay!
   

Problem C - Rendering

Whoever invented geometry sucks.

When dealing with potentially thousands of interactive items in the world, rendering becomes a significant bottleneck on both CPU and GPU resources.

Luckily in Unreal 5, we have access to Nanite which will significantly mitigate a lot of the costs associated with drawing the triangles of the items to the screen. So I leverage that, which mitigates most of the problems (while creating some other problems of its own). But Nanite doesn't magically solve everything.

The naive approach of creating an individual actor for every tree, rock, or placed item would be catastrophically expensive, even with Nanite, and this mistake gets made a lot. Unreal has many "Per Object costs" (non technical term I just made up) associated with rendering things actor by actor. It could probably do it at or slightly below 60 frames per second, but ideally I would like more.

I approach the problem the same way I do with Chunked Replication - but with Chunked Rendering.

The other Algorithm

1. When Item Edit Chunks replicate down to our machine, we send a "Root Position" for the chunk also.
2. If no "Item Edit Renderer" is near that location, we create one. This will be a new actor, and we pay some costs here.
3. We then iterate all of the individual Edits stored within the Item Edit Chunk, and create a new "Render Instance" for that edit, and begin drawing them to the screen using Unreals Instanced Static Mesh components. In the standard rendering path Instanced Static Meshes can be slower then Unreals specialized Hierarchically Instanced Static Mesh components, but because we're using Nanite it can shortcut the need for the HISM component, and render its specific ISM component which is much faster then both.
4. Tadaa! We just received an "Item Edit" from the server

If you do this right, you can have A LOT of "things" in your multiplayer world:

Over 50 000 networked items spread out throughout the game world.

These things, in the final game, will be things like mushrooms, sticks, piles of hay, firewood, animal droppings, corpses, flesh, dropped equipment, etc. I will generalize this too to include things like building elements, furniture, etc.

Divide and conquer continued

You may have noticed that we solved all three problems in basically the exact same way. Divide the problem into some smaller set of problems, and see if solutions can attack these smaller portions directly.

Pretty much every video game ever made hinges on this concept. Rendering, Physics, Networking, everything. Its a rather elegant way that almost always tends to effectively break larger problems down into more manageable problems that the computer can crunch. Not always, but most of the time.

Final thoughts

There are many different ways that many games will attack this problem. This solution works for mine , but who knows, one day it might change again. Whatever code the game needs is what it will get.

Community!

A few people with access to the game were instrumental in helping me test and find the varying crashes and bugs associated with building this system. Thank you for your time. As always the link to the discord is here:
Join the Discord!.

Changelist

f8d7c0 - Making a big start on world replicated items scaling system
362d64 - Added module to spawn high performance items into the game world
a9f3bc - Refactoring item changes
a5afb6 - Tidying up some code around the item edits
41f3b8 - Fixing bugs
c7ce21 - Bunch of checks because items are null at the moment
17593b - Adding an item edits subsystem actor to handle map-wide item edits
9a674d - Added helper function to get terrain height at point
4c2b58 - Modified engine modules to access terrain heightfield content
163bb3 - Changes to item replication code
a74509 - Major breakthrough with item rendering code
8dd9d1 - Game world spawns with 50,000 meat
958458 - Pushing changes because items now actually compile
4005b7 - ITS ALIVE!
89d9cd - Currently have a bug involving item deletion while a new client is connecting, trying to resolve
625bba - Using spatial hash maps now instead of distance checking everything
9b665a - Adding fixes to quantization problem