Improving Mapgen4's boundaries, part 3 #
In the last post I described how I investigated and fixed several bugs in mapgen4's boundary points and rendering. I was a bit annoyed at myself because I didn't initially follow great practices while debugging, so it took longer than it should have. But I was also glad I found and fixed the bugs.
One reason I wanted to try a double boundary layer was that I thought it might be neat to "fold" the edges downwards a bit, so that when you look at the map from the side, it'd have some depth. So I tried it, and … it worked! And it was so easy (after I fixed the earlier bugs). I then changed the underground color and added a faint line at the fold:
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.
Improving island shaping for map generation, again #
Back in 2019 I rewrote the island section of my noise-based map generation page. I had high hopes for that rewrite. It was ok, but I was still quite unhappy with it. So I rewrote it again.
Labels: maps
Procedurally generated annotations #
Imagine exploring this dungeon:
Labels: maps
Improving island shaping for map generation #
One of my goals for 2019 is to improve my existing pages. This week I improved the island map section of my noise-based map generation page.
Labels: maps
Mapgen4: finished #
“Not with a bang but a whimper”
Back in July, I started mapgen4, the successor to mapgen2, my Voronoi-polygon map generator from 2010. Back in August I posted that I had planned to finish the map generator “in a month”, and then write a tutorial.
That was three months ago.
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.
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.
Mapgen4: river representation #
I've reached the point in mapgen4 development when I just want it to be over. So I'm cutting all remaining features and am focusing on finishing. Most of the remaining work isn't interesting enough to blog about so I'm going to describe the river representation I started using last year. It's worked very well for the needs of this project. Take a look at the rivers in this screenshot:
Mapgen4: outlines #
Usually when I make a map generator I focus on the underlying algorithms and data. The data will be used by a game project, so the visuals are meant to be informative and not necessarily pretty. For this project I wanted to make the output pretty. I previously blogged about the unusual projection I'm using for the graphics. It allows you to see the rivers and coastlines top-down but see the mountains from the side. There are two other interesting graphical tricks I'm using to make the maps prettier.
Mapgen4: bug fixes #
The past week has been troubleshooting. The biggest problem was water pouring out of my house's electrical panel, but that's not what this blog post is about. I've been working on bugs in the map generator. There are some bugs I've been putting off because I didn't understand them.
The first problem was that rivers haven't been reaching the ocean. This has been a problem for a while, but I didn't want to fix it until I stopped changing the algorithm. I'm mostly happy with the river algorithm now so I decided to investigate. One thing that the Game AI Summit at GDC emphasizes is building debug visualizations; I'm a fan of that technique and tried it here:
Mapgen4: oblique projection #
One of my goals for mapgen4 was to explore non-realistic approaches, both to map generation and to map rendering. I wanted to explain the unusual projection I'm using.
For procedurally generated wilderness maps, it's very common to see a top-down view, often using colors to represent height or biomes:
It's simple to implement, especially in 2D, and it shows the areas of the map, including coastlines and rivers and lakes. You can see where the mountains are, but only because of the color and lighting.
Mapgen4: rainfall #
Last time I rewrote elevation painting. The next thing I wanted to work on was biomes. I'm not actually even sure I need them, but I wanted to try a variant of an approach I had tried in the 1990s and again in 2009:
Mapgen4: elevation painting, revisited #
A few weeks ago I described elevation painting for mapgen4. The idea was to let the user paint areas for mountains, valleys, and oceans, and then use distance fields to interpolate between the areas. After some user testing, I decided to abandon this approach.
When I originally implemented it, I painted mountains and valleys on a minimap. On the main map, I used distance fields to transition between the mountain and valley areas.
Mapgen4: river appearance #
Earlier this week I moved all the heavy computation into its own thread. The rest of the week I wanted to work on rivers. The last time I worked on rivers, I replaced the slow CPU-based renderer with a fast GPU-based renderer. However, the output was ugly:
Mapgen4: elevation painting #
Last week I described the plan for elevation in mapgen4. The goal was to allow painting mountains, valleys, and oceans on the map. I used a jittered grid to pick positions for mountain peaks, and then implemented three distance fields:
- Distance from closest mountain peak. I use this to create distinct mountains instead of noise-based continuous mountains.
- Distance from coastline. On the ocean side, I use this to make shallow water near the coast. On the land side, I use this to keep mountains away from coasts. (not sure I should)
- Distance from mountain ranges. I use this to make a gradual drop from mountains to valleys.
I continued optimizing. The main map regeneration is now around 400ms for the one-time initialization and 120ms to regenerate the map while painting. I implemented a simple paint interface, with small/medium/large brushes and ocean/valley/mountain tools. It works on touch devices too, and it feels pretty good on a tablet.
Mapgen4: elevation #
Last week I posted about mapgen4, the procedural map generation project I'm working on this summer. I had been trying to limit the scope of the project, and also shifting my thinking from maps for a game to maps that look pretty. I've been spending a lot of time optimizing and restructuring the code for this. It occurred to me that I'm approaching elevation all wrong.
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.
Updating mapgen2 #
Back in 2010 when I wrote a procedural map generator based on Voronoi polygons instead of Perlin noise, the goal was to produce volcanic islands with a variety of monsters. I had started with Perlin-based height maps but got too much variety in the maps. I decided to use Perlin noise for deciding land vs water, but use other algorithms for everything else. I wanted the players to start on the beach and walk uphill, meeting other players who started elsewhere on the beach and were also walking uphill. I wanted to always produce islands with mountains in the center, so that the players on any beach would travel the same distance to get to the top. The maps were intentionally unrealistic but they were designed to satisfy the game design constraints. I made a Flash demo to accompany the article.
Labels: maps
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.
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.