2D tile map generation
I'm developing a 2D tile engine and at this moment I'm working on map generation algorithms.
I tried the basic ones usually involved in simple heightmap generation like
- hill generation
- perlin noise
- diamond square
but I always get the same problem: this kind of algorithms seems suitable when dealing with tile maps that also have a height component but this is not my case.
I basically have sprites like grass, sea, desert and so on but they shouldn't be placed inside the map according to a generated height but something like
- everything starts from ocean
- islands are placed in the middle of the map (this is where algorithms that I tried failed mostly)
- desert are generated (they should be like random spots around)
- mountain and hills chains are spawned (they should be like snakes)
What kind of approach should I try?
I solved the subcomponent problems (like deserts, hills and mountains) by developing specialized algorithms to do what I needed (for example mountain starts from a point and then follow a direction with a chance of turning) but I'm failing with the generation of the basic islands (which could be customizable to be just a pangea or many degrees of size).
Just to give you a practical idea what I'm looking for is something like the civilization algorithm:
Answer
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
