# procedural generation - deterministic or not? (No man's sky)

Here is a link of Sean Murray talking about the game No Man's Sky:

Starting at around 4:00 in the video, he is talking about how the environment is procedurally generated.

At first, I thought it meant that they ran some incredibly complex algorithms to generate the entire universe and then stored it.

But as he explains, the world doesn't really exist as stored 3d data and what have you, but it really is just the output of a very complex function that takes your position (3d coordinates, and I guess time as well) as input and always generates the exact same environment around you based on that, no matter where you are in this gigantic universe.

This is incredibly smart and interesting but there are a few things that I don't understand:

How can you interact with the environment and have any effect on it if it is the result of a deterministic function? You would have to "update" that function every time you interact, don't you?

How can multiple players interact with the environment and see the same changes?

How can only a single player blow out a piece of rock and then expect it to stay blown apart? Does it change the "world-generating function" ?

• The approach of using deterministic procedural generation to save time and storage space isn't new. It was first done by Elite back in 1984. A more modern example of this is Minecraft. Dec 28, 2014 at 17:17

How can you interact with the environment and have any effect on it if it is the result of a deterministic function? You would have to "update" that function every time you interact, don't you?

It's a simple enough concept to create any unmodified point in space / event in time / combination of these using a fixed function. The downside is that when any player modifies the procedurally-generated world at a given place / point in time, you have to store (the results of) this change -- potentially across clients if a multi-client environment. Because of custom modifications, the function alone is now no longer sufficient to produce that given point in space / time... instead you must first generate it from that function, and then apply any deltas that players have created at that point in time/space.

I suspect that anyone who was able to change this simple but apparently logically-immutable fact could make a lot of money indeed and the knock-on effects of this would run quite outside of just developing virtual worlds, as this idea runs deep into the heart of both compression and cryptography.

How can multiple players interact with the environment and see the same changes?

The deltas must be sent. The function alone cannot produce player-made changes on another player's machine, so the only way to get that information across is to send it.

How can only a single player blow out a piece of rock and then expect it to stay blown apart? Does it change the "world-generating function"?

No (as noted above).

deterministic or not?

Procedural generation should, by default, be considered to be an inherently deterministic concept as without being so, you can see how the whole approach falls apart.

• "you have to store (the results of) this change" That is wrong :) But this is right: "and then apply any deltas that players have created at that point in time/space", you don't store the result, you store the actions the player preforms. Dec 29, 2014 at 7:33
• @Zehelvion Hence the parentheses. OTOH You assume too much: We store / transmit whatever is most efficient in our given case. Your bottleneck may be time or it may be space / bandwidth. That is, it may be very costly to recreate current state by applying deltas, in which case we may prefer to store absolute state. Storing deltas is common, but not mandatory. Dec 29, 2014 at 8:29
• I agree. I simply think it may be wrong in their case to store the results cause it seems like they are going to revert most things most of the time, I don't know. Space is not much of an issue nowadays as it was only 20 years ago. I +1ed your answer either way. Dec 29, 2014 at 17:24
• I think you can see this incremental computation of the world state happen. I've seen reviews that show a piece of resource (rock?) visible from a distance (= result of the procedural generation), but upon approaching it disappears and says you already mined it (= when the modification data comes in). Aug 26, 2016 at 22:43

Procedural generation works on the idea that you know what you want to create and how it is created but you leave out the details. Think of a set of sliders for color, size, roundness / sharpness, amplitude and such aspects. You don't want to define every aspect of the result by hand. You want to outline a general idea of what you'd like and won't like to see, color sets, surface smoothness, and such.

This obviously defines the world in it's virginal state. You are saving hard drive and memory space because you aren't storing a lot of detail. You let the details get randomized with a predetermined seed which means, you don't know what will happen but it will happen again and again every time (like perlin noise from a seed), in fact, the creator says the worlds are created by noise that uses a seed to repeat the same results. It is all build on the notion that you have the functionality to build a planet using a set of values to define it's properties first and then you let the algorithm, randomly pick these values. The universe itself is built on the concept of randomly picking far enough but not too far spots to place planets.

To store player modifications, you normally wouldn't want to store the entire mesh with the modifications applied to it (i.e. storing the result) as that would be space consuming, what you normally would do is store the actions the user took. Think Command Oriented Architecture. Then when someones else approaches that area, you need to "replay" these actions as you generate the mesh. This is where things get challenging. If the player has a lot of power to modify things in the world, it could require a lot of processing power to replay these actions. This is why I think something like digging tunnels (like it's done in Minecraft) would be very hard to accomplish if you don't store the results. It is entirely possible though.

Also think of more complicated aspects, a player kills a bunch of animals. Now time passes by and the world changes because time affects it, would the players actions affect the world? In a sense probably no. Killing a hundred deer will probably not cut down on deer population (as we have come to expect from MMO) as the world will be restored to it's virginal state and be repopulated according to the seed of time and space. Unless of course, the server stores the hunting activity and takes it into account when respawning new creatures.

A lot of interesting effects of player activity that don't relate to game mechanics and have to do more with simulation are lost if everything is generated on the spot. How does cutting down the herbavor population affect the carnivor population? How does it affect the plants in the area? But I digress.

You can do this while procedurally generating content. Think about it like this: You procedurally generate like you said, but instead of storing the whole universe, you store a part of the world which you are in, say a sqare kilometer around you in the memory. When the generation is complete, you can throw a rock and store its position accordingly. When you are about to generate an other sqare kilometer of your universe, throw out the previous one.

You can even save the position (or properties) of the rock you thrown, by generating a unique indentifier for your objects in your procedural functions. If the generated id of the rock is deterministic, you can load back its properties once you move back to that area.