The map IS the territory

OK, so I’m at the point where I have to create the map to fill the tiles to play my game on. To do that, I need a map generation technique.

There’s a couple of conditions to any technique I choose:

  • it has to generate a random world map which tiles in the x and y direction
  • it has to support the creation/generation of coastlines and mountains. The other biomes will be generated from those two (in combination with a self chosen prevailing wind direction); the mountains are surrounded by hills, and these combined with the prevailing winds give me a rain shadow to place the deserts. The underlying data structure must also support the generation of rivers going to the cost and lakes/oases on the way.
  • This is going to run on mobile phones, so the data structure has to be able to run within a decent time frame and use a limited amount of memory.

I’ve already decided how to represent the final map; I want it to look like cartography, like a fantasy map instead of a realistic map. To do that I have some post processing thought out which I can apply to the tiles. But that means all I need to get from my map generation process is a heightmap, which simplifies the requirements.

So, after some research, it seems there are a number of techniques which could apply:”

  1. a basic diamond square routine: you take a 2D array of floats with possible values between [-1,1] and fill it with 0’s. Maybe prefilled with lines of 1’s to ensure mountain ranges. Then you take the edge vertices of a square and apply random + or – noise to the value of that vertice. Then you take the midpoints of that square (this is the diamond step) and do the same, taking into account the heights of the surrounding array entries. The good thing about this technique is that you only need an array of n by n filled with a single float.
  2. a fBM (fractal Brownian Motion) approach; here you would need to fill each array entry with three floats and apply a Perlin Noise function to each node. This could be modified to get a system where you would only need one float, but that would require a bit of a re-write. The advantage to this system is that you can evaluate each array entry separately. The disadvantages are a higher memory consumption. This is offset by the fact that you can dis-assemble the array into subarrays the size of each tile and process them separately, but you would still be using an array where each entry has three floats. Trying to create an algorithm which just takes one float per entry would not look differently and it would take time to see if it looked decent enough and it might not work in the end, which would be time wasted.
  3. creation using Voronoi cells, as described here: Somehow, that seems like massive overkill, as there is a lot of information I would not be using and would discard, as well as the fact that I would have to input a lot of rules which in the end I wouldn’t be using after map creation. But it sure does look nice 🙂

I’m afraid I’ll just have to try out all three options to see what the reults look like and what kind of time it takes to generate what I want…

This entry was posted in android, programming and tagged , , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s