Blobs in Games: voronoi

From Red Blob Games's Blog

Improving Mapgen4's boundaries, part 2 #

Last time I mentioned that I made some changes to my dual-mesh helper library. I use it for my Delaunay/Voronoi map and art projects. Part of the motivation was that I want to work on some new map projects, and wanted to fix some of the issues with the library. I then realized I need to test out the changes in mapgen4.

I made a list of mapgen4 bugs I wanted to fix. The main one I'm going to talk about here is that the edges of the map are jagged. Why didn't anyone notice? Because I set the default zoom level to be slightly zoomed in, so that you don't see the edges!

Labels: geometry , mapgen4 , triangles , voronoi

Improving Mapgen4's boundaries, part 1 #

I've been wanting to refamiliarize myself with the mapgen4 code because I'd like to do some new map projects and will want to reuse some of the code from my existing projects.

The first thing I decided to work on was my dual-mesh library. I had originally written it to be a generally useful wrapper around Delaunator. Since then, I wrote the Delaunator Guide, which has all the same functions, but in a way that you can adapt to your own needs. I also realized that by making this library public, I was making it harder for my own needs. So version 3 of this library is going to be primarily for my own needs.

Labels: geometry , mapgen4 , maps , triangles , voronoi

Map generation on a sphere, part 2 #

I spent 9 days working on map generation on a sphere. The first 2 days were geometry: points, triangles, polygons on a sphere. The next 7 days were maps:

• elevation: mapgen4's noise approach looked ok, but I wasn't happy with it, so I switched to using plate tectonics, which looked nice
• moisture: mapgen4's evaporation+wind+rainfall relied too much on a grid, so I wasn't able to use it; I ended up assigning biomes randomly
• rivers: mapgen4's binary tree forest works on graphs, and worked great on a sphere
• rendering: mapgen4's elevation rendering uses outlines and a custom projection which are designed for flat maps, and I wrote a new simple renderer

I wrote up my notes and am going back to working on mapgen4. I'm also putting all the (messy) code up on github.

Labels: geometry , maps , voronoi

Map generation on a sphere, part 1 #

I ran into a showstopper with mapgen4. It unpredictably "freezes" in the sense that inputs have no effect, even though both the map generation and rendering are running. I'm taking a break from that for ProcGen 2018 - 9 days to work on a procedural generation project.

I decided to play with procedural map generation on a sphere. I've long wanted to try generating entire planets instead of flat maps. See this project and this project to get an idea of what I'm wanting to learn how to do.

Labels: geometry , maps , triangles , voronoi

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.

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.

Labels: mapgen4 , maps , project , voronoi

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.

Labels: structure , triangles , voronoi

Polygonal Map Generation, HTML5 version #

Seven years ago I worked on an terrain generator for a game called Realm of the Mad God. We had started out using Perlin Noise for height maps but found that most of the maps we generated weren't a good fit for the game. I spent the summer trying out ideas for making the maps, and discovered that Voronoi Diagrams could form a good “skeleton” for making maps. The combination of Voronoi polygons and Delaunay triangles gave me places for quests, towns, rivers, and roads. I used Perlin Noise for the coastlines instead of for the height map. The resulting maps were unrealistic and inflexible but they were just what we needed for our game.

I'm a fan of sharing math and algorithms so I wrote up my notes in an article titled Polygonal Map Generation, along with a free online demo written in Flash. The response was amazing! I saw lots of projects trying out Voronoi diagrams for their own map generators, and I also saw lots of people using my Flash version to make maps for things like D&D campaigns, stories, and worldmaking.

A year later I decided I should spend a lot more time making interactive tutorials, so I started Red Blob Games, where I've written interactive tutorials on probability, pathfinding, and hexagons.

It's been seven years since I worked on the map generator. I decided I should spend this summer exploring terrain generation algorithms, revisiting the topics I explored in 2010 and expanding on them. I posted these notes:

• Voronoi alternative - I discovered that my map generator from 2010 wasn't actually using Voronoi! I had been using Voronoi during the summer while working on the generator and also while writing the tutorial, but towards the end I tweaked the polygons to improve the rivers, and in doing so I was no longer using Voronoi.
• Triangle meshes - In 2010 I had used an array-of-structs approach to storing the map data, with an explicit graph structure. It used approximately 2700 bytes per triangle. After watching Gino van den Bergen’s GDC 2017 talk, “B-rep for Triangle Meshes”, I learned about more efficient data structures, and wrote one that uses approximately 27 bytes per triangle. That's a 99% savings! I also learned how to eliminate a common source of errors in my 2010 code: edge cases (literally). By wrapping the map around the "back", I can get rid of all the null pointers in the data structure, and the code became much cleaner.
• Procedural river drainage basins - Part one - I had found a cool paper that described making rivers first and then making mountains to match the needs of the rivers. I wanted to try this out! I spent a week playing with rivers and drainage basins.
• Elevation from rivers - Part two - making the mountains. I ran into some issues that were mentioned in the paper but I wasn't able to come up with a solution within my one week self-imposed deadline.
• Procedural elevation - Part three - still trying to make mountains, I decided to give myself another week. In working on this I realized I've been pursuing all of this because it sounded cool instead of trying to solve the problem I actually had. I stopped pursuing the mountains-from-rivers approach.
• Elevation control - One of the problems I was actually trying to solve is giving the level designer some way to influence the terrain generator. I spent a week playing with some simple algorithms, and found something extremely simple and fast.
• Adding details to sketched terrain - In the previous week I had found something I liked a lot, and I wanted to see if I could hook it up to the mountains-from-rivers algorithms. It was kind of cool but not cool enough that I wanted to pursue it.
• Terrain shader experiments - I took a break from terrain generation to play with shaders. I wanted to see whether shaders could be useful for drawing the boundaries between the Voronoi polygons. Using barycentric coordinates, I got some cool effects, but the only one that was simpler with shaders than without was noisy boundaries.

Having time to experiment was great. I learned a lot. I wrote lots of quick & dirty code, most of which I'll never use again. A few parts of it I want to use for future projects, so I went through those parts and cleaned up the code, ran some automated tests, and then improved the design and usability.

One of the things I've been wanting to do for some time is rewrite the tutorial with interactive diagrams, and reimplement the 2010 map generator from Flash to HTML5. Back then, Flash was a reasonable choice, but not so much today. I spent a few weeks on the tutorial but was unhappy with the way it was going, so I put it on hold. I worked on an HTML5 version of the map generator instead. It doesn't have all the features of the Flash version, but it has some features the Flash version didn't have. It's much faster too.

Try out the new version here!

I'd like to get back to the tutorial, but I think it'll be more compelling once I have some new algorithms to share.

Labels: maps , project , voronoi

Alternatives to Voronoi for procedural map generation #

When I think back on my polygon map generator project from 2010, the word I associate most with it is voronoi. I used Voronoi diagrams for spacing the points and also for constructing polygons around those points. Seven years later, I'm revisiting this, looking at the ways in which Voronoi wasn't a perfect match for my needs, and looking for alternatives.

Labels: maps , triangles , voronoi

Updating the Polygon Map Generator demo #

When I published the Polygon Map Generation article in 2010, I wasn't expecting it to get as much attention as it did. It's now one of the more popular pages on my site. I also got lots of feedback and feature requests. I decided to implement a few of the easier features.

Labels: maps , voronoi

Polygon map generation, part 3 #

In the previous blog posts (part 1 and part 2), I described generating random polygonal maps with elevation, moisture, biomes, and rivers. For some games, those maps are sufficient. However, in other games I want to hide the polygon structure. In this blog post I'll describe how to render the polygons into a game map that doesn't look polygonal, and conclude with the demo and source code.

The full article is here. There's also a demo and source code.

Noisy Edges

Recall from earlier that there are two graphs: one for Voronoi corners (1, 2 in the diagram below) and edges (blue lines), and one for polycon centers (A, B) and Delaunay edges (red lines) between them:

I wanted to add some “noise” to the the straight lines. I tried making them move randomly, but sometimes lines would cross, and I realized I needed to constrain them so that they would never cross each other. The second thing I wanted was to make sure that the lines had as much space to wander as possible.

I realized that points A, 1, B, and 2 form a quadrilateral, and I could constrain the wanderings of the line segment to that quadrilateral:

I further divided the quadrilateral into four quadrilaterals. Two were usable for the red (Delaunay) edge and two for the blue (Voronoi) edge. As long as the lines stayed within their allocated space and met in the center, they'd never cross each other. That takes care of constraining them.

The entire map can be divided up into these quadrilateral regions, with no space left over:

That ensures that the noisy lines aren't constrained any more than necessary. (I wonder if these quadrilaterals would be useful for game mechanics.)

I can use any noisy line algorithm that fits within these constraints. I decided to subdivide the quadrilaterals recursively and stitch line segments together within the small quadrilaterals into a complete edge. The result is here:

The noisiness is tunable, and I have examples at segment size 7, segment size 4, and segment size 1. In the map demo I use segment size 1 for rivers and coastlines, 3 where biomes meet, and 10 elsewhere.

More noise

I'm generally a fan of noise in game art, and wanted to add a little bit of noise to these maps as well. In a real game map the noise might reflect vegetation or small variations in terrain. In the demo I just filled the screen with a random noise texture, and smoothed the colors between adjacent polygons:

However, with a bit more random noise, we can generate this (described in the full article):

Here's a rendering with 16,000 polygons, noisy edges, a noise texture overlay, and simple lighting:

Demo

I wrote a Flash demo to explore the generated maps:

The simplest way to explore the maps is to click Random and the various View options.

Try the demo!

In a shape number like 85882-3, 85882 chooses the overall island shape and 3 is the random number seed for the details (random points, noisy edges, rivers, lava). You can type in a shape number and press Return to generate that map. The demo also shows some unfinished features that may be useful for some games: lava, roads, and watersheds.

Source

I've placed the Actionscript source under the MIT license; it's available on github. There's an overview page describing what's in these blog posts, along with notes about the code. I don't expect that the code will be immediately useful to anyone, but it might be a useful starting point if you'd like to use these techniques for making your own game maps. The diagrams are built with 300 polygons, the demo uses 2000, and the code can go much higher, although I've not tried above 16,000.

If you find the ideas or code useful, I'd love to hear about it!

Update: [2010-09-22] I added a noisier rendering, which is described in the full article.

Labels: flash , maps , project , voronoi

Polygon map generation, part 2 #

In the previous blog post I described creating polygon island maps. Given random points, Voronoi diagrams with Lloyd relaxation produce a nice set of polygons. The polygons, their edges, and their corners can be represented as two related graphs. Given a random shape, those polygons can be marked as land, ocean, or lake. In this blog post I'll describe how to add elevation, rivers, moisture, and biomes to make the maps interesting.

The full article is here. There's also a demo and source code.

Elevation

The most realistic approach would have been to define elevation first, and then define the coastline to be where the elevation reaches sea level. Instead, I'm starting with the goal, which is a good coastline, and working backwards from there. I set elevation to be the distance from the coast. I originally tried elevations at polygon centers but setting elevations at corners worked out better. Corner-to-corner edges can serve as ridges and valleys. After calculating the elevation of corners, the polygon elevation is the average of the elevation at the corners.

Water polygons don't count towards the distance. This is both because I expect lakes to be flat instead of sloped, and because this tends to build valleys around lakes, which helps guide rivers towards lakes.

One problem with the simple definition is that some islands have too many mountains and others have too few. To fix this, I redistribute the elevations to match a desired distribution, which has more low elevation land (coastline) than high elevation land (mountains).

Elevations always increase from the coast to the mountains. That means that for any location, going downhill will eventually lead to the ocean. This diagram shows the steepest downhill direction from every corner:

By following the downhill arrows from any location, we eventually reach the ocean. This will be useful for rivers but may also be useful for calculating watersheds and other features.

I had two main goals for elevation:

1. Biome types: high elevations get snow, rock, tundra; medium elevations get shrubs, deserts, forests, and grassland; low elevations get rain forests, grassland, and beaches.
2. Rivers flow from high elevations down to the coast. Having elevations that always increase away from the coast means that there's no local minima that complicate river generation.

In addition, games may define their own use of elevation data. For example, Realm of the Mad God uses elevation to distribute monsters.

Rivers

Rivers and lakes are the two fresh water features I wanted. The most realistic approach would be to define moisture with wind, clouds, humidity, and rainfall, and then define the rivers and lakes based on where it rains. Instead, I'm starting with the goal, which is good rivers, and working backwards from there.

The island shape determines which areas are water and which are land. Lakes are water polygons that aren't oceans.

Rivers use the downhill directions shown earlier. I choose random corner locations in the mountains, and then follow a path down to the ocean. The rivers flow from corner to corner:

I tried both polygon centers and corners, but found that the corner graph made for much nicer looking rivers. Also, by keeping lakes flat, elevation tends to be lower near lakes, so rivers naturally flow into and out of lakes. Multiple rivers can share the lower portion of their path, but once they join, they never diverge, so tributary formation comes for free. It's simple and seems to work pretty well.

Moisture

Since I'm working backwards, I don't need moisture to form rivers. However, moisture would be useful for defining biomes (deserts, swamps, forests, etc.). Since rivers and lakes should form in areas with high moisture, I defined moisture based on distance from fresh water:

As with elevation, I redistribute moisture to match a desired distribution. In this case, I want roughly equal numbers of dry and wet regions. In this map generator, moisture is only used for biomes. However, games may find other uses for the moisture data. For example, Realm of the Mad God uses moisture and elevation to distribute vegetation.

Biomes

Together, elevation and moisture provide a good amount of variety to define biome types. I use elevation as a proxy for temperature. Biomes first depend on whether it's water or land:

• Ocean is any water polygon connected to the map border
• Lake is any water polygon not connected to the map border
  • Ice lake if the lake is at high elevation (low temperature)
  • Marsh if it's at low elevation
• Beach is any land polygon next to an ocean

For all land polygons, I started with the Whittaker diagram and adapted it to my needs:

Here's the result:

These biomes look good in the map generation demo, but each game will have its own needs. Realm of the Mad God for example ignores these biomes and uses its own (based on elevation and moisture).

In the last blog post I'll describe how I get from this biome map to maps like this: (or even this!)

Update: [2010-09-22] I replaced the last diagram on this page with what I originally wanted but didn't finish in time for the blog post. At the time of posting, I used this image instead.

Labels: maps , project , voronoi

Polygon map generation, part 1 #

I wanted to generate interesting game maps that weren't constrained to be realistic, and I wanted to try some techniques I hadn't tried before. I usually make tile maps but this time I decided to make polygonal maps. Instead of 1,000,000 tiles, what could I do with 1,000 polygons? I think the distinct player-recognizable areas might be useful for gameplay: locations of towns, places to quest, territory to conquer or settle, pathfinding waypoints, difficulty zones, etc.

There were three main things I wanted: good coastlines, mountains and rivers. For the coastline, I wanted to make island/continent maps that are surrounded by ocean, so that I don't have to deal with people walking to the edge of the map. For the mountains, I started with something simple: mountains are whatever's farthest from the coastline. For the rivers, I started with something simple: draw rivers from the coast to the mountains.

The full article is here. There's also a demo and source code.

Polygons

The first step is to generate some polygons. I picked random points and generated Voronoi polygons, which are used for lots of things, including maps. Here's an example of random dots (red) and the polygons that result:

The first problem is that polygon shapes and sizes are a bit irregular. Random numbers are more “clumpy” than what people expect. What I really want is semi-random “blue noise”, not random points. I approximate that by using Lloyd relaxation, which is a fairly simple tweak to the random point locations to make them more evenly distributed. Here's the result after running Lloyd relaxation twice:

Compare it to running once or fifty times. The more iterations, the more regular the polygons get. Running it twice gives me good results but every game will vary in its needs.

[2010-09-22] The second problem with the polygons is that some edges are very short. For games where boundaries between polygons matters, having short edges is a problem. We can adjust the edge lengths by moving corners, but we lose the Voronoi properties. Since I'm using Voronoi only to generate polygons, and do not need to preserve the Voronoi properties, I move the corners to the average of the polygon centers they touch. Note: I added this code after the initial blog post, and did not update diagrams to show this step.

Map Representation

I'm representing the map as two related graphs: nodes and edges. The first graph has nodes for each polygon and edges between adjacent polygons. It represents the Delaunay triangulation, which is useful for anything involving adjacency (such as pathfinding). The second graph has nodes for each polygon corner and edges between corners. It contains the shapes of the Voronoi polygons. It's useful for anything involving the shapes (such as rendering borders).

The two graphs are related. Every triangle in the Delaunay triangulation corresponds to a polygon corner in the Voronoi diagram. Every polygon in the Voronoi diagram corresponds to a corner of a Delaunay triangle. Every edge in the Delaunay graph corresponds to an edge in the Voronoi graph. You can see this in the following diagram:

Polygon A and B are adjacent to each other, so there is a (red) edge between A and B in the adjacency graph. For them to be adjacent there must be a polygon edge between them. The (blue) polygon edge connects corners 1 and 2 in the Voronoi shape graph. Every edge in the adjacency graph corresponds to exactly one edge in the shape graph.

In the Delaunay triangulation, triangle A-B-C connects the three polygons, and can be represented by corner 2. Thus, corners in the Delaunay triangulation are polygons in the Voronoi diagram, and vice versa. Here's a larger example showing the relationship, with Voronoi polygon centers in red and corners in blue, and the Voronoi edges in white and the Delaunay triangulation in black:

This duality means that I can represent the two graphs together. Edges are the key. Each edge in a normal graph points to two nodes. Instead of representing two edges in the two graph separately, I made edges point to four nodes: two polygon centers and two corners. It turns out to be quite useful to connect the two graphs together.

With the combined representation, I can now use the Relationships Between Grid Parts sections of my article on grids. They're not grids so I'm not assigning grid coordinates, but many of the algorithms that work on grids also work here, and the algorithms that work on graphs also work here (on either of the two graphs).

Islands

The second step is to draw the coastline. I used a simple function to divide the world into land and water. There are many different ways to do this. You can even draw your own shapes, e.g., a skull island. The map generator works with any division of points, but it forces the outer layer of polygons to be ocean. Here's an example that divides the world into land and water:

A simple flood fill starting from the border of the map can determine which water areas are oceans (connected to the border) and lakes (surrounded by land):

In the next two blog posts (part 2, part 3) I'll describe how I add elevation data to build mountains and valleys, add moisture data for lakes and rivers, render the map so that it doesn't look polygonal, and conclude with the demo and source code. Together, elevation and moisture produce a good range of terrain and map features. The goal is to produce maps like this:

Update: [2010-09-22] Since the original blog post, I added a corner adjustment step to lengthen short edges. Just as Lloyd relaxation improves the polygon sizes, I needed to adjust the edge lengths. The adjustment does not preserve Voronoi properties, but I'm not using those properties so it worked out. I didn't update diagrams to reflect this change. I also improved map rendering and replaced the last diagram on this page. I originally wanted to have a rendering that didn't show the polygons at all, but couldn't get it to work in time, so at the time of the blog post I used this rendering instead. The rendering technique is described in the full article but not in the blog posts.

Labels: maps , project , voronoi