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: