Update [2016] I have an updated interactive version of this technique here, with sample code.
My friends Alex and Rob at Wild Shadow Studios entered the TIG Assemblee competition. In the first 30 days, artists create art assets, and in the second 30 days, programmers create games with those assets. Alex and Rob decided to write an MMO in those 30 days. They asked me about generating game maps.
In the past I had generated outdoor terrain maps by using randomness, erosion, and water flow (see the Simblob Project). However there was a terrible trap in there. I spent years refining the terrain generation system, and far too little time working on combat and the game itself. I had fun, but I never finished that game.
Wary of my tendencies to work on one aspect of a game too much while neglecting everything else, I decided this time to do something simple. I started with Perlin Noise. I generated both a moisture map and an altitude map:
To ensure that some areas are dry and some areas are wet, I renormalized the moisture map to try to produce equal areas of every moisture level. I also renormalized the altitude map to produce far more flat and low lands than high altitudes, following a quadratic function. After renormalization every random map has a reasonable mix of land types.
From these I defined simple rules that assigned a vegetation. High altitudes are snowy mountaintops and low altitudes are ocean or beach. In between, the moisture determines how green or yellow the land is. Since most altitudes are not reflected in the map coloring, I added some shading so that it would be easier to see the mountains and valleys:
There were two things I wanted to add. The first was noise. I find noise to add to the visual appeal, and in this case it would also decrease the sharp boundaries between different terrain types. Compare this map to the original:
The second thing I wanted to add was wind. In many parts of the world, wind picks up moisture from the ocean and spreads it over the land. At mountains, much of this moisture is extracted from the wind and dropped as rain:
You can see this pattern in the United States, with winds out of the west dropping moisture in Oregon and California, passing over the Sierra Nevada mountains, leaving Utah and Arizona rather dry. In Australia, the winds come from the east, hit the Great Dividing Range, leaving the eastern coast wet and the interior of the continent dry. In South America, the winds come from the east but don't hit mountains until the Andes, so the rain falls over most of the continent, giving us the Amazon rainforest. I wanted the mountains in the game map to affect the moisture levels. I added a wind algorithm that spreads moisture from west to east and generated this map:
You can see that the dry areas in the northwest are now green, and the southeast, where the moisture is blocked by mountains, is dry. It seems more “realistic” but I think the players don't really notice such things.
In the demo app you can click on the minimap to see the zoomed area, change the number of wind algorithm iterations (then press Update), randomize the map seed (the Randomize button), or type in a random number seed and press Update. I find that 83980, 59695, 94400, 92697, 30628, 9146, 23896, 60489, 57078, 89680, 10377, 42612, and 29732 are seeds that produce decent maps. The demo differs a little bit from what we used in the game but the overall map shape and features are the same.
For Realm of the Mad God we exported the map and then made vegetation and monsters based on the terrain characterstics. The tree density was higher in jungles than on hills, rocks mostly were on mountains, and dead trees littered the deserts. Monsters too were terrain-specific at first, but they ended up spreading throughout the land. On top of the map we added random temple ruins and were hoping to make those areas special in some way, but ran out of time.
Looking back on this project, there were lots of things I did that don't really matter to the players. I tried to make the algorithms “scale independent” so that I could generate maps of different sizes and they'd end up with similar features, but in practice we only wanted maps of 2048x2048. The noise, which looks good in the overview map, looks awful when playing the game, so we ended up smoothing it out. I tried to make a two-step process that would generate the large scale features with one algorithm and the details with a different algorithm, and I never got that working well; I ended up just generating everything with the large scale algorithm. I had a river algorithm that carved out canyons, and I didn't get it working well enough in time for the game contest. I tried several ways to make the edges of the map into oceans (so that players would never reach the edge of the map) but none of them worked out, and players didn't seem to mind reaching the edge. The edges of the map never worked out right because bands of weirdness would form (you can see this in the demo). The simplest thing would've been to cut off the edges.
There were also lots of things I'd like to add, but probably shouldn't because I should move on to other projects. It would've been nice to create a map rating algorithm that could automatically pick out maps that look good (plenty of water, beach, mountains, variety, etc.). But for Realm of the Mad God we just looked at a bunch of maps and picked seed 72689. It was a pretty nice looking map, except the peninsula turned out to be a little frustrating for players, and we don't want the bosses to spawn on islands that players can't reach. For the expansion pack we'll probably just pick a few random seeds that look good and make maps from them. It would've been nice to automatically pick spawn points for players and monsters but those too were just placed manually. It would also be nice if there were some landmarks and regions with names so that the players could talk about where they were.
Try the game and see how different it feels to be exploring the map in the game than it does to look at it in the demo app. For example, the god monsters live on the mountains; it's much easier to see where these are on the map than to figure it out while playing the game. I think the 30 day time limit really helped keep me focused on things that would be useful for players. After the contest was over I found I was spending time on much less important things. I'm planning to stop working on the map generator for now, and only revisit it if there are specific features I need to add. The source is available under the MIT license (however the Oryx tileset is not licensed the same way so the version I put on github uses solid colors instead).
Oddly enough, I was curious about the game's map; I suspected that it was semi-randomly generated, but I wasn't entirely certain. Given the rushed nature of the rest of the game's content, I thought it was also vaguely possible that they had modified a real-world map for game use. This was an interesting read.
Awesome read! This sort of detail is much more fun to us programmers than to the players, but I guess there's no harm done in indulging a bit hehe :) I think that, subjectively, a player can tell that the maps are of higher quality this way than with just noise; even though he can't really say why.
Hm, it seems that you and Jice have been playing with the same stuff! Check out his post on the subject. [Roguelikes FTW!]
http://doryen.eptalys.net/2010/01/improved-precipitation-map/
I really like the wind feature. I think that will give the map a more true-to-life look and feel. I'd like to try something like this but add gravity-driven water that forms streams/lakes.
Thanks for the pointer, Jotaf! It looks like Jice not only has winds for spreading moisture, he also renormalizes altitudes (he uses x^3 and I use x^2). His maps look nice.
Thanks, Scott — I did try gravity-driven water and didn't get it to work. I'm somewhat afraid of working on that because it consumed me when writing SimBlob (http://www-cs-students.stanford.edu/~amitp/games.html) — so much so that I never got around to writing military, combat, game goals, and other things I needed to make it a game. Water flow is endlessly fascinating.
Also, for Realm of the Mad God, we didn't have roads and bridges, so rivers were only for eye candy. In a future game we may revisit this, as rivers can have a huge impact on transportation (both because you can move along them, but also because it's hard to cross them), and that could be a fun game element.
Hi Amit,
Here I am again trying to pick your brain, as it were.
Am I missing something (possible) or are the "Altitude" and "Moisture" labels in the demo switched?
Apropos, a small doubt: is the moisture map created completely separate from the altitude map or is it based on it? I'm asking because I'm planning to follow a similar approach now that I have my Perlin noise height-map working in order to produce different terrain type... a simpler way would be to just use some interval in order to create forests and the like, but that would not reflect stuff like "forests in hills" and "forests in montains", hence why I'm finding the moisture map interesting (even if I don't implement the wind).
Just as a side-note I'm also struggling with the need to surround the map with water. While possible when I was using a method that used interpolation upon a provided "base noise" (since I could just tweak the base noise to have certain values at the borders) using Perlin noise pretty much destroyed this possibility since the value of each coordinate is completely dependent on the algorithm itself.
Cheers, and thanks again,
Frederico
Scott, an update: gravity-driven rivers worked really well when I generated the altitudes to eliminate local minima, and ensured that there are oceans for the rivers to flow into. This is in a new map generation project, which I'll post soon.
Frederico, I believe the altitude and moisture labels are correct in the demo. The moisture is white for the ocean/lake areas. Altitude is white for mountains and black for oceans. However, I didn't put in gamma correction so the altitude bitmap may look too dark (too many black areas).
Initially the moisture map is completely separate from the altitude map. However the wind simulation uses the altitude map to influence the moisture map, so by the end of the simulation they are connected. I think it's fine to have them completely separate. Try setting the wind iterations to 0 in the demo to see the effect. I put in wind because it makes the maps more “realistic”, but when people played the game, it didn't seem to matter, so in my next map generation project I don't have wind. Having both altitude and moisture leads to more variation in terrain types (like forests in hills/mountains); it's an easy way to make the maps more interesting.
I tried several different approaches to surrounding the map with water, but didn't find any that worked well when I started with Perlin noise. For my new project, I'm not using Perlin noise at all. Instead, I'm starting with a randomly drawn coastline, and then setting altitude to be distance from coastline, and moisture to be distance from river. You can see some initial results here (click on the map to generate a new one). If you want to see the unfinished (Actionscript) code, it's in prototypes/voronoi_set.as.
Amit,
Thank you for the explanation, highly appreciated.
The new map generator looks extremely good, I'm sure to keep an eye on it! I especially like the way the rivers and lakes are represented, along with the natural-looking altitude. I'm curious to see how would it work in a more "massive" scale, i.e. with several large landmasses.
Cheers,
Frederico
Really cool! I've been wanting to play with procedural generation and this is a step in that direction.
FYI the link to the .as file on GitHub is a 404 :)
Thanks richtaur! Sorry about the broken link. Since August I've refactored the code and made a series of blog posts about it. The code is available here.
how can I run this AS code? There's not fla file?
Hi Crirus: There's a .swf file at http://www-cs-students.stanford.edu/~amitp/game-programming/mapgen-realm-of-the-mad-god/mapgen.swf and an .as file at https://github.com/amitp/mapgen . I don't use the Flash IDE so I don't have a .fla project file. I use free command line tools (Makefile, etc.).
This is great. I've always had fun with Terragen and wanted to do something like it. This is a great post and I'll definitely try coming back.
I'd love a feature for the rivers and streams to "flow". Walking upstream will make you slower, but walking downstream will speed you up. :D
Hi Anonymous — the polygonal map generator does support river flow, but the flow information isn't being used by any games (such as Realm of the Mad God). I agree, it would be nice to use that data in a game.
Hello there,
I have a question - I've checked the terrain generation demo (the latest one, using voronoi and not perlin). Everything looks cool but I have a problem with the altitude - whole terrain seems like a big iceberg starting from low (ocean-close coastline) to high (far from ocean, mountains).
For my project, I need a terrain with more realistic feel, so I need vast flatlands (low hills or just mostly flat land), sometimes uplands and some mountain ranges, but not necessarily being generated in a "concentric" way from ocean to middle. Did you think of any algorithm that could be used with your method to create terrain that would look more like what I described?
Thanks a lot for any feedback :)
Hi noizex,
Yes, this is something I want to do as well. The first trick is to use a non-linear elevation map. Normally I equalize elevations distributions evenly from 0.0 to 1.0 (see the redistributeElevations() function). Instead make low elevations much more common than high ones, using sqrt or some other function. In my (unpublished) experiments, the low elevations ended up much flatter, and the high elevations became much steeper.
In my original code I had non-centered mountains, but switched it to centered because that's what Wild Shadow needed. In assignCornerElevations(), I was adding a variable amount depending on the direction; now I'm adding a constant amount. However I only had one mountain range; it was either on the left or the right. The next time I work on maps I'd like to generate more interesting mountain ranges.
Hi,
Thanks for quick reply! :) I'm very interested in this topic and I really like your approach. I'm thinking about utilising it somehow in my new project which is followup to PrEdiTer project (sample video: http://www.youtube.com/watch?v=J5mRKFzBHUI). We used combined Perlin noises there to first create biome "meta" information and then based detailed sampling on that information.
I'm thinking about using your method to generate such large scale metadata, because pure Perlin makes it impossible to generate anything else than some terrain features - no rivers, no special things that can be placed procedurally. I'm still not sure how and what data to use from such voronoi bitmap and how to base Perlin detailed function on it. Additional difficulty is that I need 3D volume data for my voxel grid that is then extracted to form mesh that can have overhangs, caves and such. But for now I'll aim for something that is 3D but resembles heightmap more, because its easier and should be faster because I can determine highest point at any coordinates and generate air automatically above it. With 3D noise its not that easy because somewhere above there can be overhang and I wont know it until I process every possible block upwards at that coordinates :)
Anyway, back to topic - if you have some ideas how to use your method with that kind of terrain I described, it would be great if we could contact via e-mail. I'll really appreciate any help on this topic.
Hi noizex, yes, I think it'd be interesting to use the polygonal map approach to generate large scale data that then feeds into the parameters for the noise function, instead of directly generating biomes. I've tried a few experiments along these lines but didn't get something that worked well enough to share. I couldn't find your email address; feel free to contact me at amitp@cs.stanford.edu .
what about dem rivers
I see you have a function carveCanyons, but you don't use it?
Hi Anonymous, yes, from the code you can see that I experimented with rivers, but I didn't get them to behave how I wanted them to. Rivers didn't get implemented until version 2, which you can read about here.
Great post! I think this could serve as a base for games where the envirnoment affects the gameplay. It wouldn't be too hard to extend this generator and implement a wheather system, am I right?
Is this project still active? Great maps! Wanted to see the game :)
Deian: the game is called Realm of the Mad God and you can find it on Steam. :-) However, it no longer uses this map generator, as we replaced it with a much better (and also open source) map generator. https://www.realmeye.com/wiki/maps-of-the-realm
Post a Comment