Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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

share|improve this question
3  
"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 Jul 8 '12 at 13:23
1  
He means "at the level of Dwarf Fortress",as in scale. –  Byte56 Jul 8 '12 at 13:56
1  
@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 Jul 8 '12 at 14:07
1  
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 Jul 8 '12 at 14:13
1  
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. –  jco Jul 8 '12 at 15:06

3 Answers 3

up vote 21 down vote accepted

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.

share|improve this answer
    
Great and informative as always, @Byte56. :) –  jco Jul 8 '12 at 15:09
1  
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 :) –  Byte56 Jul 9 '12 at 3:23

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.

share|improve this answer

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.

share|improve this answer
    
Thanks, really, +1 for the links! –  jco Jul 10 '12 at 19:16

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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