2D Dynamic Terrain Generation.

[mirhagk]

Sweet and simple, basically I want minecraft's terrain generation in a 2D game I am building lol. I want to be able to provide the game with a seed function, and no matter which direction you explore first, or the order that you uncover areas, I want the final output to be the same.

It actually is a system that works similarily, where I have regions that can be dynamically created, and objects are animated/scripted based on which region they are in etc. What I want now is a way to create realistic looking terrain, based off a seed, and have the worlds be truly unique.

I have a couple ideas for this, for instance I can create a sort of randomizing function that will take 3 values, do something with them, and give a good pseudorandom number. I will pass it the x and y of each tile, and the seed value, and have it return a random number for use in the terrain generator.

I also need to know how to create random terrain, I'm thinking some of the things can be created with a random controlled recursive function that will make tiles near it be the same, based again off of it's x and y, and the seed value. I will need some ideas for this I believe.

The other obstacle I see is the regions, since I have split the regions into seperate objects (to make controlling what is animated/scripted/drawn each frame much easier), so the tiles may not neccassarily be able to access it's neighbours (at least not directly). And even if they can, then what about when it comes across a region that has yet to be created?

[DemonWasp]

Here's a relatively simple and common way: http://gameprogrammer.com/fractal.html

And an expansion on it, used in a game called Tribal Trouble: http://oddlabs.com/blog/?p=94

Or, if you're feeling adventurous: http://vterrain.org/Elevation/Artificial/

[mirhagk]

See Demonwasp, your the reason why I love this site lol.

[Insectoid]

Wow, that's actually really neat. The author of the first article mentioned that clouds and 2-D maps can both be generated with the same algorithm and I damn near didn't believe him. I was very pleased when I found out just how simple it was.

[mirhagk]

Actually after reading this article (which is awesome by the way) I realized that this really only works in 3D. Then I was like, WAIT I CAN USE THIS. So here's what I got: (keep in mind this is a top down RPG game, much to the style of final fantasy etc)
So I use the algorithm to create continents or something in the ocean, so each border is always water, then I use the algorithm to raise or lower the value of the tile, and each type of tile will have a range of values that are for it. For instance grass could be 0.1,0.4 and water could be -1.0,0.0. This will basically be using the heightmap and converting it to 2D.

I believe this algorithm works pretty well, and makes the continents tileable (as well having water be the majority of the range will mean that there will be large oceans in areas).

Let me know if you guys think this is clever/good, or if there is possibly a better way of doing it.

EDIT: Oh and to make sure that no matter what order you use the same values are used, each continent will have it's own random number generator, which is seeded with the world seed+x*10000+y (this means that after 10000 tiles up and down, the tiles will start to repeat, so if there is another way to take 2 numbers [x and y] and generate a unique [at least for reasonable values of x and y] number [modded by 2^32] then let me know)

EDIT2: I will also modify this algorithm by making any edge points always equal to 0 (ie whenever a point lies on the edge it will ignore the algorithm and just assign 0 to it)

[DemonWasp]

I'll assume you're using the first algorithm -- midpoint displacement -- and not any of the other ones. What you're describing is more or less just looking at what people do when the algorithm is handled in 3D. In 3D, once you have a heightfield generated (which midpoint displacement does for you) then you can assign "types" of terrain based on slope and elevation.

The simplest way looks something like this:
1. Anything below a given level is underwater. That is, water is at level X, where X is between the extreme points of your heightfield. Obviously, some parts are deeper than others (draw them a darker blue?).
2. The region immediately above the water is sandy shoreline.
3. Above the shore but not yet mountainous is grassy or forested* (deciduous / mixed).
4. Low-mountainous, moderate-slope terrain becomes alpine forest (pine trees).
5. High-mountainous or high-slope terrain becomes "cliffs", or snowy mountains, depending on elevation.

It's up to you whether you have harsh lines of demarcation between these regions, or whether they blend smoothly. You can also be more sophisticated about it (the approach above looks funny when you look at it sideways, because everything is banded), but that's probably not necessary for 2D top-down.

The best part about this algorithm is that you can use it on any scale, and because it can be recursively defined, you can zoom down to any detail level you want (though it only looks realistic for levels between "large island" and "person size"). You can do the entire thing with a single PRNG, with a single seed.

You may want to re-think your seed algorithm. As written, it will not repeat after 10000 tiles in the X direction. It will repeat if you go 10000 tiles in the Y direction and "down" one in the X direction. If you want it to repeat every 10 tiles in either direction, then you want something like "master_seed + 10 * ( x % 10 ) + y % 10;", so that x controls the tens digit and y controls the ones digit. Alternately, "master_seed + ( x + y ) % 100", which is a different pattern. I'll leave extending that idea to repeating after 10000 tiles as an exercise. If you want it to (almost) never repeat, then what you should do is calculate something like "( x ^ y ) mod (large prime number)", which is usually pretty non-periodic.


* You can also generate reasonable-looking forests using this method. Do the midpoint-displacement twice for a given region (or once, and create a flipped / rotated duplicate). Use the second one as a map of "foliage density". Then, modulate that by the terrain heightfield:
high foliage / mountain : pine forest
high foliage / grasslands : deciduous / mixed forest
high foliage / shore : low bushes / swampy
high foliage / water : kelp / seaweed
low foliage / mountain : snowy
low foliage / grasslands : grass
low foliage / shore : sand
low foliage / water : sandy bottom

[Insectoid]

Haha, I've spent the whole morning thinking about ways to add other effects to ultimately generate random scenes that look realistic. unlike mirhagk I'm more interested in generating landscapes. If I ever finish the other projects I'm working on (school will motivate me) I might work with this stuff.

[mirhagk]

Thank you demonwasp, that way of generating it precisely what I will do. Also I'm considering (since the map is dynamically generated and theoretically unlimited) just storing the seed value, and calculating each continent when it's needed (obviously caching nearby ones). This way the map can literally be infinite (although it couldn't be changed, which isn't a problem really.

x^y mod prime number sounds like a good solution to a non-periodic map (obviously the map will have duplicate sections but they should be very far away from each other, and only single continents should be duplicated I believe, instead of the entire map tiling)

EDIT: the x^y algorithm may be too costly to do dynamically on each map that could be used (NPC's far away from the character can affect things [only once every second or so, but that might still cause lag]), so I may just go with the x*largeNumber+y since the user won't notice the tiling if it's really big.

[DemonWasp]

I like your idea of infinite map and on-demand generation, but there's probably some problems. First, midpoint displacement doesn't generate terrain that always tiles nicely with the next tile over if the tiles are generated separately. If you want to make infinite terrain, you will need to think pretty seriously about how to do it. The key is that the heights on each of the borders will need to match; to a lesser extent, you should also make sure that the slopes don't change too suddenly across the boundary.

This means you can't just blindly generate one tile while ignoring other tiles.

If you declare that each land mass must be contained by a single tile, and that the depth of the ocean is irrelevant, then you could ignore the "borders" between areas, and just generating tiles would work pretty well. The only downsides are that your generated terrain will have a relatively high water-to-land ratio, and you may be able to see a "grid" artifact if you zoom out to see enough continents. Potentially, neither is an issue for the game in question.

As it turns out, while computing x ^ y is a somewhat expensive operation, computing (x ^ y) mod z is easier. See here: http://en.wikipedia.org/wiki/Modular_exponentiation . This kind of computation turns up a lot in PRNGs and cryptography, which is why I suggested it. In particular the "right to left binary" method is extremely fast. If this somehow turns out to be super-costly, lookup tables are pretty quick.

If you did want a mutable landscape, you can do that too. First, define the base map by some extension of midpoint displacement (as above). Then, define a way of sending a "delta" or "difference" from the original data. This lets you make relatively small modifications without needing to send the entirety of an infinite map across the network. For example, if you happened to be a Dubai construction company and decided to build some islands shaped in a funny way, you would modify the terrain in some section of one of the tiles. Then, all the server needs to relay (and only to people observing that tile) is the master seed, and the modifications made.

This, however, is starting to get ambitious.

[mirhagk]

Yes I will be making the edges of each land mass to be water, and zooming out won't happen (potentially a map or something in the future, but not now). I may do the delta landscape too, since that sounds really cool, and the changes themselves could be compressed even farther. (for instance if a given tile can only be changed a certain number of ways, I can have a code that will store a 2 bit (or 3-4) number to encode that change).

It does sound ambitious demonwasp, but ambitious is my middle name. Well it isn't but by golly I'll make it my middle name.

[raggy]

DemonWasp wrote:

I like your idea of infinite map and on-demand generation, but there's probably some problems. First, midpoint displacement doesn't generate terrain that always tiles nicely with the next tile over if the tiles are generated separately. If you want to make infinite terrain, you will need to think pretty seriously about how to do it. The key is that the heights on each of the borders will need to match; to a lesser extent, you should also make sure that the slopes don't change too suddenly across the boundary.

This means you can't just blindly generate one tile while ignoring other tiles.

i was looking for a random world map generator my self and this eems to work nicely. but i did wanted it to havea infinate world generating.

what i did was copy the borders of the chunk that have been generated before.
in general this works out fine. the world generates on demand new chunks while considering the old chunks. and continue with the landscape.
the only give away that i have not managed to completly solve yet are the borderlines it self. zoomed out this looks find most of the time. its when zoomed in that you can see it better

i have added 2 pictures. one of a zoomed out(1pixel per tile) view. and one of a zoomed in (10 pixels per tile) view. (there not the some location)

in the zoomed out version you can see that it contintues with the landscape and does what it needs to do. (this is a setup of 9 chunks generated from top left to lower right)

on the zoomed in version you can see in the lake there are some miner errors that still have to be solved.(this minor error is the borders of the chunks)


the problem ofcoures comes from copying the border lines of premade chunks.
does anyone have any suggestions on how to improve this?

[mirhagk]

It's inherit in the algorithm, I'd look into altering the algorithm itself. For instance if you use an algorithm like midpoint displacement, with a restriction that the edges must be a constant, then the chunks will tile automatically, and the algorithm will always look nice relative to the border.

The problem that then comes into play however is that if you zoom out sufficiently, you will notice that each chunk has a border, and therefore you will notice where each chunk is even though on a small scale they integrate quite nicely.

EDIT: You also could alter your algorithm to have a smooth function at your edges, that might work well, without changing you algorithm. Basically you pass over all the values close to the border, on either side, taking the average of them, and then moving them closer to the average, so they all smooth out. You can do this in passes, where the first pass smooths out strongly, with only the closest values (to make them meet) then you can extend out once more each time, and have the smooth function be less harsh each time.

[mimimimi]

Insectoid @ Mon Aug 29, 2011 9:09 am wrote:

Wow, that's actually really neat. The author of the first article mentioned that clouds and 2-D maps can both be generated with the same algorithm and I damn near didn't believe him. I was very pleased when I found out just how simple it was.

i found a video that shows you how to do it:
https://www.youtube.com/watch?v=nPX8dw283X4&noredirect=1
make thinngs much easier


______________________
And a new day will dawn for those who stand long
And the forests will echo with laughter
vb 2d barcode generator