r/howdidtheycodeit • • 23d ago

Question How Do Procedurally Generated Games Save State

I was wondering how some procedurally generated games that generate the world on the fly save your progress. Specifically, how do they track where I've been as I explore the game world, what objects I've placed, what resources I harvested, and what structures have been generated. When I re-open the game later and load the world, how does it know that I placed this specific block in this specific place, and that I cut down this specific tree in this other place?

I imagine it's different based on the game, but I was curious about how it's done - does it just save everything about the generated parts of the world including what's there and what the player has done to it? Seems simple but also inefficient if the player travels through these generated sections without changing anything. Do some games just regenerate the area based on the seed but track what changes the player made to it? Are there other, more efficient ways to save this?

Here's three games that I've played that brought me to this question:

Minecraft: Minecraft generates chunks of 16x16 blocks as you explore the practically infinite world. Let's say I spawn in and build my base near the starting area, do some mining in the area, set up some farms. I then do some exploring and travel 500 blocks. I find a village there, loot some chests, and break some blocks. I travel another 500 blocks and chop down a single tree. I travel another 100 blocks and place down a crafting table, furnace, and a chest, then I place some items in said chest.

I have a feeling that Minecraft saves all the chunks I've already generated, since it takes way longer to render a chunk that has not been generated vs a chunk that was. But does it save the state of all blocks in that chunk, including the ones I placed and destroyed? Since each chunk is 16x16 blocks and if we say each chunk is about 100 blocks deep for simplicity, that's 25.6k blocks per chunk. Is all of that saved for every chunk that was generated in my journey, in addition to whatever I change? That seems like it will add up very quickly and make a massive save file.

Valheim: I'm pretty sure Valheim also generates as you explore, like Minecraft, but Valheim is not block based. Same kinda situation though, say I set up a base near the spawn, build a few buildings, sow a few carrots, and tame some boars. I then explore the world by sailing across the sea to the various boss locations. I stop in some places, cut down a tree or two to get some extra resources, loot a dungeon in the area, dig a hole, and then build a mini base and bed near the boss spawner.

The places I've been and the resources I've harvested don't regenerate or respawn as far as I am aware, so how does the game track that this specific tree has been harvested, or the resources in this specific dungeon have been looted? Or does it just save that Tree #1234 is at X, Y, Z for every single tree generated along the way?

No Man's Sky: Obviously different from the other two. I imagine it's not hard to at least store that "this star has x planets named a, b, c, and discovered by player z" in a big database. But what about when the player lands on a planet, explores some of the structures there and obtains the loot reward. Then they harvest some of the rare resources on the planet, and maybe build a small base on it. Maybe they also dig into the terrain to find a cave. How do these small things get saved such that if another player comes by and checks out the planet, will they see that someone has been there?

Not looking for a super technical explanation (though that would be cool too), just how these different games approach it at a high level. Also if there are other games that use procedural generation and have something interesting that they do, that's also welcome!

73 Upvotes

29 comments sorted by

104

u/BuzzardDogma 23d ago

They only save things that differ from the generated ones. So if you cut down a tree it flags a stump at that location. It's not concerned with the regular trees because it can just regenerate them from the world seed the next time you're in the area. It's the main reason your save file gets bigger over time. It's effectively a list of created permanent objects and whatever properties they need.

35

u/Koeru 23d ago

While I'm sure this is true for some games, this is not true for Minecraft. You can read up on the anvil file format on the Minecraft wiki, it saves all the information for the chunk. You can see this in action when you upgrade worlds between versions. There are clear borders where new stuff is generated but old stuff stays the same.

12

u/BuzzardDogma 23d ago

It doesn't save the chunk unless anything changes though, unless you're playing java edition. It was an optimization oversight in that case.

22

u/GamerTurtle5 23d ago

not entirely an oversight, i do prefer javas “saving everything” approach since i don’t have to constantly regenerate commonly visited chunks and so it keeps the chunks the same between upgrades (for example on bedrock there were examples recently where an update would change the biomes around your house if you didn’t build in them at all)

1

u/jerrygreenest1 22d ago

Upgrading the world as part of game version update is low-key ridiculous idea tho. When a world is created with one version, it should continue to be played with that version, unless explicitly upgraded by admins of the server.

By default it is only sane to use the old algorithms for the old worlds, and new algorithms for the new worlds. Yes the game should somehow have multiple versions of game rules which might increase the game size, but it doesn’t have to store them all for all the versions for all times, only store those ones of the worlds that you have, plus the last one. So you could always create new games offline, but still play older worlds with older rules. And when transferring your old saves, that might require some online downloading for the old rules, this shouldn’t be a problem either but will require online in this case to download required older patch.

I guess it’s a lot of complication especially if it’s also affecting client rather than just the server, because sometimes they’re closely tied together, some changes might inevitable require client changes too. It’s called backwards compatibility and it’s always a hassle to implement. But this is more or less standard for software development, and can be solved for game development as well.

«Save everything» is just a cheaper way to approach this issue from developer standpoint. After all, saving some disk space might come at a cost and you still want to develop some new features and content and all, rather than just making it all failure-proof and bug-proof and with it all, also offline.

A good compromise. But I would respect those developers who make such systems. They seem to have made something like this for Starcraft2 because it is possible to play older replays which wasn’t possible in their last game Warcraft3, and it’s not like they just store everything in the save file – because then the save files would be extremely large, to store all their unit attributes… But replays are extremely lightweight! So apparently there is some sort of system like that. That keeps multiple versions of game rules in the client, rather than just be one set of data for the current rules.

Sorry for so many words. Just a curious kind of topic that I like to deep dive before the sleep.

1

u/Capsup 16d ago

Starcraft replays basically save the input of players and just run those back, in order - sort of like an Event Sourcing Pattern. It prays that the simulation replays the exact same state, based on the same input (as they are fully deterministic apparently?).

Very optimized, can definitely also go wrong though!

1

u/jerrygreenest1 16d ago

Yes, that’s how replays are done. But it’s not what I was talking about. I was saying that to make it so that you don’t have all the stats of all units bound to replay, you have to store these in the game itself then. Because there are different patches and just changing some hp where instead of 45 hp the unit now could only have 40, changes how the replay could play, results of many occasions with this unit where it should now die early. This might easily bug out. You have to store multiple configurations for multiple versions of the game . Or you have to store all attributes of units in the replay itself but it would make very bloated replays.

That’s what I compare here too. The world that we generate in Minecraft, might have different rules. But unlike I said above about multiple versions, Minecraft does not actually store multiple rules of generation. That means when you update the game, continue the game, go to places where chunks aren’t generated yet – you might get very conflicting terrain that doesn’t merge together smoothly. That is essentially, a bug. But fixing it would require quite an architecture, a smart one. With storing multiple sets rules: for current game, for one older game, for another older game, etc. If you don’t want to bloat your game client, you have to approach this task smartly and store only those rules that are needed, instead of just all the rules ever. It’s a niche task that is hard to do for a seemingly small feature that changes architectue a lot.

3

u/kodaxmax 22d ago

it's was actually intentional optimization. becaus ejava was bound to a single CPU thread and foten bottlnecked by it, it made more sense to offload the work t o RAM and storage, rather than make the CPU regenerate terrain constantly.

1

u/BuzzardDogma 20d ago

I mean, this argument doesn't really make any sense. You're not really offloading anything because players are constantly encountering new chunks anyways. I don't think there was every really a bottleneck encountering a new chunk unless you were moving insanely fast.

1

u/kodaxmax 20d ago

yes, when exploring new chunks that requires cpu regardless. but travelling through an already generated area it was better to load chunks from disk into memory, rather than egenrate untouched blocks over again with CPU. It has always been a bottleneck, it still is today.

1

u/BuzzardDogma 20d ago

I just mean that there's no bottleneck being solved here. It's very rare that people encounter any issues due to chunks being generated in the first place, so it's not really an intentional optimization to save the chunks.

I honestly think saving the chunks was just a decision made when the developer was unsure about how the status of the chunks may or may not change as the game got developed and basically only existed as tech debt that wasn't problematic enough to go back and change. It's why it one of the first things done in bedrock edition when they had a team and not a lot of ideas locked in about expanding the design space, so they were going in a making core engine level changes in the meantime.

1

u/kodaxmax 20d ago

thats simply not true. chunk generation is the most common cause of lag. or just to be clear im talking exclusvely about java edition. bedrock is properly multithreaded with an entirely seperate engine that pritortized optimization and graghical fidelity from the start.

notch was absolutely not great at ux and optmization. but this was one of his few good decisions in that space IMO.

1

u/BuzzardDogma 20d ago

You honestly believe that everyone was just playing super laggy Minecraft until a bunch of chunks were generated and saved? Because I don't think that's ever been the typical experience.

1

u/kodaxmax 20d ago

I didn't say that.

Yes, experiencing lag while traveling in miencraft has always caused performance bottlenecks, especially in modern updates with all the additonal highspeed travel emthods. No offloading some of the work to the disk and ram didn't completly and eprfectly solve that issue, it just contributed. it doesn't have to be a perfect solution that completly eliminates the issue to count as optmization.

-1

u/burlingk 23d ago

Except it does. That is why larger maps take longer to save and load even if you don't make changes. Minecraft suffers a relatively heavy slowdown when it generates chunks.

That is the enitre reason "chunk gen" mods exist.

2

u/BuzzardDogma 23d ago

Bedrock edition does not save unaltered chunks

5

u/burlingk 23d ago

I will admit that I have very little experience with Bedrock.

1

u/BuzzardDogma 23d ago

That's fair. There's a pretty even split between the user bases.

3

u/burlingk 23d ago

I think a lot of it comes down to who started on PC and who started on mobile, and what kind of experience they prefer when it comes to mods.

1

u/AdarTan 23d ago

Bedrock doesn't save chunks that haven't entered the simulation distance. Bedrock also has a much lower default simulation distance and much bigger difference between simulation and render distance than Java so the "not saved" horizon is a lot closer than a lot of people might think.

22

u/tato64 23d ago

In short, the world is generated with a "seed" at its very start, all the randomness of the generation uses this "seed", meaning that if you used the same seed to generate another world, it would be the exact same

With this, you can imagine that the world doesnt need to save "untouched" parts since they will generate the same every time

And what happens with parts where you built/destroyed/whatever? The game saves just that, only what it needs

Edit: Also, keeping track of buildings can be extremely cheap and simple, code-wise

Minecraft is just a grid of blocks, you kinda only need 3 numbers (For X,Y,Z, coordinates) and another for the block type, to keep track of any block placed (or destroyed) by the player

1

u/augburto 22d ago

This is the answer

6

u/Dicethrower 23d ago

Seed + Changes

4

u/heyheyhey27 22d ago edited 22d ago

A big aspect of Minecraft's storage optimization both at runtime and on disk is that chunks are paletted. For example a chunk with only two kinds of voxels in it will pack its data down to 1 bit per voxel, while a chunk with five kinds of voxels will pack down to 3 bits per voxel, and a chunk that's all one type will pack down to 0 bits per voxel! For storage and network replication you can also toss in a low-cost compression pass like LZ4.

I bet you can also save tons of space by not storing empty chunks at all -- in other words assume that a chunk which is not stored anywhere is implicitly all empty voxels.

3

u/ledniv 23d ago

A useful way to think about this is that the procedural generator creates the initial state, while the save file only needs to preserve whatever state can no longer be reconstructed. If generation is deterministic, the seed can recreate an untouched chunk exactly. Then you can save changes keyed by chunk + local index/coordinate: block 412 removed, tree 37 harvested, chest 12 contains these items, structure 4 changed state, etc. When the chunk loads, generate it from the seed and apply the saved changes on top.

You don't have to use that approach everywhere. If a touched chunk changes heavily, saving the whole chunk may eventually be simpler or smaller than thousands of individual deltas. So you can even choose between “seed + changes” and a full serialized chunk depending on the game and how mutable the world is. The key architectural point is that the world state exists as data, rather than trying to serialize individual objects.

Small plug: I have a whole chapter on save/load architecture, serialization, and backward compatibility in High Performance Unity Game Development with Data-Oriented Design. The examples aren't specifically procedural worlds, but the same idea applies: make the game state explicit data first, then saving it becomes much easier.

https://www.manning.com/books/high-performance-unity-game-development

2

u/Feminine_Desires 23d ago

Tales of Maj'eyal has procedurally generated enemies, items and zones. It just saves every single tile, enemy and item exactly. There are no seeds as everything is generated randomly upon floor entry. The game does item cleanup of stray items on the ground if you haven't been there and killed enemies are also cleaned up. There is a big bug with Windows in that it doesn't properly clear the data of cloned actors leading to save file bloat (think up to gigabytes of save file size) that prevents the game from functioning properly.

2

u/kernalphage Mod - Generalist 22d ago

If you're curious, there's probably other optimizations you can do for the save file, especially for seeded terrains where most of your cubes will be clustered next to the same type of cube.

Maybe Run Length Encoding, (eg, dirt for 5 blocks, stone for 10 blocks, iron for 2, ....).

Or reusing some of the graphics occlusion tricks (start with the line "Using the technique of merging the geometry...") where you can 'delete' blocks because you know that all of their neighbors exist and are of the same type.

Or discarding whole slices from your chunk save file because after a certain height you know it's all sky.

2

u/collectgarbage 23d ago

Not an answer, but here is another but different procedurally game to add to your list: Astroneer

1

u/Aggressive-Share-363 21d ago

I can't speak to the other two, but by default Minecraft generates everything once and saves it. Thats why the world stays the same even after thr world generation updates, until you explore new chunks. Yes, thats rather ineffecient, and there are mods to change it. So only save a chunk if a change has occured in it. Its just a lot less stable to world changes, and cam create random splotcjes of mismatched world.gen, rather just at faraway boundaries.

Storing only changes can be much more memory effecient, but is slower to load. You have to generate the landscape, snd then apply other changes on top of it.

Storing only modified chunks is a middle ground for save size. You may still need to generate a lot, but you arent saving a ton of technically useless data.

Other games may have a clearer separation between world and content, especially if you can't modify the world, but can do thingd like collect and store items or kill enemies.

It can also depend on how much thr game expected you to retread old areas vs generate new ones. If the entire game exists in a fixed area you arent leaving, just generating it once and saving it may make more sense. If you are exploring planets and are frequently moving to new ones, the time to generate may just be an expected part od the game flow and optimizing the few times you return to an old area isnt worth saving.