Mapgen4: elevation
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.
Mapgen4: goals
tháng 8 16, 2018
mapgen4, maps, project, voronoi
No comments
I've been posting on Twitter but was reminded that I should be posting more to my blog. I don't want Twitter to be the only place to read about what I'm doing.

Back in 2010 I had written an influential article about map generation, making maps specifically designed for one game. I made a Flash demo called mapgen2. At the time I didn't emphasize enough how each of the layers of the process could be different. Many people took the recipe as the way to do it, even though the recipe was specifically for the needs of that one game. In mapgen2 the rivers depended on elevation which depended on coastlines. But it could've been coastlines depended on elevation which depended on rivers. There are lots of different ways to glue the pieces together. In 2017, I wanted to go back and try a different recipe with the same ingredients (Voronoi, elevation, rivers, biomes, etc.). For a while I thought the new project, mapgen4, will do all the things! I experimented with lots of things but the task seemed overwhelming. I decided to step back and limit my scope. I rebuilt the same algorithms with the new framework (HTML5, and more efficient data structures), and launched that as an HTML5 version of mapgen2. Then I put everything on hold.
Five months later, in part inspired by the fantastic procedural map generation work of Scott Turner and Azgaar, I decided I should take another look at my unfinished map projects. I had found lots of cool things during my experiments, and it would be a shame to not use any of them. I made a list of the experiments and decided to drop many of them to limit my scope:
- representation:
- variant of voronoi → YES
- compact triangle/voronoi dual-mesh from graphics instead of regular graph data structures → YES
- delaunator library instead of as3delaunay → YES
- land/water:
- rivers on the delaunay triangle structure → YES
- using rivers to guide elevation (part 1, part 2) → NO
- perlin/simplex noise → MAYBE
- letting you draw your own (part 1, part 2, part 3) → MAYBE
- noisy edges for rivers and coastline → NO
- other:
- biomes → MAYBE
- wind, rain → NO
- territories/nations (part 1, part 2) → NO
- natural resources → NO
- towns → NO
- trade routes (roads, sea) → NO
- named areas → NO
- output:
- webgl (part 1, part 2) → YES
- non-realistic projection ("plan oblique") → YES
- non-photorealistic shading ("aspect" lighting) → YES
- outlines that look hand-sketched → YES
- delaunay triangle rendering → NO
- valley/ridge rendering → YES
- vector format → NO
Ok, that looks like I already have 90% of the work done. But of course, the last 10% takes 90% of the time! The big areas are performance and map quality. The map generation and rendering code from last year is taking 5500ms. I want to be able to change parameters, or draw constraints, and see results right away. So I need to somehow get this down to 100ms. So there is a lot of work to do.
- point selection
- poisson disc is too slow and also was too obvious in output
- jittered grid is fast and less obvious in output, but has artifacts if you jitter too much
- simplex noise per pixel is slow
- switch from per pixel noise to per vertex noise
- cache noise output
- use less noise in general
- memory use
- reuse arrays for mesh (point selection, triangulation)
- reuse arrays for map (elevation, rivers, biomes)
- reuse gpu buffers
- minimize data sent to the gpu by separating static and dynamic data
- river renderer
- used a software renderer last year (screenshot)
- implemented a gpu renderer but it looked much worse (screenshot)
- this seems somewhat fixable though
- implemented a different gpu renderer but it had glitches
- this seems unfixable with my performance constraints
- have yet another gpu renderer designed on paper
- but it only renders major rivers and not every tiny creek
- elevation renderer, currently four passes
- remove elevation+moisture pass → FAIL, as there's a bug in this that is making the output look cooler
- I might be able to turn this bug into a feature, and remove this rendering pass
- remove depth pass → FAIL, as outlines became significantly worse
- remove elevation+moisture pass → FAIL, as there's a bug in this that is making the output look cooler
- for non-interactive use, support many more polygons
For map quality, I had to change direction. Last year's goal was to make interesting maps for a game with specific gameplay needs. But that game was cancelled, and its gameplay needs are no longer relevant. Now my goal is to make good looking maps. Beyond that, I want to make "cartoon" maps like people might draw by hand. Take a look at the Lord of the Rings map or the Game of Thrones map or all the maps on @mythicmaps or /r/FantasyMaps. See how they have mountains, hills, forests, rivers, lakes, and towns, but they don't look like a typical Perlin Noise or Midpoint Displacement procedurally generated map! There's a lot of simplification to emphasize the important features, at the expense of realism.
- projection
- non-realistic "plan oblique" is the primary goal
- emulates hand drawn maps, which have top-down rivers and coastlines but side-view mountains and trees
- uses a shear matrix instead of a rotation matrix
- top down might be nice too
- orthographic might be nice too
- non-realistic "plan oblique" is the primary goal
- lighting
- non-realistic "aspect shading" used in cartography
- hand-drawn shapes have outlines around key features
- decide on point density
- high makes mountains rounder, rivers straighter, coastlines smoother, process slower
- low makes low-poly mountains, but river pattern too obvious (need noise)
- add biomes
- simplified, not realisitic
- river flow should depend on biomes (as opposed to mapgen2 where biomes depended on the rivers)
- handle local minima and rivers
- mapgen2 constructed elevations to have no local minima but mapgen4 doesn't
- canyons: lower elevation of downstream rivers to make sure they always flow downhill
- filling: raise elevation of upstream rivers to make sure they always flow downhill
There's even more. I don't know that the system I have now will work well for the user-drawn constraints. Parts of it were designed for mapgen2, not mapgen4. That's the next thing I need to test. I don't know that it will be fast enough; I should try webworkers. I also need to build a UI. And after I finish all of this, I want to write an interactive tutorial that explains all of these algorithms. So much to do!
If you want to see 100MB of images I've saved over the past few weeks, I put them here.
I hope to finish the map generator in a month, and then I can start on the tutorial.
Games Design Graduation ceremony 2018
tháng 8 10, 2018
Games Design Graduation ceremony 2018
No comments
Delaunator guide
I decided that I should work on a new tutorial this summer. What better than to take all the map experiments I worked on last summer, and turn them into a procedural voronoi-map generation tutorial? As I worked on the outline and some of the initial diagrams I realized this was going to be big: poisson disc, delaunay, voronoi, elevation, climate, biomes, oceans, rivers, towns, roads, natural resourcess, and so much more. And starting with something big often leads to failure. So I needed something smaller.
I decided that I should start with just the structural part: Delaunay and Voronoi, and how they can be used for game maps: poisson disc, jitted grid, delaunay, voronoi, graph properties, neighbors, traversal, lookups, iterators, ghost elements, centroid vs incenter vs circumcenter, rounded regions, subdivision, and more. While working on the outline for this I realized again that it was going to be big. And starting with something big often leads to failure. So I needed something even smaller.
I decided to write a guide for the Delaunator library, which I was using for all of these experiments. It's a fantastic library that outputs two compact arrays of integers, and by cleverly traversing these arrays, you can construct neighbors, Delaunay triangles, Voronoi polygons, and other structures you might want for these game maps. The documentation doesn't say much about how to traverse these arrays, except in the simplest cases. It's not obvious how half-edges work, and how to traverse the half-edges for finding the neighbors of a point, which you need for creating the Voronoi structures. It's best explained with an animation. I'd previously attempted to describe these data structures (here and here) but those pages were specific to my projects.
I wanted a guide to this library that wasn't specific to game maps, so I wrote one using ObservableHQ. In doing so I realized there were a lot of things that I hadn't figured out yet, because I hadn't needed them for my projects. The biggest hole was that I needed to figure out how to handle the (literal) edge cases: the convex hull, where triangles don't have neighbors, voronoi cells are incomplete, and you run into weird cases. In my own code I had eliminated these edge cases by using ghost elements: I surround the map with extra triangles and edges that “wrap around” the back of the map, so that it no longer has edge cases. For a general purpose guide though, I had to explain how to handle them. So that took a lot of sketches on paper and tests with code. Even then, every few days I would find a simpler way of handling them. Hours and hours I spent on simplifying 5 lines of code.

ObservableHQ is interesting. It makes exploratory pages easier to implement. The main feature I liked is that automatic dependency tracking, which I previously wrote about here. It's structured as an array of cells, and each cell know which other cells it depends on, like a spreadsheet. Unlike a spreadsheet, the cells can contain Markdown or HTML or SVG or Canvas, so that you can write a document with them. It was great for iteration, but it wasn't how I wanted to deliver the final product, so I switched to raw HTML + SVG.
One of the tricks I used for the guide was to show the code that was running on the page. I wanted to show sample code, but I also wanted to use that sample code to create the diagrams. The trick is to realize that the <script> tag is an HTML tag like any other. You can style it. By default it's hidden with display:none but you can change that to display:block, and it will show on the page! The sample code on the page uses <script> instead of <pre>.
You can see the guide here. At some point I'd like to get it integrated into the main Delaunator project page. Update [2018-08-28] This guide is now part of Delaunator.
How does this fit in with my overall goals?
- I want to continue my experiments, but I also want to get back to making non-experimental output.
- I want to continue making interactive diagrams, but I'm less convinced that everything has to be interactive.
I think the next natural step after this is to explain how to use Delaunay+Voronoi for game maps. But my experience with this page reminded me that there's lots I probably don't realize I don't know. So I'm going to take a detour and actually produce game maps with these data structures, and then I'll be sure I actually know how to do it. I can write up the algorithms after I make sure they work. You can see what I'm working on on Trello.

🎓



















