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: ,

Thoughts on explorable explanations

Conversations with several people over the past few months have led me to wonder about the purpose of the interactive diagrams in my articles. I see lots of interactive diagrams but most are not integrated into text. The interactive diagrams are cool. They make me feel like a pioneer exploring a new medium. They're exciting! I like making them! But … that doesn't mean I should be making them.

Labels: ,