Edit: The feedback from comments is that the names “teleological” and “ontogenetic” aren't good fits. I agree. There's an interpretation in which the terms work but there are also other ways to interpret them where it doesn't make sense. I had gotten the terms from the procedural content wiki, but in the future I'll avoid using these terms. I've changed the blog text to use “bottom up” and “top down”. Thanks for the feedback.
Long ago, I spent years working on the terrain generation for a game I worked on. I used earthquake faults, volcanoes, soil erosion, lava, river erosion, sediment deposition, water flow, weather simulation, vegetation (affected soil, which affected erosion), forest fires, floods, continental uplift, and other physical processes. This is the teleological approach bottom up approach to making maps.
To make good maps, I'd change parameters and run it to see if the maps looked good. I'd go back and change parameters again and again. Ideally I'd write a search/evolutionary algorithm that explored the parameter space. To do that I need to write code to determine whether a map will look to my eye, and I never did figure that out. I knew it when I saw it.
The other approach to map making is ontogenetic top down. Start with the structure you want to see, and make algorithms produce that directly and fill in the details. This is what I did with last year's simple map generation project. I had seen Perlin Noise, and thought, hm, that looks vaguely like a map — let's see how much work it takes to turn it into a map. Not much, it turns out!
For the past month I've been working on a new map generation project. I wanted island/continent maps with rivers, and Perlin Noise wasn't a good fit for that. I tried making random mountains come out of the ocean, and then using water flow algorithms to carve out rivers. I've been tweaking and testing, tweaking and testing, tweaking and testing, and finally realized that I'm back to using bottom up algorithms. It's incredibly addictive. It feels right: erosion, mountains, gravity, and all the other “realistic” things that form terrain.
The trouble is that I really don't need all of that. I'm working on 2D Flash games, and I don't need terrain; I need maps. It doesn't need to be completely realistic. It just has to be interesting. So I'm stepping back a bit and switching back to the top-down approach. I'm drawing some maps that I like, and then I'll find algorithms that generate maps like those, instead of modeling physical processes that produce realistic terrain. I think this will lead to better maps with less work.
Update: [2010-09-04] See my newer blog post to see the beginning of the new map generation project.
coolio amitp is god
The reddit comments include a note about the terms ontogenetic and teleological, and whether they're backwards. I think that's a fair point. I don't think either term is a great fit but I used them because that's what showed up when reading about procedural generation. It looks like Cowboy Programming has thought about it a bit more.
It could be good "mixed" approach to write an app that takes lo-res hand-made map and generates hi-res detailed map from that.
makc, I agree, that'd be cool.
If I had an algorithm like that I'd actually like to do something different: I'd generate thousands of low-res maps and compute a rating for each based on amount of coastline / mountain / forest areas, and then for the best rated maps I'd generate the high-res detailed maps.
Awesome :)
The "hand-drawn to hi-res map" idea reminded me of Mingos's implementation of the exact opposite: a random map generator that outputs maps that look like they were hand-drawn. The result is quite cool:
http://umbrarumregnum.110mb.com/image/tid/20
One of the posts detailing it: (somehow the embedded images got lost...)
http://umbrarumregnum.110mb.com/node/82
Amit,
I see two things you amy wish to consider. One is your definition of what makes a map intersting. For certain game play scenarios, a map that is dominated by a desert region with few other features can ahve unique and intersting gaemplay; sometimes more so than one that ahs an abundance of features.
This leads me to the second issue. The maps you are generating tend to be good on a larger scale than used for most gameplay. For example, look at a map of North America. It is simialr to the fetures you are tring to create. However, very few game play featuers would use the whole US. If you zoom in to California, the map has a very different look. Each feature is more dominant. Even on this scale, gameplay is difficult to envision. Zoom in to some area about 1/3 of California. This is a scale that game paly is liekly to occur (although small is still possible). At thsi scale each 1/3 looks very different and each 1/3 does not contain all the features of the others. Northern is dominated by mountains. Southern is a vast basin. The middle is mostly defined by the coast and the mountain boarders.
I hope these thoughts help you find a good solution as I think the problem you are working on is fascinating.
Jeffrey, I completely agree that the definition of “interesting” can vary. I think that's one of the reasons I wasn't happy with the way my code was evolving. I was tweaking parameters, trying to make something interesting for my application, instead of trying to describe what is interesting, and working from that. The designers should be able to link map features to game features and game difficulty. For example, a mountainous map might be better for a game level with caves; a desert map might be better for a game level with ancient burial chambers. I am hoping that a more direct approach will be better for game designers.
You're right — scale matters quite a bit. I started out trying to make a “continent/island generator”, but that encompasses a wide range of scales, from Australia to Hawaii! The larger the scale, the more likely there will be more variation in features. But the individual features should also be scaled: rivers, mountains, caves, forests, etc., all should take into account the map scale. A large island might have a handful of rivers; a continent might have hundreds. I haven't thought much about this yet.
Amit,
I've been silently using your Game Programming page as a reference for some time now, and it was instrumental in making me understand two key components of a pet project I'm working on in my spare time: hexagonal maps and path-finding, which I have now working (and, better yet, I *understand*... it is always possible to have it working without understanding it, but it doesn't really scale).
I've been also reading on map generation and I've found both this article and the "simple map" one extremely interesting. For my project I started using a "poor man's" teleological approach ("poor" in the sense that my needs are much more modest and it was basically a way to generate a simple height map in order to end up with a 2D map composed of islands, continents and sea), but while it seemed "easier" to begin with I couldn't get the results I was aiming for, and started to investigate Perlin noise and fBm.
The results seems much more "immediately" useful in that the generated 2D map is much more "realistic" to begin with. All this to say, however, that I'm finding it hard to locate straightforward information (a tutorial of sorts) on working with Perlin noise and fBm: most resources seem to tackle the issue differently, some talk about Perlin noise and include the fBm as part of it without mentioning it, others disregard the pseudo-random nature of it, some contradict each other, etc, etc.
So, this is an area were I'm always hoping to read more about. If you have any pointer to a good resource on the subject I would be thankful.
Hi fsmunoz! You might find this page interesting: http://www.vterrain.org/Elevation/Artificial/ I'm continuing exploring some ideas for map generation and will soon write more about them on this blog.
Post a Comment