#random map generation

A Python Implementation of Amit Patel's Polygonal Map Generator

Early last year, I took some time away from my game to work on a random map generator, and not for a first attempt. One of the earliest things I had wanted to create in Python was a map generator, but, lacking any idea of how to do it and anything more than a modest talent for mathematics, it never came to much. And then, last March, I give it a third try, this time based on RedBlob Games' very good tutorial-demonstration essay, constructed in ActionScript. (ActionScript, which I know bits and scraps of but have been away from for years..)

I took about half a year out and worked on creating a Python implementation of that code (borrowing from some other sources as well and leaning on the mathematics knowledge of my brilliant girlfriend), and although I doubt that this code will lend itself to my current game so far, it did prove to be a very constructive learning experience. (If you have arrived here looking for the code itself, I imagine I will post it once I get it to some presentable state, whenever that happens. Please look forward to it!)

Here is a point-form description of how the maps are generated (although the previously-linked essay describes it much better).

The map generation process takes place in three main phases:

- 0. Random point selection and Voronoi diagram generation.

i - Random points selected using Python's random.sample() method.

ii - Diagram setup.

iii - Voronoi diagram and Delaunay triangulation generation by Fortunes algorithm (the steepest part of the learning curve goes here).

iv - Diagram resolution.

v - Lloyd relaxation and diagram regeneration (repeat from (ii) for n steps, using Voronoi cell centroids from current diagram relaxation).

vi - Generate 'noisy' borders.

vii - Resolve cell perimeter points.

- 1. Water body propagation and elevation profile generation

i - Determine land-water cell ratio; diagram border/ocean configuration.

ii - Distribute water to starting ocean and lake cells.

iii - Initial water cells pass surplus water volume to their neighbours (recursive).

iv - Assign basic elevation values to cell vertices (elevation equal to minimum 'hops' to nearest coastal vertex, less distance over lakes).

v - Scale elevations relative to a maximum elevation (preserves relative altitudes; excludes water).

vi - Apply elevation data to cells (based on the elevations of their vertices).

- 2. Meteorology, rivercourses, and biome assignment

i - Determine runoff corners for cells (rainwater accumulates at their lowest perimeter vertex).

ii.a- Determine rivercourses (non-coastal vertices transmit accumulated water to their lowest-elevation adjacent vertex).

ii.b- I did not have to do it but rivers terminate at lakes, and lakes generate output rivers, and it is all far more complex than I can put into a single sentence. Sorry; I will try to explain it properly some other time. :s

iii - Apply rainfall to cells (base per-pixel rainfall multiplied by cell size) (I want to work out some kind of rainshadow thing here but I have not gotten around to it yet).

iv - Assign 'moisture' values to cells based on the volume of water flowing (and standing) around them.

v.a - Assign biome types to cells based on their elevation and moisture parameters.

v.b - Some biomes overlap, and when they do, choose one at random.

v.c - I added some special biomes which also respond to average incline among vertices, volume of adjacent water or sand, salt, and a few others.

v.d - Some biomes can 'spread' to adjacent biomes if conditions are correct. (This took a bit of fine-tuning)

vi - Assign cells to custom groups based on common properties (biome, elevation, relative location on the diagram, et cetera..).

- 3. I also made a thing that renders the map in 3d, since all the data is there already!

There are a few different ideas that the Patel essay includes, which I have not implemented here yet-- Perlin noise looks pretty but I do not know how to make it work in Python (yet). I have not added roads yet either, although it does not seem over-hard compared with the complexity of rivers. I am still experimenting with different map generation geometries, with various degrees of success. The Voronoi diagram generator still has some strange and infrequent flaws I do not know how to resolve (or, in fact, even how to trigger or reproduce), and the noisy-borders math implementation I have set up creates some aesthetic issues here and there (most noticeably on the borders of dart-shaped, rather than kite-shaped, Voronoi cells).

I also have had some ideas about how to illustrate the maps beyond blocks of colour (it might be nice if forests had some depth, or at least did not end abruptly at cell borders) and how to group cells up into geometric or 'political' regions, but the time I have dedicated to it has decreased since I returned to the project I have posted here so far. For what it's worth, I have no plans to abandon it, but I also cannot work on both at once so well..

Anyhow, this is the first post in a potential series to do with this map generator. As I add to it or find additional uses, I will do my best to post them here! See you next week! :y