Saturday, January 30, 2010

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:

Moisture and altitude maps

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:

Generated map

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:

Generated map with a bit of noise

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:

Rain shadow illustration

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:

Generated map after wind spreads moisture from the west

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

Labels: ,