Jump to content

  • Log In with Google      Sign In   
  • Create Account


Infinite terrain generation in chunks - need hints on handling chunk edges


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
34 replies to this topic

#21 BGB   Crossbones+   -  Reputation: 1549

Like
0Likes
Like

Posted 25 February 2013 - 06:59 PM

Kylotan, on 25 Feb 2013 - 14:38, said:
cr88192: I must admit I have no idea how any of that would work - although I'm not sure I would need it if I had a function that was defined for all possible values of x any y. I think "interpolating over the region-edges via a windowing function" is essentially what I described originally, bilinearly interpolating between the values for adjacent regions - right?

it would be more like how one interpolates between the IMDCT output-blocks in something like MP3 or Ogg/Vorbis.
(may help give an idea at least: http://en.wikipedia.org/wiki/MDCT ).

basically, each region would have its own local set of interpolated sample points, which are used as its own local noise function.

now, when blending between regions, the local sample-values would be computed independently within each region, and the windowing would be between the various noise functions (simulating a larger-scale continuous function from a large number of smaller-scale periodic functions).

Edited by cr88192, 25 February 2013 - 07:03 PM.


Sponsor:

#22 swiftcoder   Senior Moderators   -  Reputation: 9731

Like
0Likes
Like

Posted 25 February 2013 - 08:20 PM

None of these values will ever hit the interpolation part as FractionalPartOf(x) always returns 0. In this case the Noise function is no different from a discrete random number generator, and no smoothing is being performed. The detail is effectively at maximum all the time, for any whole-number value for frequency.

You can always choose to sample a function at such a low frequency that it does not appear continuous. I guess I'm confused why you insist on taking that frequency as your base case?

Tristam MacDonald - Software Engineer @Amazon - [swiftcoding]


#23 JTippetts   Moderators   -  Reputation: 8208

Like
3Likes
Like

Posted 25 February 2013 - 11:48 PM

You're always going to have problems with the typical variants of noise if you insist on sampling at integer boundaries. In fact, if you use Perlin's gradient noise, that will get you values of 0 across the board, since gradient noise is constructed specifically to cross the 0 line at grid corners, thus shifting the "peaks" and "valleys" of the function off the grid points and out into the middle of the cells somewhere. If you only sample at grid corners there, you miss all the peaks and valleys completely. If nothing else, just divide your integral coordinates by the size of a chunk; this will map unit-sized pieces of the domain to your chunk, then you can modify the frequency of the individual functions comprising your generator to tune it for feature density.

 

A lot of implementations of noise that you find on the web have a relatively small period. The reference implementations of gradient and simplex Perlin noise, for example, have a period of (IIRC) 255 samples, since they hash unsigned char coordinates. For ANL, I built my hash using a FNV-1A hash that can be applied to arbitrarily sized arrays, using it to hash integer coords (or long, or even long long if I so desired, though I have yet to find a need to have a function with a larger period than an int type can provide) then XOR folding the hash down to access the 256-entry lookup table of gradients. (The 256-size table isn't really necessary; you can get away with an 8-entry table) This gives me an effectively unlimited function. After that, it's a simple matter of mapping out small pieces of it to chunks. The hash can be used to hash any required dimensionality of noise (ANL goes up to 6D, in order to implement a special kind of 3D seamless mapping if desired). It's a bit slower than the simple byte folding in the reference implementation, but not too bad, and I have done small scrolling tile-map style demos of infinite worlds just to test the concept, and it has been sufficient.

 

As far as your idea to have a base height that is interpolated, I don't really see how this is different from just adding in another very low frequency noise layer with the higher frequency detail layers on top of it. If your chunk size is 100x100, for example, and you are dividing the integral coordinates by the size (100) to map a unit-sized cell of noise to your chunk, then a base layer with an internal frequency of 1/100 would net you approximately 1 "feature" (a low or a high) per cell/chunk, smoothly interpolated by the basic noise generator to be continuous, upon which would be added the subsequent detail layers.



#24 Kylotan   Moderators   -  Reputation: 3333

Like
0Likes
Like

Posted 26 February 2013 - 05:26 PM

I don't get any choice of where I sample the function. I'm generating a heightmap and for that I need a value at x=1, a value at x=2, etc. I only have the choice of scaling the function to suit what I sample, or wrapping it in another function that does the scaling, but the combination will be equivalent. So really I need a function that is smooth to some degree across several integer values.

 

I'm having real trouble describing my problem and as a result nobody is quite understanding me. Let me try and describe it as if I'm a newbie and hopefully it'll be clearer.

  • I have an infinite world, coordinates going from -infinity to +infinity. (Will describe as one-dimensional to keep it simple.)
  • I generate chunks that are 100 units long, .eg. from -200 to -100.
  • I need samples at every integer position along that range, -200, -199, -198, ..., -100
  • I want to generate the height maps based on a simple sum of several rounds of interpolated value noise - not real Perlin noise, or Simplex noise, etc. - each weighted by its 'amplitude'. I don't need nor care about higher-level continuity or any of that.
  • The highest frequency for any of my rounds of noise should be equal to the height map resolution. Values at that level should appear completely incoherent from one value to the next. The amplitude will be minimal for this round. The output at each position here could essentially be determined as hash(x) * amplitude.
  • Each successive round should generate data with more apparent coherence than the last, up to round N which will be so smooth that adjacent values will always be similar.
  • I do not know what function to use for the successive rounds. The value needs to be interpolated between 2 separate hashed values. I don't know how to select both the inputs to the 2 hash functions, based on the integer value of x. I need to know how to choose those 2 inputs in such a way that I get to vary a frequency parameter (by that name or another name) to alter the level of coherence between adjacent integer samples.

 

 

As far as your idea to have a base height that is interpolated, I don't really see how this is different from just adding in another very low frequency noise layer with the higher frequency detail layers on top of it.

The only real difference is that these base heights are predetermined outside of the algorithm, that's all. It might be simple to add this as a trivial final 'layer' - if only I could work out the logic to get the other layers first.


Edited by Kylotan, 26 February 2013 - 05:27 PM.


#25 JTippetts   Moderators   -  Reputation: 8208

Like
1Likes
Like

Posted 26 February 2013 - 06:49 PM

I don't get any choice of where I sample the function. I'm generating a heightmap and for that I need a value at x=1, a value at x=2, etc. I only have the choice of scaling the function to suit what I sample, or wrapping it in another function that does the scaling, but the combination will be equivalent. So really I need a function that is smooth to some degree across several integer values.
 
I'm having real trouble describing my problem and as a result nobody is quite understanding me. Let me try and describe it as if I'm a newbie and hopefully it'll be clearer.

  • I have an infinite world, coordinates going from -infinity to +infinity. (Will describe as one-dimensional to keep it simple.)
  • I generate chunks that are 100 units long, .eg. from -200 to -100.
  • I need samples at every integer position along that range, -200, -199, -198, ..., -100
  • I want to generate the height maps based on a simple sum of several rounds of interpolated value noise - not real Perlin noise, or Simplex noise, etc. - each weighted by its 'amplitude'. I don't need nor care about higher-level continuity or any of that.
  • The highest frequency for any of my rounds of noise should be equal to the height map resolution. Values at that level should appear completely incoherent from one value to the next. The amplitude will be minimal for this round. The output at each position here could essentially be determined as hash(x) * amplitude.
  • Each successive round should generate data with more apparent coherence than the last, up to round N which will be so smooth that adjacent values will always be similar.
  • I do not know what function to use for the successive rounds. The value needs to be interpolated between 2 separate hashed values. I don't know how to select both the inputs to the 2 hash functions, based on the integer value of x. I need to know how to choose those 2 inputs in such a way that I get to vary a frequency parameter (by that name or another name) to alter the level of coherence between adjacent integer samples.
The only real difference is that these base heights are predetermined outside of the algorithm, that's all. It might be simple to add this as a trivial final 'layer' - if only I could work out the logic to get the other layers first.


Unless I'm mis-interpreting you here, what you are describing is standard fractal noise. The basis function (whether it be one of Perlin's variants, interpolated value noise, or whatever) is completely irrelevant. In fractal noise you pile up successive layers of noise, each layer having a smaller amplitude and higher frequency than the preceding layer. (The most common variant uses half the amplitude and twice the frequency of the preceding layer).

As far as using integer coordinates, if you absolutely must use them then just set the internal frequency of your generator function to, say, 1/100. Successive layers can have their own internal frequencies relative to that. That way, you can still use integral coordinates it's just that internally they are converted to smaller ranges before being passed to the generator.

#26 Sandman   Moderators   -  Reputation: 2084

Like
0Likes
Like

Posted 27 February 2013 - 04:37 AM

I do not know what function to use for the successive rounds. The value needs to be interpolated between 2 separate hashed values. I don't know how to select both the inputs to the 2 hash functions, based on the integer value of x. I need to know how to choose those 2 inputs in such a way that I get to vary a frequency parameter (by that name or another name) to alter the level of coherence between adjacent integer samples.

 

Perhaps it might be easier to think in terms of wavelength, rather than frequency.

 

Your highest frequency noise has a wavelength of one - and doubles (or whatever) each octave after that. Using integer maths, your hash inputs are just (x / w) and  ((x / w) + 1), and your interpolation ratio is (x % w) / w

 

You may want to provide the octave as an input to your noise function as well, in order to avoid weird effects with identical patterns being layered on top of each other at different scales.


Edited by Sandman, 27 February 2013 - 06:30 AM.


#27 Kylotan   Moderators   -  Reputation: 3333

Like
0Likes
Like

Posted 27 February 2013 - 04:43 PM

Ok, I have the start of a working system, so thanks to all who've contributed. I've obviously been overthinking the original terms when a lot of them don't matter, and I worked out how to get integral values of x into fractional values falling between two hashed samples using division by a wavelength parameter, and it mostly works. I still need to work out how to use cubic interpolation instead of linear (which has some sharp edges, obviously), but then the basics will be done.

 

I'd like to be able to vary some parameters from one chunk to the next - eg. If I want one chunk to be almost flat, and one to be very hilly. I don't know the best way to guarantee they'd be continuous at the edge. I suppose I could interpolate between 2 different invocations of the function with the different parameters, if there's nothing better that I'm missing.



#28 swiftcoder   Senior Moderators   -  Reputation: 9731

Like
0Likes
Like

Posted 27 February 2013 - 06:51 PM

I'd like to be able to vary some parameters from one chunk to the next - eg. If I want one chunk to be almost flat, and one to be very hilly. I don't know the best way to guarantee they'd be continuous at the edge. I suppose I could interpolate between 2 different invocations of the function with the different parameters, if there's nothing better that I'm missing.

Doing this on a chunk-by-chunk basis is asking for trouble - you are going to spend a lot of effort dealing with the resulting discontinuities.

 

It would be better to use another low-frequency procedural function to drive the interpolation between hills and plains.


Tristam MacDonald - Software Engineer @Amazon - [swiftcoding]


#29 Kylotan   Moderators   -  Reputation: 3333

Like
0Likes
Like

Posted 28 February 2013 - 08:04 AM

Sure, that would be easier, but that's not the specification I have to work with. :)

 

I refactored things a bit so that instead of generating one value for each point of the height map, I generate one for each type of potential terrain topography (eg. plains, hills, mountains) and then blend between them, based in the actual value at this grid square and those of neighbouring ones. Currently I'm doing this via a hack with 3D vectors and spherical interpolation, but I'm hoping I can generalise it to an array of contributions from each terrain type which I can normalise and use as weightings for each of the different sampled values.



#30 FLeBlanc   Crossbones+   -  Reputation: 3085

Like
2Likes
Like

Posted 28 February 2013 - 12:52 PM

If it were me, I'd use a value noise function with a frequency of 1/chunksize as others have suggested for a base layer, then use that base layer in a selection function to choose between different types of terrain. The selection function takes two inputs and a control function, and using a threshold parameter and a falloff parameter (see the description for the CImplicitSelect function of accidental noise for details)  to smoothly select and blend between the two input types. So, say your chunks are 100x100. Then a 5x5 array of chunks might have a base layer like this:

 

908oHYF.png

 

Each "block" in the base layer roughly corresponds to a chunk. Then I would use a selection function to map between Plains and Hills, with threshold set at 0.333 and falloff set at, say, 0.2:

 

 

(The hills and plains are simply fBm fractal functions with specific frequencies and amplitudes, tweaked to suit)

 

Then a second select function, again using the base layer as a control, would be used to select between this Hills/Plains combo and Mountains, with the threshold at 0.66667 and the falloff again equal to 0.2. (Vary this value, of course, to vary the smoothness of the transition between terrain types):

 

J2uy15Y.png

 

rJPrcQZ.png

 

And there you have it. You can package all of this up into a meta-function such that for any point in the world you can call func(x,y) to get the height. Then it's a simple matter of mapping out sub-regions to your chunks as you go.


Edited by FLeBlanc, 28 February 2013 - 12:52 PM.


#31 Kylotan   Moderators   -  Reputation: 3333

Like
1Likes
Like

Posted 28 February 2013 - 07:26 PM

That's quite interesting, and I can see that I might be able to simplify some aspects with a generalised selection function like that. However I don't get to have a smoothly varying base layer. The system has discrete per-chunk values for Grass, Hills, Mountains, etc.

 

I have already implemented a system that produces something much like in the screenshot, but achieved the smoothing across chunks by using bilinear interpolation when deciding what each position's topography weighting (ie. how much plains/hills/mountains) should be. This seems to be working well for me, and I'm quite relieved that it is equivalent in many ways to what you're describing as it shows I'm not doing something ridiculous.


Edited by Kylotan, 06 March 2013 - 05:51 AM.
Fixed formatting that the editor broke


#32 noizex   Members   -  Reputation: 853

Like
0Likes
Like

Posted 02 March 2013 - 02:20 AM

Kylotan could you elaborate a bit on your bilinear interpolation using discrete per-chunk values? I'm now working on a terrain that will be finite, but generated by noise based on properties of "chunks" that will be generated from voronoi cells (look at http://www-cs-students.stanford.edu/~amitp/game-programming/polygon-map-generation/). Basically:

 

  • I generate random set of points and run voronoi algorithm on it to create voronoi cells and delaunay triangulation, as described in Amit's post
  • Diagram allows me to run all sorts of terrain-building algorithms, with manual control over some details like where I want cliffs, generating rivers thanks to interconnection of voronoi cells and so on. I call this large scale detail map.
  • I generate a pixel map out of that diagram (again, like Amit) to have a finite (say 4096x496 bitmap) array of values which will describe various data. It can contain base height, biome type, humidity, temperature - all factors that later affect small scale details like how the terrain is generated, what plants are there. I can sample this bitmap by coords of chunk and know exactly what conditions are in this chunk.
  • Now I had a plan to generate perlin noise for small detail, so final terrain. I wanted to base this on sampled value from array, but I realized that single value from that map will create chunky terrain - every chunk will end exactly on its boundaries, and terrain wont blend between. So i need to smooth the transitions somehow - I also thought about blending nearby factors and using that interpolated value as input into noise function, but I haven't yet figured out how to do it best. Reading from FLeBlanc's post, thats what he uses falloff for in first picture probably, so the borders are not sharp but slightly blended.

Edited by noizex, 02 March 2013 - 02:20 AM.


#33 Norman Barrows   Crossbones+   -  Reputation: 1966

Like
0Likes
Like

Posted 02 March 2013 - 02:32 AM

I'm facing a similar problem in my current project.

 

the world is 2500 miles by 2500 miles. Its divided up into 5 by 5 mile map squares. A map square can use one of five different procedural heightmap formulas, depending on the elevation in the map square (ocean, flat, hill, mountains, or impassable mountains). Needless to say, heightmaps at map square edges don't line up. I spent a bit of time working on this, and just about have it solved. what i do is blend the values of the two heightmaps together over a distance of 100 d3d units  from the edge. so at the edge, the height is 50% of one edge + 50% of the next edge. at 100 from the edge its 100% just the one heightmap. at 50 units from the edge, its 75% one + 25% the other, and so on. this yields beautiful seamless edges. until you get to the corners. I haven't implemented it yet, but it looks like the trick is to "zip up" (average together) all the seams running north south, then use those results to zip up the seams running east west. a method like this doesn't care about the procedure used to create the heightmaps, so you wouldn't have to worry about finding a noise function that works. you could use anything you wanted, then just "zip up" the seams.


Norm Barrows

Rockland Software Productions

"Building PC games since 1988"

 

rocklandsoftware.net

 


#34 Kylotan   Moderators   -  Reputation: 3333

Like
0Likes
Like

Posted 06 March 2013 - 06:12 AM

Kylotan could you elaborate a bit on your bilinear interpolation using discrete per-chunk values?

 

Basically for any position in the world, I collect the 4 nearest per-chunk terrain types. This is done by subtracting half a chunk from the x and y directions, then checking the chunk values at (chunkX, chunkY), (chunkX+1, chunkY), (chunkX, chunkY+1), and (chunkX+1, chunkY+1).

 

Interpolating between them is a bit tricky because the terrain types are stored in an enumeration and obviously you can't just linearly interpolate along that. So I create a vector for each chunk that holds the chunk's weight for each of the terrain types. This will be 1 for the chunk's designated type and 0 for everything else, eg. (0,1,0) if I had 3 terrain types of Plains/Hills/Mountain and this was a hill.

 

Then I can interpolate between those, which will give me a value like (0.6, 0.4, 0) for an area just inside a Plains chunk, next to a Hills chunk. So I run the noise generator on this position for the Plains and for the Hills, then use the interpolated values to weight the sum, ie. PlainsNoise * 0.6 + HillsNoise * 0.4.

 

I had a plan to generate perlin noise for small detail, so final terrain. I wanted to base this on sampled value from array, but I realized that single value from that map will create chunky terrain - every chunk will end exactly on its boundaries, and terrain wont blend between.

 

In your situation I don't think you need to try and blend anything. If you're just generating fine detail and that detail is the same everywhere then you can just add the noise to whatever is already there and the values should be continuous as long as the underlying terrain is continuous and the noise is continuous also. To achieve that, you just need to ensure that the noise sampling wraps around. Most implementations of noise already do that. You'll have the problem I did, in that most implementations assume the resolution and dimensions of the world follow the patch of noise rather than vice versa, but it's simple to fix that once you get your head around it (which only took me about 20 forum posts above. ;) )



#35 Kylotan   Moderators   -  Reputation: 3333

Like
0Likes
Like

Posted 06 March 2013 - 06:17 AM

I spent a bit of time working on this, and just about have it solved. what i do is blend the values of the two heightmaps together over a distance of 100 d3d units from the edge. so at the edge, the height is 50% of one edge + 50% of the next edge. at 100 from the edge its 100% just the one heightmap. at 50 units from the edge, its 75% one + 25% the other, and so on. this yields beautiful seamless edges. until you get to the corners.

 

That's basically what I do, except I blend everywhere rather than just at edges. So in the middle of a section, that section contributes 100% of the value. As you move towards the edge of the section, that drops linearly to 50% of the value, plus 50% of the next section's value. I do this with linear interpolation for now, so I could change it to only blend nearer the edges by scaling the input values.

 

The problem with corners is solved by bilinearly interpolating across the 4 nearest sections. You can do it the way I described in my previous post, although there may be a simpler way to achieve the same effect - my attempt was shaped somewhat by the code I had already written.


Edited by Kylotan, 06 March 2013 - 06:18 AM.





Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS