Sign in to follow this  
Jonax

Terrain Generation: Creating an Island

Recommended Posts

Greetings - Long-time reader and first-time poster. ;) At the moment, I am currently working on an application that generates terrain base one one or more algorithms. Currently the application supports terrain generation by heightfield generation, geological faulting and Perlin noise. The next stage will be to also introduce the algorithms for midpoint displacement & particle deposition. After several weeks, I've gotten to the stage where I'm happy with the results so far. The current issue is now modifying the generation code to make the result resemble something other than a mountain range - More specifically, an island. Looking at my own application, it looks like it's theoretically possible to use an algorithm destructively so that it will reduce the height of some points in the terrain below a sea level. This would most likely be used with a variable strength so that the reduction is weakest at a point around the "center" of the island, while producing a stronger effect as the distance is increased. That's the "why" part over - The main question is whether there's any particularly recommended concepts or background reading to do this or otherwise "islandify" a terrain. While using only a constructive method such as deposition is likely easier, the main reason for wanting to generate the terrain constructively then destructively is so that the below-sea-level points can be used to render a seabed around the island. At the moment, I'm looking at modifying my faulting algorithm so that it can reduce points away from the island, although even when the result is imagined it still seems a little messy. If anyone can recommend anything, it'd be appreciated. :)

Share this post


Link to post
Share on other sites
You could try using a separate modifier map as either an additive or multiplicative modifier to the outputted Perlin noise. The mask would resemble an 'island' and could be generated algorithmically. I perform a similar technique for impact craters, using a modifier map such as

applying some turbulence to 'noisify' it up a bit, then adding it to the output of a Perlin function to get something like this:

I describe the process a bit more fully here., although the process detailed is pretty tied to my heightmap editor/generator stuff.

As a first whack at an island mask generator, you could calculate the distance of each heightmap element from the center of the map, and perform height = (radius-distance)/radius, where radius is the outside radius of the mountain. This would generate a sort of cone with height 1 at the mountain's center and height 0 at the edges. You could give it a more bell-shaped quadratic appearance with (radius*radius-distance*distance)/radius*radius if you wish, or otherwise play with the function.

Once you have the function to generate the island shape, perturb the x and y input coordinates to the function with a set of perlin turbulence functions to noisify the too-regular shape. I whipped up a couple test scripts in my heightmap editor and came up with the following non-perturbed and perturbed island masks, just to see how it might work:




The perturbed version used a turbulence of 150, meaning the input coordinates were perturbed by noise values scaled to the range [-150,150]. Less turbulence retains more of the round shape, more provides more irregularity.

I note that you could just about use the perturbed map as-is. [grin]

Share this post


Link to post
Share on other sites
Quote:
Original post by JTippettsI note that you could just about use the perturbed map as-is. [grin]


Hehe - To be honest, I didn't really notice until you said. [grin]

Thanks for the advice JT - I'll try them out first thing tomorrow and let you know the result. [smile]

Share this post


Link to post
Share on other sites
Yup, i make the same cone-thing in my island-generator, and pass it as a starting value for the ridged perlin noise. Gives pretty good (though unnatural) results.
If you arent doing it runtime, you should also do some erosion. You know, islands are often eroded.
[ad]The game in the signature uses an extremely simple island generator in runtime. Take a look at it to get an idea [/ad]

And that perturbing looks really nice too.

Share this post


Link to post
Share on other sites
Depending upon how you want to use the islands, then the hill algorithm described at Robot Frog 3D might suffice. If you apply a smoothing routine to the heighmap afterwards the results are flatter islands that you could move around on. See the "Island modification" section of the tutorial.

hth
F451

Share this post


Link to post
Share on other sites
Just a quick update - I'm one who believes it's custom to show the result of any help I'm given. [smile]

So far I've been working on the implementing & fine-tuning the bell-curve algorithm. It took about an hour to get it right and a couple more finetuning things here and there (mostly towards clamping the distance-radius value so that the lowest it can go is zero). Some additional finetuning to make sure values outside the circle are not affected and below-sea-level values are within the circle, and I've got something looking remotely like an island. [grin]

A few shots to show the process in action - Apologies that the engine isn't that attractive, been spending most of my time on the terrain generation. [smile] The first is the result of the Perlin Noise algorithm creating some sort of random terrain. The second is the result after the "Islandify" algorithm is passed over the same terrain.


I'm working on adding turbulance to the island's shape - I'll let you know how things go on with that. [smile]

Quote:
Original post by Gagyi
If you arent doing it runtime, you should also do some erosion. You know, islands are often eroded.


Aye, I think I'll definitely have to add code to remove things here & there to give it a more natural shape, although a few passes of a smoothing algorithm is helping a fair bit so far (but may be enhanced in the next day or so).

I'll have a look at Stickman Warfare later on today. [grin] If you have any particular pieces of advice, it'd be appreciated.

Quote:
Original post by Fahrenheit451
Depending upon how you want to use the islands, then the hill algorithm described at Robot Frog 3D might suffice.


Yep, I found the Robot Frog tutorials shortly before registering on GD. The only problem is that the way Bob's code generates the islands - His hill algorithm seems to generate the islands by adding hills to form the shape. While a pure constructive algorithm is a more sensible way of making the island, I'm already using particle deposition as a pure constructive generator - Right now it's only the destructive part I've issues with.

Thanks to JT, Gagyi and F451 for the help so far - For some reason, this was a lot more help than I was originally expecting. [grin]

Share this post


Link to post
Share on other sites
One way I've often implemented for varying the shape of the bell-curve in such situations is to generate a parameter, clamped to [0,1], using the (radius-distance)/radius method, then use that parameter to interpolate a curve with the desired cross-section. I can set-up a curve as a series of heights, and perform cubic interpolation between points to sample any point on the curve using the parameter. This allows me to specify any sort of cross-section I desire.
I implemented a general purpose curve class, templatable, for this purpose. I can create a curve, push a few control points onto it, then call various interpolation functions with a parameter to sample the curve. So if I want an island that looks vaguely volcano-ish, I could build a curve cross section to suit, then construct my height function around it.

In Lua-ish code (since my heightmap generation stuff is all Lua scripted):


function height_function(x,y,centerx,centery,radius,curve)
-- Calculate the parameter
local dx=centerx-x
local dy=centery-y
local dist = sqrt(dx*dx+dy*dy)

local param = (radius-dist)/radius
if param<0 then param=0 end

-- Sample the curve and return
local height = curve:cubicInterp(param)
return height
end


Using a sample curve such as



I get an island like this:



Not very exciting, true, but the control such a curve-defined height function gives me allows me a certain measure of control over the overall shape of the island or mountain peak.

In case you care, the C++ template class that I use for curves is here:


template <class T>
class TBasicCurve
{
public:

TBasicCurve()
{
m_interval=0.0;
};

~TBasicCurve()
{
};

void calcInterval()
{
int numpoints=m_points.size();
if(numpoints<2) return;

int numintervals = numpoints-1;
m_interval = 1.0 / (double)numintervals;
};

int getPointIndex(double t)
{
if(m_interval==0.0) return 0;

// Divide t by m_interval
int i = (int)(t / m_interval);
return i;
};

void pushPoint(T p)
{
m_points.push_back(p);
calcInterval();
};

void clear()
{
m_points.clear();
};

void initFromVector(std::vector<T> &vec)
{
m_points = vec;

calcInterval();
};

T linearInterp(double t)
{
int numpoints = m_points.size();
if(t<0.0 || t>1.0 || numpoints<2) return T(0);

// Find the point right behind the interpolant
int i = getPointIndex(t);
if(i<0 || i>=numpoints) return T(0);

T p1 = m_points[i];
T p2 = m_points[i+1];


double interp = t - ((double)i * m_interval);
interp = interp / m_interval;

T result = (p1*(1.0-interp)) + p2*(interp);
return result;
};

T cosineInterp(double t)
{
int numpoints = m_points.size();
if(t<0.0 || t>1.0 || numpoints<2) return T(0);

// Find the point right behind the interpolant
int i = getPointIndex(t);
if(i<0 || i>=numpoints) return T(0);

T p1= m_points[i];
T p2=m_points[i+1];


double interp = t - ((double)i * m_interval);
interp = interp / m_interval;

const double PI = 3.14159265;

double mu2 = (1.0 - cos(interp*PI))/2.0;
T result = p1*(1.0-mu2) + p2*(interp);
return result;
};

T hermiteInterp(double t, double tension, double bias)
{
int numpoints = m_points.size();
if(t<0.0 || t>1.0 || numpoints<2) return T(0);

// Find the point right behind the interpolant
int i = getPointIndex(t);
if(i<0 || i>=numpoints) return T(0);

int i1,i2,i3;

i1 = i-1;
i2 = i+1;
i3 = i+2;

if(i1<0) i1=0;
if(i2>numpoints-1) i2=numpoints-1;
if(i3>numpoints-1) i3=numpoints-1;

T p0,p1,p2,p3;

p0=m_points[i1];
p1=m_points[i];
p2=m_points[i2];
p3=m_points[i3];

double interp = t - ((double)i * m_interval);
interp = interp / m_interval;

double int2 = interp*interp;
double int3 = int2 * interp;

T m0 = (p1-p0)*((1+bias)*(1-tension)/2);
m0 += (p2-p1)*((1-bias)*(1-tension)/2);
T m1 = (p2-p1)*((1+bias)*(1-tension)/2);
m1 += (p3-p2)*((1-bias)*(1-tension)/2);

double a0,a1,a2,a3;
a0 = 2*int3 - 3*int2 + 1;
a1 = int3 - 2*int2 + interp;
a2 = int3 - int2;
a3 = -2*int3 +3*int2;

T result = (p1*a0) + (m0*a1) + (m1*a2) + (p2*a3);
return result;


};

T cubicInterp(double t)
{
int numpoints = m_points.size();
if(t<0.0 || t>1.0 || numpoints<2) return T(0);

// Find the point right behind the interpolant
int i = getPointIndex(t);
if(i<0 || i>=numpoints) return T(0);

int i1,i2,i3;

i1 = i-1;
i2 = i+1;
i3 = i+2;

if(i1<0) i1=0;
if(i2>numpoints-1) i2=numpoints-1;
if(i3>numpoints-1) i3=numpoints-1;

T p0,p1,p2,p3;

p0=m_points[i1];
p1=m_points[i];
p2=m_points[i2];
p3=m_points[i3];

double interp = t - ((double)i * m_interval);
interp = interp / m_interval;

double int2 = interp*interp;
double int3 = int2 * interp;


T a0 = (p3)-(p2)-(p0)+(p1);
T a1 = p0-p1-a0;
T a2 = p2-p0;

T result = (a0*int3) + (a1*int2) + (a2*interp) + p1;
return result;
};



protected:
std::vector<T> m_points;
double m_interval;
};



It's pretty rough, probably prone to bugs, and could probably stand some improvement, but it allows a certain measure of abstraction for general curves, and provides a number of interpolation methods you can use.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this