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. Update [2018-08-28] This guide is now part of Delaunator.

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.