Map generation misc notes

 from Red Blob Games
11 Sep 2013

 1  Generate-and-test vs constraints#

The generate-and-test approach to things is to generate some things, then test them to see if they match the characteristics you want. For example, you could say that you want maps where the two players have an equal number of iron deposits. You can then generate a map, and check where the iron deposits are, and whether both players have sufficient quantities of iron.

The constraint approach to things is to only generate things that match the given constraints. For example, you could write an algorithm that generates only maps that have an even distribution of iron deposits.

Typically generate-and-test is easier to write. You can separately write a map generator and a map tester. You can reuse the map generator with different tests, and you can reuse the test algorithm with different map generators.

The problem is when the number of maps matching the constraint goes down. If 1 in 10 passes the test that’s ok. You generate 10-20 maps and one of them is going to pass. But as you add more conditions (for example needing iron distributed and water distributed and wood distributed and so on), the chances of all of them passing goes down, and you might need to generate thousands or millions of maps to get one you like. So the constraint approach, although harder, allows you to generate just the types of maps you want.

You can mix the two approaches. You can start with tests, then if it becomes too slow, turn the most troublesome tests into constraints.

My experience with midpoint displacement and Simplex/Perlin noise has been that it lends itself to a generate-and-test approach. I might want two mountain ranges, but the noise function may or may not produce it. So I hit “new map” repeatedly until it looks good. The Voronoi/Polygon map generation approach was my attempt to use constraints instead of generate-and-test. Just about every time I click “new map” it looks pretty good. It’s just a lot more work to do things that way, and it’s often better to do that after you know what your gameplay constraints are.

 2  Noise vs physical modeling#

The noise approach to things is to use some sort of function to generate the map. There are some nice things that come out of this. Some noise functions let you generate an infinite map. Some noise functions let you generate part of a map without generating the whole thing.

The physical modeling approach to things is inspired by physical processes such as volcanism, tectonic faults, weather, rain, and erosion. These typically run on the entire map at once, so do not easily work with infinite maps or partially generated maps.

I find the noise approaches unsatisfying at the large scale. But they seem to be fine at the small scale. I like physical modeling, not necessarily for realism, but because the maps can be more interesting, and the players can see features that they can identify with. It also depends a lot on the game. If the player is going to see the world map, then the noise functions often produce bland maps. But if the player doesn’t see the world map, that same map might be just fine.

Unfortunately often times when I pursue physical modeling, I end up doing a lot of tweaking or generate-and-test. I have a tendency to go overboard in seeking realism. In future projects I’m trying to be more aware of this. I find it helps to write down the gameplay constraints and keep that in mind when working on the maps.

Email me , or tweet @redblobgames, or comment: