10
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I'm voting to close this question as off-topic because it's too broad. \$\endgroup\$ – Almo Apr 15 '16 at 3:28
  • \$\begingroup\$ I realise it's very broad. Would you recommend I try a gamedev forum or something instead? There is not really any way to make the question more specific. I was hoping I might hear from someone with a lot of experience in this area, with some cunning tricks that have not occurred to me. \$\endgroup\$ – null Apr 15 '16 at 3:40
  • 2
    \$\begingroup\$ Almo is mistaken. It is not at all broad. This is an excellent question and quite narrow enough for good answers to be given. It's something that I think a lot of us procedural folks have often pondered. \$\endgroup\$ – Engineer Apr 16 '16 at 8:24
8
\$\begingroup\$

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")

\$\endgroup\$
  • \$\begingroup\$ If you built the generation rules, then is there a way for you to reverse the generation? I.E., given a game state, can you revert this to a seed? If that's possible with your data, instead of linking the player to a different game version, you could provide an update utility which generates a world from a seed with the older system, then uses the generated state to produce a seed for the new generator. You may have to warn your players of a wait for conversion though. \$\endgroup\$ – Joe Apr 15 '16 at 11:49
  • 1
    \$\begingroup\$ This is not in general possible. You're not even guaranteed that there exists a seed for the new generator that gives the same output as the old one. Usually these seeds contain about 64 bits, but the number of possible worlds your game could support is likely to be greater than 2^64, so each generator only ever produces a subset of these. Changing the generator will very likely result in a new subset of levels, which may have little or even no intersection with the previous generator's set. \$\endgroup\$ – DMGregory Apr 15 '16 at 11:54
  • \$\begingroup\$ It was hard to choose the "Right" answer. I picked this one because it was concise and summarised the main issues in a clear way. Thanks. \$\endgroup\$ – null Apr 17 '16 at 22:29
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Hi. That sounds similar to some things I'm doing. I usually generate a bunch of sub-seeds up front based on the initial world seed. Recently I started pre-generating a longish array of noise, and then each "slot" is simply an index into that array. That way each subsystem can just grab the right seed and work in isolation. Another great technique is to use x,y coordinates to generate a seed for each location. I'm using the code from Euphoric's answer on this stack page: programmers.stackexchange.com/questions/161336/… \$\endgroup\$ – null Apr 16 '16 at 8:36
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ That's a clever idea, to simply use different generators for different areas. \$\endgroup\$ – null Apr 16 '16 at 6:43
2
\$\begingroup\$

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? :-)

\$\endgroup\$
  • \$\begingroup\$ Thanks for your answer. That sounds like an impressively large procedural area to maintain. I can see how for such a large area, even when you have access to a lot of storage, it's still impossible to simply store everything. It sounds like versioned generators are going to have to be the way forward. So be it :) \$\endgroup\$ – null Apr 17 '16 at 6:21
  • \$\begingroup\$ Of all the answers, I find myself thinking most about this one. I enjoyed your slightly philosophical descriptions of things. I find the term "Cage" very useful when explaining the ideas, so thanks for that. Let the butterfly fly... in its cage :) \$\endgroup\$ – null Apr 18 '16 at 4:29
  • \$\begingroup\$ PS I'm really curious to know which game you work on. Are you able to share that information? \$\endgroup\$ – null Apr 18 '16 at 4:29
  • \$\begingroup\$ Could add one more thing about the numerical space: It's worth to always stay close to zero. That you knew probably already. Close to zero gives the best numeric accuracy and most bang for least bits. You can always offset a whole bunch of close-to-zero numbers later on, but you only need a single number for that. Similarly, you can (i'd almost say you MUST) move distant calculation closer to zero, with an offset. - Stormwind \$\endgroup\$ – Stormwind Apr 18 '16 at 14:33
  • \$\begingroup\$ Evaluating on the previous, consider a small vehicle movement, a 1-frame increment of 0.01 [meters, units]: You cannot accurately calculate 10000.1+0.01 in 32-bit numeric accuracy (single) but you CAN calculate 0.1+0.01. Hence, if the "action" takes place far away (behind the mountains :-)), do not go there, instead move the mountains to you (move with 10000, then you are at 0.1 now). Valid also for storage space. One can be greedy with storage of numeric values close to each other. Store the common part of them once, and the variations individually - may save bits! Did you find the link? ;-) \$\endgroup\$ – Stormwind Apr 18 '16 at 19:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.