Saturday, November 16, 2013

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.

  1. Control the number of polygons. I added buttons to set the number of polygons to 500, 1000, 2000, 4000, or 8000. The diagrams were generated with 400; the image at the top used 16,000; the demo defaults to 2000. I didn't include 16,000 because Flash starts misbehaving badly and I thought it better to not have to deal with that.
  2. Use a grid instead of a Voronoi diagram. It turns out that the Voronoi algorithm is one of the stumbling blocks, cited as a reason not to use these techniques. But all the techniques work almost(**) as well with a grid. You don't need to use Voronoi. So I added buttons to use a square or hex grid instead of Voronoi regions based on random points. While I was at it, I also added an option to use either Voronoi on random points, or on blue noise points (the default). In the article I explain why blue noise looks better, but now you can see it for yourself.
  3. Export bitmaps. I had an “bitmap” export before, but it actually exported byte arrays (for example, a 0–255 height map). I renamed that to “byte arrays” and added a true image export, to PNG. It's 2048x2048 without the noise layer, so that you can put it into Photoshop and add your own coloring, textures, features, labels, etc. I don't know if this is the best format but since it was a common request, I've implemented it.

(**) The Voronoi-based maps get randomness from the random polygons, the random river sources, and the random edges. Without random polygons, I needed an alternate source of randomness, so when using a square or hex grid, the demo adds randomness to the elevation. I don't know if this is the best way to add back randomness. If you're using these techniques with grids, you will probably need to experiment some more to find something that works for your needs.

Other requested features that I did not implement:

  • Non-island generation, e.g. multiple continents, endorheic basins, climate variations
  • Non-uniform slopes, or multiple mountain ranges
  • Variable density of point distribution
  • Ocean water depth
  • Export to minecraft map files
  • An island shape editor, or an island shape uploader
  • Proper 3d output (the algorithms were designed for a 2d game so it's not ideal in 3d)
  • Better rendering (I just did the simplest thing, and there are much better possibilities)
  • Separate rendering style for the map view and the zoomed-in gameplay view
  • Smoother transitions between biomes
  • Flora and fauna placement
  • Non-smooth elevations, with features such as caves, canyons, and cliffs
  • A hybrid implicit/explicit generator that could generate details on the fly
  • Physical processes such as erosion, rainfall, wind, river valleys, lava flows
  • Roads, towns, mineral resources
  • Polygon representations of roads and rivers (such as what Path of Exile does)
  • A hybrid system that lets designers alter the output at each step of map generation

Some of these will take time to think about, but more importantly, it's much more useful to design them for a specific game's needs than to design things in a vacuum. I probably won't tackle most of these until I have a concrete project to work on.

Screenshot of mapgen2 demo
Try the new demo!

Labels:

3 comments:

Shlomi O. wrote at November 17, 2013 11:49 AM

Wow!!

Rasmus Praestholm wrote at November 17, 2013 6:12 PM

You know, if you're *looking* for a project to apply some of this awesome tech on, there's no lack of potential candidates :D

I'm lead for the Terasology open source project and we came across your original article more than a year ago - it is still one of my favorites. Got posted in our forum: http://forum.movingblocks.net/threads/biomes-and-map-generation.518/#post-4502

We've had some interesting starts on world gen stuff like a plate tectonic-based generator that makes amazing base heightmaps, a separate climate simulator, etc. But we lack something to tie it all together, like an interested world lead fellow :3

lahosken wrote at November 18, 2013 5:48 AM

Always chant "You must construct additional polygons" before clicking those buttons; it's very satisfying.