Mapgen4: goals

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 emphase 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 2017, I wanted to go back and try a different recipe with the same ingredients (Voronoi, elevation, rivers, biomes, etc.). 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 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 where the river gets its water
  • 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: ,

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.

Delaunator uses half-edges

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.

How does this fit in with my overall goals?

  1. I want to continue my experiments, but I also want to get back to making non-experimental output.
  2. 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.

Labels: ,

Modifying spelling

Back in 2016 I started a mini-project to play with neural networks. I concluded that the approach I used didn't give me enough control over the procedural generation. I wanted to revisit the project and focus on word manipulation (the problem I wanted to solve) instead of neural networks (the tool I was learning). Over the past week I read a lot, played with some code, and learned more about English. I tried modifying the spelling of existing words. Example:

Four skore and seven yirz ago our fatherz brougt forth on this kontinent, a noo nation, konceived in Liberty, and dedikated too the propozition that all men are kreated ekual.

I wrote up the results, including an interactive demo and instructions for compiling and using the software and dataset I found. I don't know what I will do with this, but it was interesting and I hope it's useful to someone.

Labels: ,