Generating terrain for a video game is almost always done by hand, by artists, over a long period of time, sometimes even going to the lengths of placing each blade of grass that the player will see. This visual design and implementation of large scale AAA video games is the vast majority of their development budgets, spanning tens of millions of dollars that we obviously don’t have.
So we don’t do it that way. We can’t compete with it. Instead, we (like many other indie game companies) cut corners by making the game world generate itself procedurally, writing algorithms for the placement of trees, grass, rocks, rivers, mountains, glowing ruins and evil monoliths. Seriously, we have an algorithm for evil monoliths.
David and I have been arguing since the last post on game terrain about the “binning” of our biomes into the 9 categories. His argument being that it’s an unnecessarily simplistic system for such a potentially rich environment. My argument was, of course, that at some point the simulation is growing so intricate that we’re spending time where we shouldn’t be, and that we’d be far better off improving the game-play than the terrain, but if we’re doing things right, the game-play will be pretty heavily influenced by the terrain, so a certain amount of this makes sense.
So I have capitulated, may the internet have mercy on me. Here’s how the system works right now. (If you don’t think that math functions are cool, this might be a little dry. Sorry about that!)
Where once we had a very Minecraft-like concept of biomes with somewhat abrupt transitions from the mild areas to the cold tundras, we instead store a point for every terrain object in 2d space with axes of temperature and humidity, and a range of values for land fertility that a terrain object can spawn in.
We then make a little voronoi diagram of these points, assigning every possible point in the space to a particular object, so that if we want to gradually shift the temperature of the map to colder as you get further north or south, we can assign temperatures to every game space, and as they get colder they’ll get new types of trees, new ground textures, maybe snow instead of rain when there’s precipitation, and all that. The voronoi diagrams give us the ability to put as little or as much in these 2d maps as we like: the more we add to them, the more rich the world will be, and things just get shuffled around automatically.
The cost for this change is that the possibility space for our terrain (what could be placed for any given combination of temperature, humidity and fertility) gets so huge that we can’t actually visualize it easily. Thankfully though, we can test it pretty easily by generating a whole bunch of terrains and looking for things that appear out-of-place. We still run the risk of having some grass that’s badly coded in XML never appearing in the game, but if the world feels enough more like a real world that you can immerse yourself in it, it’s probably worth it anyway.
So that’s how we know what to place, but we also need to know where to place it. After all, forests are places of fertile soil, but there aren’t trees everywhere, nor are they evenly distributed in rows, and forests usually have a structure. Little trees by themselves often don’t survive, as with long thin bands of trees, but large clumps of trees create a habitat for other organisms which protect and nurture the trees themselves. We obviously aren’t going to simulate all of that, it would take us years and would drive us all insane, but if we don’t pretend we do, then you spend time wondering why the forests look weird instead of thinking about how to abuse them for profit.
I have fallen in love with 2D Perlin noise functions. Basically, you supply a series of values to the function and it gives you a 2D map of values. Properly tuned this function in particular has a really amazing capacity for creating naturally shaped anomalies with really pleasing gradients.
We generate a Perlin noise map for ground fertility, modify it just a bit, then apply a histogram to the map so that we can easily designate the top 35% of values to be forest, the next 50% of values to be grass, and the rest to be barren.
At this point we could call it good, but we have some pretty weird looking regions. Like a contour map, you’ll have weird rings of contours of the anomalies, and that’s just… not how real forests exist. They just wouldn’t grow like that. So there’s one more step.
We generate a voronoi diagram overlay of the map using about a hundred totally randomly generated points. For each of the cells in the voronoi diagram, we average up their fertility values, and if the average of that cell is within the values for forests, it’s a forest cell, otherwise it’s a grassland cell or a barren cell. We still get some of the neat grouping that the Perlin function gave us because some of the anomalies will span a few of the voronoi cells, but we get big clumpy forests with weird shapes now instead of little Dr. Seuss forests. I’m sure I can find a use for those guys somewhere though.
As far as the haunted mines and evil monoliths are concerned, we generate another perlin function for “abnormal activity”, and we skim off the top few (or more) game tiles with the highest values, and we focus our paranormal activities there. The really high-value tiles get some really nasty surprises, and the outlying ones have just enough dangerous and terrifying things that hopefully you won’t keep exploring in that direction unless you really want to.
So… this is a lot of work, not for a computer, and honestly not once you get it all working, but it’s a very sophisticated system, and because of that it’s going to be prone to breaking and being a huge pain in the ass. But the world in which you play a game is so important, and the placement of the smallest details are often the ones that reach us in the most profound ways, that if there’s anything we can do to make these moments happen in just your game, hopefully you will feel like all of this effort was worth it.
Also, again, as always, a brief disclaimer that we may just get extremely pissed off at this process and change it later, and there’s always more that we can add to this if we have time, but I’ll continue to fight feature creep because we want this game to come out one day.
Great update, thanks. Cool to read tidbits of what goes on in game development. You’d think that after at least 20 years of procedurally generated terrain maps (my memory goes back to Civ I, but I’m sure there is older stuff?) there would just be a selection of off the shelf tools that can do this, like 3D engines…
Can you post some screenshots / mapshots of the kind of terrain you are generating? Or even post a couple hundred and lets us have fun pointing you at the really odd ones?
There are quite a few tools out there that’ll just “generate terrain”, but unless you make one yourself, you run into a similar problem as mass-marketed artwork: it just doesn’t seem or feel personal enough, or it doesn’t quite seem to fit the world it’s supposed to represent. You get another flavor of this problem every time you play a game where all of the characters “look like Poser models”.
As to pictures of the maps, definitely, but that’s a ways off. They still need more work from me on the topography side, some texture blending, and more art assets to choose from.
This sounds so awesome! I sympathize with the huge pain it will be, haha. But we do appreciate it. 😀
Thanks!
So, will the grey and the gray men have other evil brothers and sisters? The green guy? The lavender person? The off puce dude?
The blue individual.
No doubt they’ll come in groups.
The yellow civilian.
Having spent the week debugging a (relatively) simple database sync tool I can honestly say that all sounds like a huge pain.
It sounds, as ever, like you guys are really putting the extra work in!
Very interesting, thanks for posting 🙂
The way this is shown, it looks like any given forest will be entirely one kind of tree because the local temp/humidity combination will fall in only one tree’s category. Is that true? Or am I just reading too much into a simplification?
It’s actually typically the case in nature that for a given canopy layer, a forest is dominated by one type of plant.
If we have time, we might play with including random nearby ones here and there, but i think we’ll have enough diversity of tree types and enough temp/humidity classifications in a map that you’ll see a nice amount of diversity. The canopy layer is, after all, just one layer of the terrain, there will also be similar plots of the other layers so not all “willow forests” will be the same.
I give FAR more credit to many art programmers today than most modern art being produced. There has to be something said for the sheer brilliance needed to produce a random world that has enough diversity and design flavor that the player wants to wander and explore for the sake of randomly generated landscape than even game-play.
The testament however is that when it is done so well that even after loving and exploring it for whatever length of gaming time that you dedicate it, you remember it fondly — and when you revisit the game, it seems just as magical as the last time.
Just reading this makes me imagine a world as beautiful as skyrim’s but completely randomly generated. The secondarly overlay of perlin noise (at a much lower density than terrain overlay) is actually quite brilliant. Finding an Cursed Shrine in an ‘enchanted’ forest definitely adds flavor, as well as a the body of an ancient demon in an ice cave.
And I hope that the statistically unlikely but extremely high points still have some diversity so that it might be 5-10 games before you find such a point and even then it has a half dozen (or even a full dozen) different possibilities.
Questions for the Developers
1. Are you planning on letting the modding community have any interaction/access with the terran generation features?
2. Is the engine written to allow empty space as an option? Minecraft sky islands were always a hit, and I don’t see them being any less exciting when trying to build a civilization on them. The average Joe wont want to be tweaking the numbers to get a playable sky island scenario, but if someone could write a mod that tweaks the numbers accordingly (while still maintaining resources necessary for it to be fun).
3. Are there going to be Seeds so that if people experience a really random and fun scenario they can replay it over and over or share it with others (as opposed to sharing the save file generated at start up)?
1: all of the biome data is in XML so you’ll be able tweak it, but no idea how you’ll share that sort of thing just yet.
2: Probably not for release but it’s a really cool idea.
3: We have a plan to help people share their worlds, it’s both ambitious and not yet fleshed out, though, so all I can say is that yes, you’ll be able to share.
I didn’t know salt pillars and icicles count as trees. Science marches onwards, I guess.
But really, I think what you have here is a pretty nice way to handle things. Not necessarily optimal in all areas, but then again something has to be sacrificed to gain something else.
Nice update. I absolutely love biomes, and I can’t wait to see how your experiment fares further along.
Personally, I’m quite in love with simplex noise, if only due to how it scales into higher dimensions, and that it gives similar results to perlin noise anyway, and I actually find it conceptually slightly easier to understand (not that either one is particularly difficult), but that’s just me.
The grey man: cross between slender man and the rake, always in pre-rigging pose…until he takes you
Will it be possible to play on maps that are, say, divided by bodies of water, such as in the case of chains of small islands? Would bridges then be a possibility?
I hereby apply for the position of drummer in Majesty of Noise.
Also: Nice update once again, you continue the good work, both in your work and these updates, sweetness 🙂
I hope that the next post will be about metagame or combat
Thank you from your friendly local botanist for putting so much effort into making the ecology feel right!
You NEVER need to worry about apologizing for talking about math. Math is the best invention by mankind in all of time, and always will be. You can feel sorry for those who are afraid of math and don’t have a mind beyond a three-year-old dolphin, but you certainly are not the one to blame for their ignorance.
A very awesome and inspiring post. I can’t wait to mess around with Voronoi diagrams now!