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.

Screenshot of a procedurally generated map

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:

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

Labels: , , ,

– Amit – Thursday, August 16, 2018

0 comments:

Subscribe to: Post Comments ( Atom )