Combining Minecraft and Dwarf Fortress: Simulating autoplay in a pseudo-infinite procedurally generated world?

Question

One of the interesting things about Dwarf Fortress (and other procedurally generated games like Civilization) is that the game simulates multiple AI factions interacting with each other over time (what might be termed "autoplay") to generate an evolving world which changes over time, even whilst the player is playing the game.

On the other hand, simulating all the factions simultaneously is surely going to become a bottleneck as the map grows. With a bigger map and more factions, the performance requirements become exorbitant. Minecraft gets around this problem by simply storing the inactive chunk in memory as-is as soon as the player leaves the area. The minecraft world is a static, never-changing place. When a player comes back from a trip, the chunk is exactly as he left it. No world evolution occurs. Everything is always the same.

The most straightforward approach to this, which is to just to make chunks remain loaded in memory even after the player is no longer in them, has the same performance issues as mentioned earlier - as the player moves across thousands of blocks, you will sooner or later run into computation limits. Moreover, this does not solve the general problem of faction simulation - factions can expand or contract through many chunks, whereas keeping one chunk loaded in memory would not affect its neighboring chunks, so that doesn't quite achieve the same effect as autoplay.

The "solution" that I thought of is to come up with a closed form formula that simulates autoplay somehow. That is, a function f(time,coordinates), such that given the time and and coordinates of a block, will tell you what state that block should be in. The problem with this is that this assumes a truly predeterministic world evolution, in which players have control over only their local chunk and no others. In other words, no butterfly effect. Furthermore, when a player leaves a chunk, he has made some changes to it, but the function cannot take those changes into account when computing the state of the block the next time the player enters it, in other words all changes that the player made to the block are lost as soon as he leaves. This is obviously not ideal.

Am I asking for something impossible?

Answer 1

Fake it!

It's a game, after all. We approximate constantly.

Simulations have an inverse correlation between fidelity and size/scope, so given fixed hardware you'll have to compromise. If you want a huge world, you'll need to reduce fidelity.

Always ask: Can the player tell the difference?

Variable Fidelity

This answer, broad as it is, relies on the idea that you can adjust your AI/world simulation's fidelity fairly easily, which I think is beyond what I can explain here. In general, the idea is to aggressively relax constraints as you reduce fidelity, thereby reducing the time it takes to simulate.

E.g., say you have an NPC with 'thirst', and it lives in an house near-ish to a body of fresh water.

• Highest-fidelity: Path-plan how each NPC gets from their current location to the water, and have that NPC execute this at a time appropriate for their thirst level, which is affected by their other activities.
• High-fidelity: Vaguely assert that NPCs in an area can reach the water, taking X units of time to do so, so any time that "high-level action" is taken, they lose some units of time and lose thirst.
• Mid-fidelity: The NPCs live near water and have jobs with thirst 'costs'. Use those costs to reduce the NPCs' available time.
• Low-fidelity: There's a population of NPCs in an area with a mix of jobs, quenching thirst occupies X% of their available time.
• Very-Low-fidelity: A faction has a population that loses X% of its time to resolving thirst. Eventually this time can accumulate to represent large-scale works (building dams), or going to war over water rights, etc.
• Lowest-fidelity: Regions of size Y and climate Z tend to have P-Q factions, population ranging from M to N. Z climate means those factions spend J-K% of their time related to thirst and thirst endeavors.

etc.

The highest fidelity is for use when the player's in the area and may be watching, or has made significant changes the area. Lowest fidelity is for when you just want to say "Are there any factions to the east of the currently known map that might launch an attack on a water-rich nation?"

The important thing, again, is that players likely won't be able to tell the difference, if you're careful with when you employ different levels.

So with that kind of system in mind, it's really just about choosing when you can get away with reduced fidelity, and how much it can be reduced by.

Closed Form

Your 'closed form' suggestion is a good way to reduce fidelity (ignoring player edits), but I imagine you'll find it very hard to implement. AI and simulation are notoriously finicky even without this constraint.

Absence Makes the Simulation Grow ... Lower-fidelity

IMil's suggestion to think in terms of a 'state + time' mutation function is good, and I think you could find decent success by "binning" that mutation step into different fidelities, by duration.

E.g.:

• Recently visited chunk: high-fidelity update
• Absent a couple hours? "middle-fidelity" update
• Absent a couple days? low-fidelity update
• Weeks? Very low fidelity (or essentially re-randomized/placed in a 'wild' state)

Chunk 'Warmth'

If you're trying to simulate in real time, this looks a bit like a 'warmed cache' question: The chunk gets 'colder' when it's visited less frequently. As this happens, it gradually shifts to lower and lower fidelity/update frequency, and is eventually unloaded. Reload when the player approaches to catch up on the simulation.

Importance of Edits/Changes

It's worth considering how important the player's edits are, both to the simulation, and to the player.

A player spending weeks carefully tweaking a chunk is more likely to notice weird simulation there. So, weight your "chunk warmth" by time spent there by the player. Ditto if they take screenshots in the chunk. :)

Chunk Purity

If you do develop a closed-form (or 'more-closed' form) of your sim, then you can significantly reduce the burden by marking chunks as 'pure' (unedited by the player).

E.g., player passes through a chunk and punches a tree over. If they pass back through two weeks later, will they remember it clearly enough to know whether you just reset the state to being wild?

Another way to 'purify' your chunks is to add entropic forces to your world. E.g., an earthquake could significantly change a landscape, thus wiping out or masking the player's changes there.

Similarly, chaotic AI behavior can make player prediction less effective (at the cost of your world making less sense).

Statistical Simulation / Simplifications

Similar to the 'closed form', this is level-of-detail applied to your simulation mechanics.

E.g. instead of evaluating stats like hit, crit, dodge... Just compare the health and DPS of the combatants directly. (HP/DPS = time to kill, whoever takes longer to die is the winner).

If you want slightly higher fidelity, maybe you introduce an 'HPS' factor (heal per second) to represent all the ways a character can reduce/repair their damage intake.

There are many other approaches, but hopefully something here is useful.

Answer 2

A more reasonable function signature would be

getNewState(initialState, timePassed)

E.g. if your sector has a couple beavers and a river, then if you leave it for a month, there will be a dam and a lake. But if you kill the beavers before leaving the sector, the river stays the same.

Obviously, it's easier said than done. You could either deduce the long-term effects of your AI actors yourself, or use ML techniques to predict the long-term effects of their actions.

Answer 3

What you want is a stateless "simulation", ie that is for any input state and a time variable, you get an ouput state. So that when the player come back you don't have to simulate every step to the output. The simplest example is tree growth, if you plant a seed, you can compute the age based on the state, and from the age you derive the size. It's obviously limited and extremely local.

In order to model complex interaction, you need to design system in an hierachical fashion, for example, it's easy to have a stateless simulation of a planet orbit, to get the position of the moon, which depend on the state of earth, you have to get earth state first.

Instead of earth it can be any abstract model. Consider a character, where the character will be a time t? Well if it's night he might be sleeping but at day maybe he is working. That mean that time can be segmented into chunk too, not just space, and just like procedural space, you can attach unique seed for each time chunk (and time block). Using a time table and the character innate state (like personality etc ..) you can derive what a character do at any moment with a probability time table, at night a thief might try to steal house.

Now instead of just generating character activity based on time chunk, try to set a high level time table for any active agent. Then think about how they overlap at high level, and you then access to simulated interaction in similar way. Now you can use the last trick, correlation. In order to achieve stateless simulation, you can't use "cause", because you would have to generate all intermediate step, which is costly.

Correlation allows you to side step things, ie you find a state then find why AFTER, tune your simulation that it generate the right plausible coincidence, for example, it's hard to find a river for a given topology, therefore the river first, it follow the slope of the topology, and therefore define it. You empire is declining, therefore you generate war, famine, whatever plausible excuse you can from the state. There is a new house, therefore you need new habitant and make one birth, possibly that house is actually built in the future, so it's not visible yet, let the kid grows first.

Now all you need is a starting state, everytime the player modify a store state, it's easy to advance time to another plausible state.