2D tile map generation

Question

For a 2D tile engine I'm working on map generation algorithms. I tried heightmap generation :

• hill generation
• Perlin noise
• Diamond-square

Suitable for tile maps that have a height component but I have sprites like grass, sea, desert and they should be placed like :

• everything starts from ocean
• islands are placed in the middle of the map (this is where algorithms that I tried failed mostly)
• deserts are generated (they should be like random spots around)
• mountain and hill chains are spawned (they should be like snakes)

What approach should I try?

I solved deserts, hills and mountains (for example mountain starts from a point then follows a direction with a chance of turning) but I'm failing with the generation of islands (which should be customizable to be just a pangea or many degrees of size).

I'm looking for something like the Civilization algorithm:

Thirteen

At the time of asking, I don't think this existed. Nowadays, there is gamedev.stackexchange.com – Roche

Answer 1

[hill generation, perlin, diamond square] ... this kind of algorithms seems suitable when dealing with tile maps that also have a height component but this is not my case.

But it is your case. Mountains are higher than plains, and plains are higher than water.

                        ___/
                    ___/ ___ Mountain cutoff
                ___/
         ______/
    ____/ ___ Water cutoff
__/

You can quantize your data so that if it is between one set of levels, it is counted as one type of tile, whereas when it is in a different range, it is a different type of tile. You'll be throwing out some detail, but you'll still get outlines that match the type of noise that you're generating.

It'll probably take a good amount of tweaking, and will require you to generate other land features (besides impassible mountains) yourself, but you'll have to tweak a lot with any content generation solution.

Candlemaker

If you want more info on procedural content generation algorithms, techniques, experiences, etc, I recently found this wiki page. It seems like a great resource, and covers the hightmap algorithms you mentioned in your question. Not my site, nor am I involved with them in any way - it just seems awesome so I wanted to plug it :) – Candlemaker

Answer 2

I used an approach which others have referred to as using "ants" for creating the random terrain. A description of the approach used:

First, I generated a tilemap by using a twodimensional rectangular array (x,y) of a specialized tile class. The tile class holds tile related information such as drawpoint, and terrain type.

Then I created a special "ant" class, which can be thought of as an invisible entity that takes "steps" around the tilemap. Every time the ant moves to a new tile, the underlying terrain type is changed. The ant can move in 8 directions and it changes direction, every time it has moved one tile. The direction it takes after each step is random.

I spawn either a fixed or random amount of ants with a fixed or random amount of lifetime. Lifetime is the amount of tiles it can traverse / step to before being removed.

To be able to control what kind of terrain is most common, I create an "terrain type" array. This array contains a list of the terrain types (basically just an int). To get equal balance between all types of terrain, you add only one of each terrain type to the terrain type array. If you wanted a certain terrain type to be more common, you would add further entries to the array, with that particular terrain type.

Then when the ant needs to determine what terrain to change, you do a lookup in the terrain type array using a random integer as the array index.

It takes a bit of tweaking the parameters (ant amount, ant lifetime, terrain type array), but I'm achieving some really good terrains so far.

It could be further enhanced by using more sophisticated types of ant classes, that for example traversed in specialized patterns etc. For making believeable islands in a ocean, you'd probably want to modify the ant behavior so they have some constraints in terms of which way to move (so you don't randomly get long "spikes" of land , very dispersed small islands etc).

The below is an example tilemap of a forest, that's generated procedurally by a little app I made using the ant approach. Hope this can set you on your way!

You can get the source of the app (VB.NET) at Github

Kizzykjersti

+1; This is an interesting approach, somewhat similar to Cellular Automata. It seems you'd basically get a random distribution with grouping, which on the face of it seems like what you'd want. I'm don't think you're likely to get smooth gradients with this approach, especially when compared with Perlin noise, tho I feel it might be much more compelling for certain tile types (e.g. trees). As for your "table of numbers", this is similar to my answer for how to weight a PRNG. – Candlemaker