Procedural Generation, Game Updates, & Butterfly Effect

Question

NOTE: I asked this on Stack Overflow a few days ago but had very few views and no response. Figured I should ask on gamdev.stackexchange instead.

This is a general question / request for advice on maintaining a procedural generation system through multiple post-release updates, without breaking previously generated content.

I am trying to find information and techniques for avoiding "Butterfly Effect" issues when creating procedural content for games. When using a seeded random number generator, a repeating sequence of random numbers can be used to create a reproducable world. While some games simply save the generated world to disk once generated, one of the powerful features of procedural generation is the fact that you can rely on the reproducability of the number sequence to recreate a region multiple times in the same way, removing the need for persistence. Because of the constraints of my particular situation, I must minimise persistence, and need to rely on purely seeded concent as much as possible.

The main danger in this approach is that even the slightest change in the procedural generation system can cause a butterfly effect that changes the entire world. This makes it very tricky to update the game without destroying the worlds that players are exploring.

The main technique I've been using to avoid this problem is to design the procedural generation in multiple phases, each of which has its own seeded random number generator. This means that each sub-system is self contained, and if something gets broken it will not affect everything in the world. However this seems like it still has a lot of potential for "breakage",even if in an isolated part of the game.

Another possible way of dealing with this problem could be to maintain complete versions of your generators within the code, and keep using the right generator for a given world instance. This seems like a maintenance nightmare to me though, and I'm curious if anyone actually does this.

So, my question is really a request for general advice, techniques, and design-patterns for dealing with this problem of the butterfly effect, especially in the context of post-release game updates. (Hopefully that's not too broad a question.)

I am currently working in Unity3D / C#, although this is a language agnostic question.

UPDATE:

Thank you for the replies.

It's looking more and more like static data is the best and safest approach, and also that when storing a lot of static data is not an option, having a long campaign in a generated world would require strict versioning of the generators used. The reason for the limitation in my case is the need for a mobile based cloud save / sync. My solution may be to find ways of storing small amounts of compact data about essential things.

I find Stormwind's concept of "Cages" to be a particularly useful way of thinking about things. A cage is basically a reseed point, preventing run-along effects of small changes, ie caging the butterfly.

Answer 1

I think you've covered the bases here:

• Using multiple generators or re-seeding at intervals (eg. using spatial hashes) to limit the spillover from changes. This probably works for cosmetic content, but as you point out it can still cause breakage contained within one section.

• Keeping track of the generator version used in the save file and responding appropriately. What "appropriate" means could be...

  • Keeping a history of all previous versions of the generators in your game executable, and using whichever one matches the save. This makes it harder to patch bugs if players keep using old saves.
  • Warning the player that this save file is from an old version, and providing a link to access that version as a separate executable. Good for games with campaigns lasting a few hours to days, bad for a campaign you expect to be playing for weeks or more.
  • Keep only the last n generator versions in your executable. If the save file uses one of those recent versions, (offer to) update the save file to the latest version. This uses the appropriate generator to unpack any outdated state into literals (or into deltas from the new generator's output on the same seed, if they're very similar). Any new state from here on comes from the newest generators. Players who don't play for a long time could be left behind though. And in the worst case you end up storing the whole game state in literal form, in which case you might as well...

• If you expect to be altering your generation logic frequently and don't want to break compatibility with previous versions, don't rely on generator determinism: save your whole state in your save file. (ie. "Nuke it from orbit. It's the only way to be sure")

Answer 2

The primary source of such the Butterfly Effect is arguably not number generation - which should be easy enough to keep deterministic from a single number generator - but rather the use of those numbers by client code. Code changes are the real challenge in keeping things stable.

Code: Unit Tests The best way to ensure that some minor change somewhere doesn't manifest elsewhere unintentionally, is to include thorough unit tests for every generative aspect, in your build. This is true of any piece of compact code where changing one thing can impact on many others - you need tests for all so you can see on a single build what has been impacted.

Numbers: Periodic Sequences / Slots Let's say you have one number generator that serves for everything. It doesn't assign meaning, it just spits out numbers in sequence - like any PRNG. Given the same seed over two runs, we get the same sequences, yes? Now you give things some thought and decide that there will be maybe 30 aspects of your game that will regularly need to be supplied with a random value. Here we assign a cycling sequence of 30 slots, e.g. every first number in the sequence is rough terrain layout, every second number is terrain perturbations... etc. ...every 10th number adds some error to AI state for realism. So your period is 30.

After 10, you have 20 slots free that you can use for other aspects as game design progresses. The cost here is of course that you must generate numbers for slots 11-30 even though they're not currently in use, i.e. complete the period, to get back to the next sequence of 1-10. That has a CPU cost, though it should be minor (depending on the number of free slots). The other downside is you need to be sure that your final design can be accommodated in the number of slots you made available at the very start of your development process... and the more you assign at the start, the more "empty" slots you potentially have to go through each, to make things work.

The effects of this are:

• You have one generator producing numbers for everything
• Changing the number of aspects you need to generate numbers for, will not impact on determinism (provided your period is large enough to accommodate all aspects)

Of course, there will be a long period during which your game is not available to the public - in alpha, so to speak - so you could reduce down from say 30 to 20 aspects without impacting any players, only yourself, if you realised that you had assigned way too many slots at the start. This would of course save some CPU cycles. But bear in mind that a good hash function (which you can write yourself) should be lightning fast, anyway. So having to run extra slots should not be costly.

Answer 3

If you want persistence with PCG, I suggest you treat the PCG code itself as data. Just as you would persist data across revisions with regular content, with generated content, if you wish to persist it across revisions, you'll need to persist the generator.

Of course, the most popular approach is to convert generated data into static data, as you've mentioned.

I don't know examples of games that keep around lots of generator versions around, because persistence is unusual in PCG games - it's why permadeath often goes hand-in-hand with PCG. However there are plenty of examples of multiple PCGs, even of the same type, within the same game. For example, Unangband has many separate generators for dungeon rooms, and as new ones are added, the old ones still work the same. Whether that's maintainable is up to your implementation. One way to keep it maintainable is to use scripts to implement your generators, keeping them isolated with the rest of the game code.

Answer 4

I maintain an area of ca 30000 square kilometers, holding ca 1 million buildings and other objects, in addition to randomized placements of misc things. An outdoor simulation ofc. The stored data is ca 4 GB. I am lucky to have storage space, yet it's not unlimited.

Random is random, uncontrolled. But one can cage it a little:

• Control it's start end end (as mentioned in other posts, the seed number and how many generated numbers).
• Limit its numerical space, eg. generate integers between 0 and 100 only.
• Offset its numerical space, by adding a value (eg. 100 + [generated numbers between 0 and 100] produces random numbers between 100 and 200)
• Scale it (eg. multiply by 0.1)
• And apply various cages a around it. This is reducing, scrapping part of the generation. Eg. if generating in 2-dimensional space, one can put a rectangle on top of number pairs and scrap what's outside. Or a circle, or a polygon. If in 3D-space, one can accept for example only triplets that reside inside a sphere, or some other shape (now thinking visually, but this doesn't necessarily have anything to do with actual visualisation or positioning).

That's about it. Cages also consume data, unfortunately.

There is a saying in finnish, Hajota ja hallitse. Translates into Divide and conquer.

I quickly abandoned the idea of precise definition of smallest details. Random wants freedom, so it got the freedom. Let the butterfly fly - inside it's cage. Instead i focused on having a rich way to define (and mainain!!) the cages. It doesn't matter what cars they are, as long as they are blue or darkblue (a boring employer said once:-)). "Blue or darkblue" being the (very small) cage here, along color dimension.

What is manageable, for controlling and managing numerical spaces?

• A boolean grid is (bits are small!)
• Corner points are
• As is a tree structure (= to follow into "cages holding cages")

Maintenance-wise, and version intercompatbility-wise... we have
:if version = n then
:elseif version = m then...
Yep, the code base grows larger :-).

Familiar things. Your correct way to go ahead would imho be to define a rich method to divide and conquer, and sacrifice some data on that. Then, where possible, give the (local) randomisation freedom, where it is not crucial to control it.

Not totally incompatible with the funny "nuke it fom orbit" proposed by DMGregory, but perhaps use small and accurate nukes? :-)