Terrain Generation

[therobot]

Hi all,

I was thinking of some old RTS games, namely Age of Empires 2, and I was wondering how they handle the Map Editor that comes bundled with the game.

Essentially, there is a feature in the map editor that lets you create random maps of various types (islands, coastal, plains, desert, rivers, archipelago, etc), given a seed #...

I was wondering how one might build a similar system. My first inclination was to use a perlin noise bitmap, and translate the bitmap data to tile data, but it doesn't necessarily seem so simple, as the map editor i've seen allows for varying map types. For example, a map type of islands would be much different than something like plains. Is it just a matter of cleverly interpreting perlin noise bitmaps differently depending on the selected map type, or is it more complex.

I'm not really looking for code samples here, just straight theory on how others might tackle something like this.

Thanks!

[bluemagica]

Terrain generation can be done with perlin noise, but for something like AOE, I would rather have a custom flood fill algorithm!

First based on the seed, divide the map in zones (zone decomposition), or rather in small portions. Then in each zone, pick a center area, and generate a boundary around it,(you can use the cloudy sky algorithm here), then you flood fill the newly defined region based on seed and map type!

[flyingmonkey456]

i used to do a lot of pro map making in starcraft, so i know a lot about how they do it. first of all, they predraw every tile. there are generally 500-1000 of them so it's a lot of work, but it has to be done if you want a decent editor. there are two things you can do for the next part. either use a lot of code to select a random tileable tile every time you place a tile and put those tileable tiles around it or make layers of every terrain type. that means that you use the tiles to make a layer of solid grass, a layer of solid snow, or a layer of solid water for example. this would also include layers of single angles of border tiles (coastline, cliffs, etc.). you have to make sure that the border tiles match the tiles they're bordering, too. then when the tool passes over a tile, you just change alphas to make it work. it's a lot of work, but it might be easier than the first method. the first one would give the person using it a lot more freedom, but it's up to you.

[therobot]

use a lot of code

Thanks for the reply, guys.

@FlyingMonkey - I honestly have no idea what you're talking about. The topic was more along the lines of general algorithm guidelines, though I'm not sure you really addressed that. Correct me if I'm wrong.

@Bluemagica - This is more along the lines of the stuff I'm trying to get at, but I don't know what you mean by the cloudy sky algorithm. Also, I don't really know how providing a unique seed affects things, really. I don't know much about psuedo-random numbers :( But anyhow, you're advice is a step in the right direction - thanks!

[mousehog]

Yeah AoE was obviously tile based so I am guessing you could pre-make certain terrain tiles and give them attributes like passable or impassable. then painting those tiles on in the editor would be a matter of swapping tiles in your grid.

the water painting in AoE (and other map editors) is kinda neat because they obviously update the graphic of the tile to look right visually as you add and delete tiles. writing that little bit of code would be interesting. this of course is related to flyingmonkey's thoughts.

all in all the biggest effort might be the pre-making of the possible tiles...because (and I'm sure I'm glossing over something here) at first glance it doesn't seem too complicated.

[bluemagica]

cloudy sky algorithm is an algorithm generally used to create a border around a point in a irregular shape, where the shape is based on a seed! But well, if you know any way to draw a circle around a point(instead of using a direct draw_circle type command ofcourse), you can randomise the sin,cos values based on a seed to get an irregular shape!

As for seed thing, umm, I can't really explain, but its just a unique id which you can base your calculations off of! I will see if i can find some reading materials on it!

For now, just think of dividing the map based on map type! then create random island shapes on each sector!

[flyingmonkey456]

@FlyingMonkey - I honestly have no idea what you're talking about. The topic was more along the lines of general algorithm guidelines, though I'm not sure you really addressed that. Correct me if I'm wrong.

okay, what i'm saying is draw every tile that you will possibly need to use. this is called a tileset, in case you're not familiar with map making. the tileset is not going to have one single tile for each terrain, it will have several that can be arranged and rearranged in different ways and still be tileable (move smoothly to the next tile). you would need to define a lot of variables in each tile telling exactly how they interact with other kinds of tiles. what tiles can border them and on what sides, mostly. to make this easier, you'll want to assign each tile a unique number. make sure you have every possibility, they won't only be bordering one tile. for example, let's say you have 3 tiles. we'll call them tiles 1, 2, and 3. if you draw tile one, then draw tile 2 to border tile 1, it will look good with only those tiles. but then you add the third tile and you have to make it tile with the other two. but it can't attach in just one spot. nor will tile 2 only be able to attach to tile one on one side. you don't need to make every single possibility, there would be millions. you do need to make enough that the terrain won't get boring, though. if you notice on most map editors, terrain that you previously put down that is bordering the new terrain will change. that's because there isn't a tile to go in that spot so it changes it so that one can go there. water is even trickier because it moves. you need to make these both loopable and tileable for the entire loop. make sure you keep the ripples going in the same direction and this should be pretty easy, but it's still about 4-5 times more work that plain grass. remember border tiles as well, if you put grass and you put water right next to it the program needs to put a shore tile there. the algorithms for all of this really can't be told to you, you have to figure them out on your own. it's a lot of very complex math with a lot of checking and cross-checking variables several times for each tile. you could always do this the easy way and let the player pick the tiles individually instead of the program picking for them. this would make it a lot more difficult on the player, however. i prefer to do it that way because most map editors are very limited, but it wouldn't hurt to have both for the lazier players :)
i hope this helps, it's all i can give you.

[flyingmonkey456]

wow, even i'm intimidated by that post O.o

[Gnoll]

Want to buy paragraphs? :D

Do you mean generating same tiles with differing looks or generating major sections like islands?

[TOdorus]

the water painting in AoE (and other map editors) is kinda neat because they obviously update the graphic of the tile to look right visually as you add and delete tiles. writing that little bit of code would be interesting.



//mainclass
private var time:int = 0
update(){
time++
var tile:Tile
var tileFrame:int
var w:int
var h:int
var width:int = tiles.length
var height:int = tiles[0].length
for(w = 0; w < width; w++){
for(h = 0; h < height; h++){
tile = tileTypeMap[w][h]
tileFrame = time % tile.animationLength
}
}
}


This is also handy for character movement animations. If you base the frame to be displayed on a general time integer and your character switches from moving down to moving right it wouldn't restart the animation but continue the animation from the same frame. Say a soldier had it's right foot up, he wouldn't restart with it's right foot down.

@blueMagica
What I did to solve this problem is create a typemap, which holds the tiletype (water, grass, playdoh). When a level is loaded a second map is generated, which assigns the actual tile to be displayed. I wanted to be able to destructable terrain, so the engine should be able to decide which tiles to display when one goes missing or changes type (scorched). Another example would be when a player can build walls.

And like Gnoll said: give those words some air to breath, thow a enter in there :D

But that all really wasn't what the initial poster asked. I think this link (http://www.xtremevbtalk.com/showthread.php?t=101479)is interesting mentioning a seeding approach (not sure if this is already cellular automata). The initial poster didn't really seem to get that suggestion judging on his stringy vs masses remark, but I think that would work nicely for what you want to do. Mark each seed with a unique ID and with each iteration check if it's children are a minimum distance away from tiles of the same type with another ID. This way a patch of land or mountain wouldn't come to close to other patches of land or mountains.

[bluemagica]

@Todorus: What problem are you reffering to with the typeMap thing?

@FlyingMonkey456/MouseHog: Please atleast read the main topic, and understand it before answering! theRobot, is not building a tile/map editor! He is not asking how to lay out tiles on a map! We are talking about "Terrain generation", as in AI, where the program itself generates the map, lays out the tiles, and sets all the required Info, using one of the many generation algorithms, and in this case, he is trying to understand the inner-works of seed based algorithms!

Terrain generation is not simply about laying out tiles on a map, you need to consider the rules set for a map, and the data/info required after the map has been generated! For example, in AOE, the map is predefined in "zones", and the "collection zones" like gold mines, deer breeding areas, e.t.c have precalculated paths associated with them, and this is done during the generation part of the map!

[TOdorus]

Really? Wasn't that done after building the map? That way AI could also handle humanmade maps. There's a pdf floating around the net somewhere about terrain handling AI in Age of Empires which I suspect you read, but I can't be bothered to go look for it at the moment :sombrero:

I was referring to the problem of what tile to display: a corner tile, grass tile, a shoretile (grass moving into water). Flyingmonkey was referring to this. A good example of this is wall placement (like in Command & Conquer). When there's one wall it's a horizontal wal. If there's a wall below it, it becomes a vertical wall. If there's another wall right of it, it becomes a corner wall etc. I just use a map storing all the types (in this case wall or not) and let the engine generate the correct tile for display. For me there's a split between the tiles behavior and what the tile looks like on screen. A grass tile is a behavior, but it can have lots of different tiles to display it (because you need border tiles, but sometimes also variation). That's why I code my engines to have the tile object and the displayed graphic be independent of each other. What I mean by that is that I don't code this tile is that frame on a tile movieclip, it's just a Grass object that has never heard of a movieclip in it's short life. A display object takes all the tiles and decides which tile to display.

[bluemagica]

yeh, while placing tiles, i go for a similar approach, for a tile I check it's neighbours and set it accordingly!

As for the paths, yeh I have read that pdf, but I have also read several interviews of the guys the made AOE! I am not saying all paths are precalculated, but collection zone paths are! These are mainly used for automatic placements on the map, so that your town center dosen't end up inside a forest or gold mine with no way to get out! If you notice closely you will see most of the time your villagers, or fishing boats are snapping to the same path when you click on a resource/collectible rather than a tile! This precalcualtion of paths is also used for flocking behaviours while travelling between zones! But, that's a topic for another time!


The methods of AOE may not be the best way to do things, and if you read various design postmortems of modern games, there's a lot of new methods that have been created nowadays (well those are a thousand miles away from my understanding)! So what we do is mostly dependent on our game, but as far as simple automatic terrain generation goes....what I said earlier is the most simplest way of doing it!


Ahh, now i feel like playing AOE again...well I am off to conquer the world...MUAHAHAHA!

[flyingmonkey456]

OHH!!!!! :doh:
i thought he was asking about how they make the editor put the terrain down to that it tiles correctly without repeating too much. lol, you'll have to explain how it generates the terrain for me to get that. i've played AoM and AoE, but never messed around with the editors. what do the maps look like when u randomly make one?
you could probably get a center point and generate a random shape around that using sin and cos at various points around the center. i think someone else already suggested that, though :/

[therobot]

OHH!!!!! :doh:
i thought he was asking about how they make the editor put the terrain down to that it tiles correctly without repeating too much. lol, you'll have to explain how it generates the terrain for me to get that. i've played AoM and AoE, but never messed around with the editors. what do the maps look like when u randomly make one?
you could probably get a center point and generate a random shape around that using sin and cos at various points around the center. i think someone else already suggested that, though :/

I didn't want to sound mean, but yeah..you failed twice in yr replies lol

I know what tilesets are, and honestly, making a map editor is somewhat trivial compared to developing algorithms that generate random terrain.

I've dealt with random maze generation, but that seems like a different beast, really. Thanks for the tips, guys. If I come up with anything interesting, I'll probably keep this thread going.