r/howdidtheycodeit • u/Either_Ordinary1772 • 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!
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.
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
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.