Website updates

For the most part my website setup has been the same since 2011 when I launched www.redblobgames.com. It's a static site served by nginx. I'm currently working on two updates:

  1. I'm (finally) setting up https. This has been more of a pain than I expected.

    I think I have OSCP working. I didn't set up ECDHE but may have that. I didn't set up DHE or ECDH. No POODLE or BEAST. Somehow got P-256. I have PFS. I'll do HSTS later. Didn't set up HPKP but it may be obsolete anyway. Can't set up CAA with my DNS provider. No RC4. I have ALPN, NPN. I have CORS. Don't need SRI. I have XFO and XXSS. I have CSP but don't like it.

    I have acronym overload.

    I'm also updating my internal links to link to the https version.

  2. I'm (finally) learning responsive design.

    I have pages going back 27 years and I've been making layout changes less and less often. Every time I change something it takes a while to go back through all my pages to make sure it works on all of them.

    My older pages like polygon map generation are designed for a 400 pixel width. I had designed that layout to support desktop computers back in the 1990s. As I worked on more visual pages the 400 pixel width seemed limiting so I designed newer pages for 600 pixels. For mobile, I told the phone to treat the page as 640 pixels wide, and scale it to fit. I haven't updated that layout in years. I experimented with wider layouts for the probability page and the hexagon page (both pages switch to a two column layout when the browser is wide enough) but for the most part I've tried to stick to the 600 pixel width. It's simple. It works.

    In the past few years browsers have quickly added features like flexbox, grids, calc(), scaling of images, and high-dpi. I've seen some neat layouts using these features, and it would let me do several things I've wanted to do but couldn't figure out. I want more flexibility in my page design than a single 600 pixel column. Lots to learn!

    I'm also strongly considering dropping custom fonts. I don't think they're adding that much right now, and they slow down page loading. I'm also considering using serif. Back in the 1990s serif fonts were a poor choice, as screen resolutions weren't high enough to render them nicely. But today? After a decade of 1024x768 there's been a sudden increase in screen resolutions / density, so I should consider serif fonts.

Labels:

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

Noisy edges

For some of my map generator projects I use a polygon mesh structure. Sometimes I want to hide the polygons by changing their straight edges to be "noisy":

When I wrote about this in 2010, I didn't explain it that well. Now that I'm revisiting map generation, I decided to write a longer explanation. While doing so I studied the code from 2010 and found that it had a bug and also was somewhat convoluted. I decided to use a simpler variant of that, and wrote a page about the simpler variant instead of the original.

This is what the maps look like with noisy edges:

Here's the description of the algorithm, without code (sorry). If you want to see the code, it's the recursiveSubdivision function.

Labels:

Generating details from map sketches

I was pretty happy with the sketching tool from last week but I wasn't sure whether it actually produced the data I needed. I connected several separate projects together to make the sketching tool guide the generation of rivers and elevation. These projects weren't coded to work together, so the page is rather clunky, but it served its purpose. I found that the sketching algorithm needed some tweaks, and the river and elevation algorithms need some tweaks too.

Example of generated rivers

I also extended the sketch demo to let you change the boundary points, which have elevation -1. By default they're at the borders of the map. By removing them from the borders you can get non-island maps. By adding them elsewhere you can generate lakes.

Example of generated rivers

The demo is here.

Labels: ,

Elevation control

The main reason I put the previous experiments on hold is that one of the major goals for the current project is for the game/level designers to have some control over the procedural generation. This week I experimented with a sketching tool that lets you draw mountains and coastlines.


It ended up being a fairly simple algorithm that's fun to play with.
The demo works on touch devices too.

Labels: ,

Elevation from rivers, part 2

I had been working on generating mountains from rivers. I got some cool results, but put it on hold. I had been pursuing things based on what would be cool but had lost sight of the actual goals of the project. Some images:

And here's the writeup. Next time — something different!

Labels: ,

Elevation from rivers

In my polygon map generator from 2010 I built the mountains based on the coastline, then made rivers flow down from the mountaintops. I’ve been exploring a different approach. Last week, I grew rivers up from the coastlines. My goal this week was to build mountains that matched the generated rivers.


I wasn’t able to make something that worked to my satisfaction, but I wrote up my notes, and will try again next week.

Labels: ,

Procedural river drainage basins

In a normal procedural generator I would start with elevation, then figure out oceans by looking at where the elevation is low. For my procedural generator from 2010, I started with the oceans and then build elevation to match. Working backwards led to some cool maps. I worked forwards for rivers though, making water flow downhill, then calculating river drainage basins. I'm always looking for opportunities to solve problems backwards, so this time I'm trying to make river drainage basins first, then make the rivers flow uphill, then build the elevation to match. This paper is part of the inspiration. I'd also like to be able to place some of the rivers and have the system figure out where the rest of the rivers are.


I wrote my notes here.

Labels: ,

Data structure for triangle meshes

Most of my project use grids. I rarely work with polygon structures. When I worked on my polygon map generator project in 2010, I created my polygons thinking of graphs: nodes and edges. People who work with polygons have better ways of representing them, but I hadn't studied them until now.

For my new map generation experiments I'm learning about half edge, winged edge, quad edge, and other data structures. I wrote my notes here.

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.

Voronoi and Delaunay graph diagram
I made my own polygons from Delaunay triangles and plan to use this for a future procedural map generation project.

Labels: ,

Making-of: line drawing tutorial

People ask me how I write my interactive tutorials. I can point at the HTML+CSS+JS but that doesn’t show the process. I decided to rewrite one of my interactive tutorials from scratch, documenting the process along the way.

I originally planned to use a very simple tutorial, but I decided to use line drawing instead. It's a medium sized project for me, with multiple diagrams, multiple layers in each diagram, draggable handles, and scrubbable numbers. I think it covers a reasonable set of the things I use for my tutorials. This tutorial shows how I put everything together.

This is an interactive tutorial about making interactive tutorials.

Labels:

Global optimization applied to game design

Outside of games or even product development, there's a broad problem called global optimization in which you are trying to find the maximum of a function in some space. If we think about a “space” of all possible game designs, then we're trying to find good places in that space. Hill climbing is the simplest approach to function optimization — in each iteration you make a step to improve. The problem with hill climbing is that you run into “local maxima” — you are at the top of your little hill but there's somewhere far away in game design space that's even better. You can't see that far away so you never find those other game designs. Metaheuristics are different approaches to dealing with this for function optimization; some of these ideas also seem to apply to game development:

  • Simulated annealing says: start with big steps early on, make smaller steps later on. This already happens with many games, with early development making larger changes and post-launch being smaller changes.
  • Swarm optimization says: explore multiple places at once. Early on, you can prototype many different related games, and then see what works well and what works poorly. Later in development it's impractical to build many different games but you can explore small variants with A/B tests.
  • Genetic algorithms says: explore lots of places at once, randomly mutate them, and make copies of the best solutions. This seems like what the modding community provides. Let them explore many alternative sets of game rules, and then incorporate the best features into other mods or into the base game.
  • Variable neighborhood search says: alternate between making small changes for a while and then making a few big changes every once in a while. This could mean periodic patches and also bigger changes in the form of expansion packs.
  • Graduated optimization says: first optimize a simpler problem, then use the solution to simpler problems as a starting point for exploring a more complex problem. This happens in games that start small and grow more complex over time.

Are there other techniques you use to avoid your game design getting "stuck" in a local maximum?

Labels: