How do history generation algorithms work?

Question

I heard of the game Dwarf Fortress, but only now one of the people I follow on Youtube made a commentary on it... I was more than surprised when I noticed how Dwarf Fortress actually generates a history for the world!

Now, how do these algorithms work? What do they usually take as input, except the length of the simulation? How specific can they be?

And more importantly; can they be made in Javascript, or is Javascript too slow? (I guess this depends on the depth of the simulation, but take Dwarf Fortress as an example.)

"Can they be made in Javascript?" The answer is obviously yes, but it depends on how quickly you want the results and how complex you want them to be. Dwarf Fortress takes a while too - and it slows down as the world ages! So as long as you want a shallow history, yes you can do it in Javascript, so it depends on how complex you want the history to be. — doppelgreener
– doppelgreener, Commented Jul 8, 2012 at 13:23
@Bane Yes, I mean you can alter how much history there will be in DF. When you start a world, it first randomly generates terrain and then starts aging the world before your eyes and generating history as it goes. You watch it as empires expand and shrink, as terrain changes, as forests grow and recede, as areas become haunted (or no longer haunted), and so on. It progresses year by year (or several years at a time really) before your very eyes. This keeps going until you tell it to stop. The farther in you get the slower the generation gets (due to CPU usage, not game mechanics). — doppelgreener
– doppelgreener, Commented Jul 8, 2012 at 14:07
To be very clear: the older the world is, the slower each year is to calculate. In a young world it will rush through the first few years, in a world hundreds of years old, the next year could take a second or a few seconds to generate. — doppelgreener
– doppelgreener, Commented Jul 8, 2012 at 14:13
Oh, that, I know. By "depth", I didn't mean the amount of years, I meant the amount of events that happen, and the precision of the simulation. You can just keep a number of how many people an empire has, or you can actually have a class called Person, that does chores, goes to the army, etc. Shallow would be letting the size of the empire decide the outcomes of battles, but deep would be having each soldier fight for his own. — jcora
– jcora, Commented Jul 8, 2012 at 15:06

House · Accepted Answer · 2012-07-08 15:06:40Z

First off, there are some hints for history generation about Dwarf Fortress. Someone asked on the Bay12 forums a while back, and a transcript was shared and you can find where the discussion begins by searching for: "our topic today is world generation and history generation".

I don't know exactly how Dwarf Fortress does it, but I'll explain how I'm planning on implementing a very basic first draft in my game. I'm going to use a simple cellular automata. If you look through these Spore prototypes, like cell culture and biome.

enter image description here

These are examples of cellular automations and what they can produce. Essentially I'll create rules for different races. Some examples of rules would be:

Their hostility towards other races
Their climate preferences
Their resource requirements
Their birth rates and life spans
Their desires (technology research, commerce, peaceful existence, world domination)
Their capabilities (structure building, resource gathering, war making, etc.)
And so on...

So, the most critical input for all this to work is a world to plop these races into. The terrain will determine their preferences and expansion. So once you've generated a world, pick random locations in the world where these races would suitably live and let them loose. Now the interesting stuff starts happening. Now that you have land and races with desires and capabilities, you can start building a history. These races gather resources, then structures are built:

Towns in high resource, high livability areas.
Roads connect the larger towns.
Bridges across rivers.
Tunnels through mountains.
Fortresses near the front lines of expansion in response to battles.

Any structure can be raided/conquered by other races. The longer a structure (like a town or fortress) exists in history, the more defensible it is, the harder it is to take over. And the more desirable it is for races that want control. Battles are waged where races meet (at at least one is hostile). Battles are named after landmarks or nearby structures, or if the battle is significant or the landmarks are not named, the landmarks are named after the battle.

Roads, bridges and tunnels are expanded through commerce and resource transport. Each has a maximum throughput that can increase with resource expenditure. Building a stone fortress in the middle of grasslands? Those roads are going to get heavy use transporting the required stone. They'll become larger and get a name.

Natural disasters occur, affecting populations and the course of history. Earthquakes might reduce a town to ruins or collapse a tunnel. A flood might wash out a road or bridge.

It's not as in-depth as Dwarf Fortress, but it's a start. Now as you can imagine, (and as Johnathan Hobbs mentioned) the more these races expand, the more cells are being simulated. Not only are more cells being simulated, but the simulations are more complex as there are now structures to build/maintain, battles to wage, commerce to... commerce, and so on. This gets heavy for any language. Javascript might slow down sooner. However, you can always sacrifice complexity for improved speed.

It's all a simulation (albeit complex), you're just recording the important events along the way and calling it history.

I also just found a Bay12 forum post for people brainstorming how to make the Dwarf Fortress world generation faster. I haven't read through it, but it may provide some hints if you ever run into issues with your implementation being too slow.

Thanks Bane. Maybe not always, it just happens that people ask questions I think I know something about. Thanks for giving me the opportunity to think about it more and get something written down :) — House
– House, Commented Jul 9, 2012 at 3:23

voithos · Accepted Answer · 2012-07-23 17:36:45Z

Just as a side point, JavaScript isn't as slow as you might think.

The browser developers have spent a lot of time and energy in optimizing their JavaScript engines. The benchmark that I linked to shows that, out of the benchmarked tasks, in the median, JavaScript was only 5 times slower than C, which can't be said for some other interpreted languages. And the lower bound is even more impressive: on par with C.

Of course, language benchmarks don't really mean much - you could probably find counterexamples using a different benchmark. But the point is that JavaScript is pretty fast. No, it isn't C or C++, and it doesn't try to be. But it's good to not get stuck in the "interpreted language == slow" mindset, because for any task of nontrivial complexity, the performance is going to matter more on algorithm design and less on language choice.

_{I was actually going to write all this in a comment, but I ran out of space.}

user29687 · Accepted Answer · 2013-04-18 05:11:18Z

1

Yes, it can be build on javascript, check proyects like ASM.js, which get almost 2x slowest speed than C. If you take care of multiple cores (using webworkers) it can be even faster than the DF (in terms of resources), which is monocore right now.

answered Apr 18, 2013 at 5:11

user29687

111 bronze badge

Add a comment |

Stack Exchange Network

How do history generation algorithms work?

3 Answers 3

You must log in to answer this question.

Hot Network Questions

How do history generation algorithms work?

3 Answers 3

You must log in to answer this question.

Related

Hot Network Questions