Procedural Content Generation with Node Decay

Released in 2016, No Man’s Sky UPS was a world with infinite possibility. I was very excited about the release of such a game because it created new possibility in games and might even inspire someone to do it better. The game flopped on release, but the concept was unique, I was excited of what’s to come. Fast-forward 3 years later, still very little innovation in such a genre.

Two incidents caught my attention recently, Minecraft 2b2t and Sky Citizen. Minecraft 2b2t server is a good example of maintaining a world with infinite possibility. 4000 GB of data, and <100 players can be on it at a time. Huge noticeable lag as the server is struggling to maintain and stream world info the user. Sky Citizen is another game designed with a world that you can take a lifetime to visit.

I did some research (just 1 hour) on procedural content generation in games on published paper. Asked one friend that studied game design from my army days. Countless nights thinking about it and doing some light Googling. There were quite a few mentions on procedural content generation but none talking about how to make such a system scale.

How to store a limitless world that can be modified?

Procedural Generation

Generate the world procedurally with an integer-like seed. I am not going to dive into this, there are enough articles about this.

Parent Seed Node

For example, the infinite world is make up of a 64 bit integer seed. In the beginning, the launch date; that’s the only piece of data you store for the game. All players will experience the world with infinite possibility with just that 64 bit seed. That 64 bit seed will be the parent node to the world.

Leaf Node

As users start to explore a region and started making changes to the world. You spawn the child node that cascades, as they get closer to the ground. The child node must also be seeded procedurally from the parent node. By doing so, you keep the player in sync as all users see the same thing. The server doesn’t have to stream additional leaf node info if the world is left untouched. Changes are made to the leaf node, and every change they make will be saved with a level of granularity. Users that are out of render distance don’t need to see the change as they are looking at their own node.

As user starts to build mega structure, you need to save the effect they make on the parent node. Similar to how satellite can see artificial structure. What you can do is use the same procedural generation technique and use a brute force seed generation technique to find the closest match and save it. By brute force computing a seed until you can find a seed with the highest % match to all the child nodes. The Higher the % matched means lesser data needs to be saved as you don’t need to stream the changes users have made as it can be calculated from the parent node seed.

You can queue this and run it in the background as they are not necessary useful if the world is heavily populated as changes are made too quickly to generate a matching seed.

Scaling by Decaying Node

Over time, as the user leaves the planet system, let the node decay. By allowing the node to decay, you can play with the granularity of what the user sees. You can also decay the node to match your procedural generation technique, meaning doing it to increase the % match. (Read above)

Decay the node upwards over time. Once all leaf nodes are decayed, start decaying the parent. Just like our world!

Grieving

The best way to protect against grieving is to balance creation and destruction. Make destruction of property harder than simply creating. Create a legal system like ours. Create an industry in game around protecting property.

Thoughts on Versioning

However, you need a procedural generation technique with versioning support. When you create a new item and object into the game, you want user to be able to create them into the world. Allow the seed data to have version info so that user can run different procedural techniques locally when they visit an existing or new world.

With versioning, you can also optimize the technique I mentioned above. Additionally, region that are left untouched, you can invent new content by replacing that node with a new version and seed and therefore new content! New structure, new clouds & new alien!

Finally

I wrote this just to get it off my mind, I am not a Game Engineer, I just like games like you. If you think I am pulling this out of my ass, please entertain me and comment why it won’t work. I would love to understand more about this.