Map Generator Algorithms: Polygon Map and Caves

     A couple of months ago I posted a blog entry about my procedural map and maze generators. I find procedurally generated content interesting because the results are can often be unique and unexpected. these results are usually based on a few very simple rules, usually inspired by mathematically geometry or natural phenomenon. In the pursuit of creating better generators I am always trying to learn new techniques. Recently I came across a couple of algorithms on the internet that I feel like talking about. They are similar in intention to my map and maze generators but use different techniques and achieve a much more natural result.

Map Generator Using Voronoi Polygons

     The first algorithm is a map generator based on Voronoi polygons rather than on square tiles. A Voronoi diagram is created by randomly placing points and creating polygons that have edges are no more than halfway to any other point. The most common way of generating a Voronoi diagram is using Fortune's Algorithm. The advantage of using polygons over tiles is that they produce a much more random and natural looking shape.

A Voronoi Diagram after 2 applications of Lloyd Relaxation

     After the Voronoi diagram is created the algorithm fills in the map by defining some tiles as land and the rest as water. It then calculates elevation based on the distance from the coast. It places rivers randomly starting in the higher elevations and traveling along edges downward to the ocean. Then it calculates the temperature and moisture level, using the height map and proximity to a river, which it uses to assign each polygon a biome. [1]

     The writer of this algorithm posted a flash demo, and there are source code examples in various languages listed near the bottom of the article.

The final result using 16,000 polygons [1]

     There are a couple aspects of this algorithm that I find interesting. Firstly, I like the idea of using Voronoi diagrams. Before I read about this I had never heard of Voronoi diagrams and now that I now about them I can think of several application that they they might be suitable for, such as the generating streets in a city. Secondly, I like the way that this algorithm was able to generate rivers, and this seems to be made possible by the use of Voronoi diagrams. Had I tried a similar technique in my generator I would probably have ended up with ugly square shaped rivers. I believe this strategy has some clear advantages over the technique that I tried and I would like to try to implement this in the future.

     Well I find this technique works generally well I have also noticed a few problems. One problem is that the algorithm places all of the mountains in the center of the land mass and then has an even slope from the mountains to the coast. While this looks good for some small islands, in general mountains are not placed like this, for example the island of Oahu has mountains on the two sides of the island with a flat area in the middle. Another issue that I find common in most map generators is that they look good from a distance but lack details like sharp cliff faces and jagged peaks. Well this algorithm is a good start, these issues make me want to consider improvements.

A terrain map of Oahu from Google Maps

     I have thought of a couple of map making strategies, based on natural phenomenon, that I believe could be used to improve this algorithm. The first is faulting or the simulation of plate tectonics. A possible faulting algorithm would define fault lines and plates, these areas would then be moved slightly to make the edges discontinuous. I believe faulting could be used to produce features like cliffs.

     Another technique is based on erosion and volcanic eruptions. The map would start with a randomly generated landmass and then randomly drop water on points and have these water drops move down hill toward water. This is similar to how rivers already work in this simulation, with the extension that overtime the rivers cause the steep edges to lower and the shallower edges to rise. This simulates how fast moving water erodes ground which slow moving water deposits. I believe this strategy would lead to steep valleys, canyons and smooth plains. I also believe that volcanic eruptions could be simulated in a similar way.

Cave Generator

     I also read about another algorithm for creating caves. I find this algorithm interesting because it is similar to my algorithm for generating mazes but using a completely different technique.

     The algorithm is very simple and is based on several agents that act as miners, digging out a tunnel. The algorithm starts with a single miner. The miner moves randomly to an uncleared tile and clears that tile. As it moves it randomly spawns additional miners. A miner dies when it is completely surrounded by empty tiles, unless there is only a single miner left in which case it continues to move randomly. The article does not mention an obvious stopping point but say that they stopped the algorithm after 400 miners had died. Once the algorithm has stopped it removes small unmined fragments and then adds water to the empty bottom tiles purely for aesthetic effect. [2]

     The writer of this article also posted a flash demo.
 

The final result of the Algorithm [2]

     There are several things that I like about this algorithm. Firstly it produces very natural looking cave maps. On a side node, the water reminds me of the movie Sanctum which I saw recently. I also like that this algorithm is guaranteed to produce connected tunnels and thus would be useful for using in a game.

     There are a couple of things that could be improved with this algorithm. The first is that it would be nice if the algorithm could be modified to produce longer more dispersed tunnels. Also, the algorithm is described as being on the vertical plane but the minors ignore gravity and the result is a mine that looks somewhat natural but if you were trying to generate a mine that looked like it was built by miners one would probably want to take gravity into account.

     There are a couple of improvements that I would like to try with this algorithm. First, I think this would be interesting to try in 3 dimensions since adding an extra dimension would be trivial. Secondly, in nature many mines are carved out by water, so using technique based on erosion might also produce natural looking caves. Lastly, adding the concept of minerals could be used to direct the miners in a certain direction giving the designer some loose control over the random cave.

     So those are two procedural generator that show that complex scenes can be constructed using some simple rules. I am very much interesting in trying to implemented a version of these algorithms. At the moment I am very busy with term projects and exams, but will hopefully have some free time after. Also, In the future as I find more interesting algorithms I will write a similar analysis of them and tag all of my procedural generation articles so they are easily to distinguish from my other articles.

Refereces

[1] Amit Patel. "Polygonal Map Generation for Games" Internet: http://www-cs-students.stanford.edu/%7Eamitp/game-programming/polygon-map-generation/, Sept 4, 2010 [April 7, 2012].

[2] Noel Berry. "Procedural Generation – The Caves" Internet: http://www.noelberry.ca/2011/04/procedural-generation-the-caves/, April 19, 2011 [April 7, 2012].