Map Generation

A while back, my brother told me about a guy in his class who was busy with a random map generator. I started to play around with the idea as well and I took a careful look at different Perlin libraries in order to come up with some random shapes. After coding around for a while, I ended up with some disappointing results. While Perlin allowed me to generate noise that wasn’t completely random, but in which each coordinate had some relation to the coordinates adjacent to it, the results were made little sense to me, despite them looking quite organic. I basically used the noise to determine elevation. Each negative value meant water, each positive value meant land. Using some simple math I could also assign different colours to different depths and altitudes. Looked kind of neat, but took an awful lot of processing power. I was playing around with this on a twelve hour flight from Amsterdam to San Francisco, and my little netbook felt like it would melt through my tray table.

A random map generated using a Perlin noise library.

What killed the performance was the sheer amount of data points to calculate and display. I rendered it in HTML, using DIVs, later using an SVG, but it really didn’t matter. The Perlin performance was poor and the amount of data points required to get anything fun was gigantic. I dropped the project for a few months, until I discovered a post on polygonal map generation written by Amit Patel and it really opened my eyes. The organic feel that I was trying to achieve using Perlin could also be achieved using a Voronoi diagram and the amount of actual datapoints would be much less. The relationships between bordering polygons was also built into the concept of the diagram and on top of that, the input needed was relatively small (depending on how many polygons you want to generate); just a bunch of coordinates for the polygon sites.

I found several libraries generating Voronoi diagrams, but the one PHP library that I found was a messy port of brilliant Javascript library done by Raymond Hill, who showed me the power of HTML5 and Javascript as a tool for data presentation! (For example; take a look at these mind boggling examples of data visualisation!) I ended up porting the Javascript library myself and creating raw PNG output. It took me a while to really figure out how all of it worked, but tonight I had somewhat of a breakthrough and I managed to solve some persistent bugs in my code. Below is an example of an 1920×1200 image with 1000 randomly generated polygon sites. One of the things to keep in mind is that the randomly generated points have been adjusted with two passes of the Lloyd relaxation to make the points a little more evenly spaced apart.

An automatically generated 1920×1200 image with 1000 random polygon sites.

The next step will be to start figuring out land from water, assigning elevation and creating some sensible colours for the polygon cells. I’ll let my new best friend Amit Patel lead the way in logic; immitation, emulatio, creatio. I don’t quite understand all the logic behind everything yet, but if I take it one step at a time and tenaciously plug away, I’m sure that eventually my brain (made of obsidian, coated in teflon and impervious to the uptake of knowledge!) will eventually make this information his.