Procedural Map Generator

 

    You might have wondered what inspired the title of my blog. It actually comes from a procedural map generator that I wrote two summers ago. It only took me one afternoon to write it and yet it can generate millions of unique maps in a very short time. It is based on two well know algorithms, Perlin Noise and A*.

    Procedurally generated content is a topic that I was particularly interested in at the time. I was fascinated by how you could write a quick program that produced nearly infinite meaningful combinations based on a few simple rules. One of my earlier projects was a procedural riddle generator which used template sentences and then inserted words of the right category to form a sentence that sounded like the question part of a riddle. Most of the time the riddles were nonsensical but often they were funny.

    The goal of the procedural map generator project was to create a map that could be used as a high level representation of a role playing style video game. The world would contain towns and the player would need to travel along pathways to get between the towns. The towns would be ordered so that the player visits the towns in order. The pathways would need to have ordering also, so that obstacles could be placed between towns to prevent the player from traveling to them out of order.

Example of Perlin Noise

    To create most of the natural qualities of the world I have used perlin noise. Perlin noise creates a set of random numbers that have several local maximum and minimum values with a smooth gradient in between. If we create a 2D set of perlin noise and render these values as a black and white image we get something that looks very similar to a topographical map. Using such a map I can set a threshold value where any point less than the threshold is water and the rest is land. Using another two thresholds we can produce a map with deep water and mountains. Forests and deserts are placed using two newly generated sets of noise since they are not depended on terrain height.
 


     After I had generated the natural landscape I needed to add in the towns and road. The towns I simply added randomly, making sure that they were not placed on water and that they were at least a minimum distance apart. Then to connect the towns I used the A* path finding algorithm to calculate a least cost path between two cities, which I repeated until all of the cities were connected. It is important to note that the least cost path is not the shortest path since the shortest path might make the road cut through a large body of water or a large mountain range. Instead I assigned costs to different types of tiles with grass having a low cost and mountains and water having a high cost. As a result, roads generally travel around water and mountains unless they have no other choice or the alternative route is much longer.

A map generated using the algorithm

    Obviously this is a very simple algorithm and can easily be improved on. One feature I would be interested in adding is rivers, rivers generally travel from high land to low land so a hill climbing algorithm might be a possible solution. I have also though of adding the concept of resources, such as water sources, minerals, lumber, etc. I could then change the locations of towns to be in areas close to resources. Climate and weather are properties I could also try to simulate to have more naturally placed deserts and wetlands.

    In conclusion, this map generator was very simple to write yet produces something that seems very creative in a very short amount of time. Hopefully this gives a better idea of why I choose the blog title, "worlds per minute", especially considering that this was only the first in a series of projects that I am still currently working on that have the goal of creating a large and dynamic virtual world in a very short amount of time.