Hey! As the title suggests, this post
describes inner workings of algorithm that we have developed to interpolate heights
between chunks in our game called „TheTravelerGame“. First of all, quick
introduction into the problem we‘ve been facing: in our game we have several
types of biomes, each with their own minimum and maximum heights, and the
heights are generated using bare Perlin Noise. Here comes the fun part: an
efficient algorithm was needed which could interpolate between those chunks
(otherwise players could get stuck in one chunk - not a death trap I would like
to get into; it also would look pretty weird).
On a picture above you can see result of
our algorithm: the average height of forest is much lower than one of a snowy
biome, and they are nicely interpolated.
In short, the height of a block is
determined by chunks this block is close to. So, for example if the block is in
the upper left corner of the chunk, only upper left, left, upper neighbouring
chunks and the main one are included in the weights of that block. Here is an
example:
More about weights: each time we generate a
block, we look at what the height of that block would be in each of
aforementioned chunks. Then, we sum up the parts of each chunks generated
height to form the finished height of a block. Pseudocode (where pos is block’s position in main chunk):
For Each
chunk in includedChunks:
sum += height(chunk, pos) * weight(chunk,
pos) / sumOfWeights(chunk, pos)
Also, you may find quite interesting how we
generate the weight for a block. Because linear interpolation is not entirely
suitable for our needs, each weight is determined by this formula:
weight
= (chunkSize – manhattanDistance(pos, chunk.middlePos)) ^ 4
Obviously, there are some caveats in using
it, like strange blocks near the chunks middle (only noticeable when difference
between heights is substantial).
That’s all guys! If you have something
interesting to say (or maybe even know a better algorithm
than ours for this) please do not hesitate to comment.
