Last week I posted about mapgen4, the procedural map generation project I'm working on this summer. I had been trying to limit the scope of the project, and also shifting my thinking from maps for a game to maps that look pretty. I've been spending a lot of time optimizing and restructuring the code for this. It occurred to me that I'm approaching elevation all wrong.
The standard way to make procedural landscapes is to use a noise function (Perlin noise, Simplex noise, midpoint displacement, diamond square all produce similar output), and then mark everything below some elevation as water. Then use the gradient of the elevation to decide where rivers flow. Noise → elevation → coastlines + rivers.
In mapgen2, made for Realm of the Mad God, I had started with Perlin/Simplex noise for elevation. That was how we made the map for the first six months of the game. We wanted to see how players behaved first instead of spending a lot of time on something custom. It's a co-op multiplayer game where we wanted new players to start playing by themselves, but as they level up, they'd join larger groups until the end when they'd play together in the same area. I designed the map to support this type of play. Players started in low elevations and made their way up. I needed the low elevations to be spread out, the middle elevations to have a diverse set of biomes (for monster variety), and the high elevations to be concentrated. The elevations that worked best for this were volcanic islands with one or two peaks and constant slope. I used noise to generate the coastline only, not the elevation, and then I used distance from the coastline to set the elevation. Noise → coastlines → elevation → rivers.
The original goal of mapgen4 was to support a very different style of game. I found a fantastic paper that showed a different approach to elevation. They started with coastlines and rivers, and then built up the elevation map. I experimented with this but decided that I couldn't make it fast enough for my needs. Noise → coastlines + rivers → elevation. That game was cancelled earlier this year. The new goal of mapgen4 is to make pretty maps that look like they could've been made by hand. I went back to standard noise-based elevation. Noise → elevation → coastlines + rivers.
Noise can produce a wide range of effects — see domain warping, voronoise, noise derivatives from Inigo Quilez, or watch Innes McKendrick's GDC talk about No Man's Sky or Sean Murray's GDC talk about No Man's Sky. However I tend to use it sparingly. The problem is that when I'm playing with noise, I spend all my time playing with parameters. That's okay for a while, but then I want to stop and think about what I actually want.
One thing I realized while experimenting was that the large scale features and the small scale features I want are very different. In fractal-based noise you add up noise at many different scales ("octaves") to produce the final result, but the patterns at each scale are similar. That's what makes it a fractal.
At a large scale, I use noise to make land and water:
Although these look okay, my ultimate goal is to allow you to paint your own shapes, using some variant of this technique.
The next level is mountain ranges. Fractal based noise normally doesn't produce realistic continental mountain ranges. You can get part of the way with ridge noise:
I'm not happy with those so I'll have to experiment more. Here too, the ultimate goal is to allow you to paint your own mountain ranges, like these:
At a small scale, that same noise produces mountains like these:
Although these look okay, they don't match what I see in hand-drawn maps, which tend to have lots of discrete mountains drawn with inverted-V shapes. See Scott Turner's blog for examples. I realized that since I'm not producing these for a game, I should generate elevation to match the look I want instead of trying to adjust the look to match the elevation I have. I used distance fields to generate these mountains, setting elevation = 1-distance:
Another problem I haven't solved is the density of points.
Spacing=
Higher density takes longer to generate so I'm leaning towards a lower density. Higher density makes rounder hills and more detailed rivers, but lower density gives me the mountain look I want. I had been hoping that I could use any density but it's now clear that the look depends very much on the density. Mountains that look angular will look round at a different density. This means the cool look is a sampling artifact! Ugh!
I still plan to use noise, but I'm mostly using it to produce shapes (which can be further edited by the user) and then using distance fields on those shapes to control the elevations. I'll then use a small amount of noise on top of that to add variety. This is my rough plan:
- Use Simplex noise to generate a coarse land/water shape.
- User can edit the shape by painting land/water.
- Refine the land/water shape with Simplex noise.
- Use Simplex noise to generate coarse mountain ranges.
- User can edit the mountain range shape by painting/erasing.
- Generate coarse elevation using distance fields on the land, water, mountain shapes.
- Generate individual mountains with distance fields on blue noise points.
- Refine the elevation with Simplex noise.
I had hoped to figure all of this out this week, but I realized I can't properly evaluate the fine level elevation details until I get the coarse elevation working. I decided to switch gears and work on performance and code structure in order to enable user-editing. My initial code took 5500ms to generate a map. I've gotten this down to 600ms. For user-editing I'd like to get this down under 100ms. There's more optimization to do!
I've also been following the Wonderdraft project, which has a cool map painter interface. What I'm doing is more complicated and less flexible, which makes me wonder if I'm on the right path. Why complicate things to take away flexibility? I think this gets back to the uncertainty around my goals. Without a specific game in mind, I find it hard to evaluate the map generator.
Post a Comment