Jump to content
  • Advertisement
Sign in to follow this  
winsrp

Procedural map building... combining techniques to get nice features

This topic is 2256 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Given 3 techniques I have explored so far

fBm - with some kind of filter over Simplex noise (sum fractal, billow, etc)
Polygonal generation (PG from now on) - refer to this link to understand what I'm talking about.
Diamond Square (DS from now on)- refer to this link and this link

Given also the assumption, that we are building a 3d map (in my case voxel map, but could be a normal 3d map also), based on a series of 2d images, could be height maps, zone maps, water maps, temperature maps, moisture maps, etc etc... that are dynamically generated by the program.

So, the objective is to have:

A map that contains the following characteristics

-is seamless, rounded, loop around, what ever you like to call it. Not infinite.
-has oceans, beach, and mountains.

If that would be the whole objective, then its a piece of cake fBm or DS, PG has some troubles on seamless edges but it can be fixed, the main problem on PG is that land cannot be on the edges of the map, only ocean, since that's kind of key to this algorithm, but lets continue to add characteristics

-the map needs to be consistent in detail at all zoom levels.

so lets say that the minimap is 128x128... small map, not much definition on the image, you zoom in to see it in 256x256... now more definition should be created on the fly to get more details on the map... and you can go all the way to ... lets say.. 8192*8192, now on your little tiny micro 128x128 minimap display, you will only draw the corresponding pixels of that zoom, no need to render the HUGE image all together, on that zoom level, each pixel of you initial 128x128 map, corresponds to 64 pixels on you 8192*8192 map, so, how to maintain zoom levels?, asuming that each time you zoom in you are doing 2^7+n, where the first zoom level is level 0 and the last zoom level could be..., well as big as you want really, but lest say 6 (so 2^7+0 = 128 and 2^7+6 = 8192),

well on fBm, its quite easy, for each each zoom level add one more octave to the count, and make your range 2 times smaller, and you have more detail, on DS, its kind of ok, each zoom level you can grab each square, and put it into a twice as big grid, and apply calculations again, it will give you detail right away, but on PG, this is really really hard, as you will normally only have the initial detail level, and in order to zoom in, you will need to make nested voronoi maps (which are a royal pain), not to mention making all the calculation for other stuff that come after it, so... not so simple... but more characteristics to come,

-has lakes, at different elevations

adding this objective right here, gives a hard time on fBm and DS, as you really cannot have water above sea level, normally you will denote water being at 0 level or coast level, asuming all values are on the range of -1 to 1. On the other hand PG, gives excelent lakes at different elevation, since elevation is calculated from the edges of the map to the center, and you can have water at mid land elevations; anyway lets add more characteristics.

-has rivers, that come down from mountains, all the way to the ocean.

hmm... now since we can build the topography up front in a height map, we could know where the x elevation points are, and then go downhill from there, it can work on all 3 techniques, it is easier on the PG since there is always a direct downhill point all the way to the ocean, but, it can also work on fBm and DS, rivers might go a little longer due to micro elevations on the landscape, but eventually they will get to the ocean, or get stuck on some valley... one more characteristics.

-gives you a location for each tree in the map... but those trees are 3d procedural trees...

no idea how to do this on any of the techniques, you can have some random point as in the first couple steps of the PG map, apply voronoi, let it give you some positions and all that, but that would be on a zoomed level, not a zoom out, and as PG cannot zoom in.. then its hard. on fBm and DS, I still have no idea how to do this, and I get trees with and without leafs, trunks, cut in half and lots of other weird stuff, now lets stop here..

we could have lots and lots of more characteristics, like temperature, moisture, biomes, waterfalls, volcanoes, etc etc... but since the basics are already hard enough to make, we will put a milestone here.

I have been giving this problem a couple weeks of tests and thoughts and I can't seem to come to a solution on how to combine them all to comply with the desired result... from top to bottom of this list.

Any ideas are greatly appreciated.

Share this post


Link to post
Share on other sites
Advertisement
Fractal noise methods in 2D to give a rough, basic elevation map.

Erosion simulation + Rainfall simulation to model the shaping of the base landform in a realistic fashion, plus a reasonable approximation of water flow.

Simulation of temperature zones, probably some combination of gradient banding North-to-South, with turbulence added by elevation.

Simulation of weather patterns; can be derived from the rainfall simulation earlier. In this stage, you generate a "moisture map" to approximate a given cell's moisture level.

Vegetation determination. For each cell in the map, assign a set of data describing the type of vegetation likely to be found there, based upon temperature, moisture, elevation, steepness, rockiness, etc...

If a location is determined to have a tree, put a tree there. Find the bounding box based on availability of space at the location (requires a pass scan through the area to check for blocking) then generate a tree within that space. The Procedural World blog has a couple entries on space colonization to generate trees that you might look into. That algorithm is fairly well suited for "fitting" a tree into whatever space is available for it, as long as you craft your generation routines carefully.

You can see from this thoroughly non-comprehensive list, that it requires a mix of techniques. Your requirement of being able to zoom can possibly throw a monkey wrench into the works. Implicit methods such as fractal noise are well-suited for zooming; simulation methods such as erosion and vegetation placement are not, due to the necessity of having to perform processing "passes" over chunks of data. You can, however, perform the generation at the finest level of detail and down-sample for the coarser levels of zoom.

It's a non-trivial task you've set yourself. Best thing I can say is just keep experimenting and trying stuff.

Share this post


Link to post
Share on other sites
I agree with FLeBlanc. A rounded world requires a mixture of approaches, some which allow easy zoom and others which don't. If possible I'd just generate vegetation and store it, then stream in as required. If you want erosion... that may be possible. I'm thinking store the difference to the heightmap caused by erosion, then use something like JPEG to compress it. JPEG is based on Fourier transforms, so is both lossy and can be expressed as a continuous function. A continuous function which could be subtracted from the map as required. Lakes above sea level could be stored as just a point and a fill level, e.g. lake starts here, fill up to this elevation. Maybe stop points for where the lake leads to rivers or a total volume would need to be set to avoid flooding the map.

Share this post


Link to post
Share on other sites
that's why I like this forum, there are some really smart people here... or I'm WAY TOO NOOB... could be a combination of both, I'm aware of that.

FleBlanc, following the links you provided I managed to get lots of information on how to makes trees... the funny thing is that I had already gone through half of them months ago, and I just couldn't understand a word of what the guy was saying, but it seems like I was missing some data in my head back then to put all that together.

Here is a representation of a perlin + perlin 3d based map (you could say this is zoom in... kind of.)

[sharedmedia=core:attachments:9460]

here is a representation of what I have, from a Polygonal Map generation. (this has river, mid elevation lakes, but is not seamless, and of course normally it won't have zoom in)

[attachment=9986:minimaptest7.png]

here is an image of a zoom in to a section of the polygonal map, and adding some simple perlin to it. (just a function over the other, not a real zoom, for testing purposes.)

[attachment=9987:minimaptest8.png]

Share this post


Link to post
Share on other sites
Here is a paper dealing with some of the topics you mentioned. Starts out with a mixture of Voronoi and Diamond Square and then further erodes the terrain.

The algorithms are designed for realtime calculation, which would be useful for your "consistent in detail at all zoom levels" plans - just calculate the detail as needed. Just "adding" one step when you zoom in won't work with the erosion though - you would need to refine the base heightmap and then calculate the whole erosion from scratch.

Take a look at it, the author of the paper hat some other criteria for his heightmaps. E.g., we wanted the terrain to have flat areas where game content could be placed easily.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!