I've taken code from "Midpoint displacement algorithm example", cleaned it up a bit, and resuited it to work as a 1D linear terrain generator. Below is my new version of the doMidpoint() method:
public boolean setMidpointDisplacement(int x1, int x2) {
// Exit recursion if points are next to eachother
if (x2 - x1 < 2) {
return false;
}
final int midX = (x1 + x2) / 2;
final int dist = x2 - x1;
final int distHalf = dist / 2;
final int y1 = map[x1];
final int y2 = map[x2];
final int delta = random.nextInt(dist) - distHalf; // +/- half the distance
final int sum = y1 + y2;
map[midX] = (sum + delta) / 2; // Sets the midpoint
// Divide and repeat
setMidpointDisplacement(x1, midX);
setMidpointDisplacement(midX, x2);
return true;
}
The code seems to work well and produces workable terrain (you can see how I've tested it, with a rudimentary GUI)
After reading "Generating Random Fractal Terrain" and "Mid Point Displacement Algorithm", my question is:
How can I identify the 'roughness constant' implicitly utilized by this code? And then, how can I change it?
Additionally, and this may or may not be directly related to my major question, but I've noticed that the code adds the sum of the y-values to the "delta" (change amount) and divides this by 2 -- although this is the same as averaging the sum and then adding delta/2. Does this have any bearing on the 'roughness constant'? I'm thinking that I could do
map[midX] = sum/2 + delta/K;
and K would now be representative of the 'roughness constant', but I'm not sure if this is accurate or not, since it seems to allow me to control smoothing but doesn't directly control "how much the random number range is reduced each time through the loop" as defined by "Generating Random Fractal Terrain".
Like I've said before, I ported the 2D MDP noise generator I found into a 1D version -- but I'm fairly certain I did it accurately, so that is not the source of any problems.
How can I identify the 'roughness constant' implicitly utilized by this code?
In the cited, roughness is the amount you diminish the max random displacement. As your displacement is random.nextInt(dist) = dist*random.nextDouble(), your dist = x2-x1 and you go from one recursion step to the other with half of this dist, it follows that the roughness == 1 (in the cited terminology)
And then, how can I change it?
public boolean setMidpointDisplacement(int x1, int x2, int roughness) {
// Exit recursion if points are next to eachother
if (x2 - x1 < 2) {
return false;
}
// this is 2^-roughness as per cited
// you can pass it precalculated as a param, using it as such here
// is only to put it into a relation with the cited
double factor=1.0/(1<<roughness);
final int midX = (x1 + x2) / 2;
final int dist = x2 - x1;
final int distHalf = dist / 2;
final int y1 = map[x1];
final int y2 = map[x2];
// and you apply it here. A cast will be necessary though
final int delta = factor*(random.nextInt(dist) - distHalf); // +/- half the distance
final int sum = y1 + y2;
map[midX] = (sum + delta) / 2; // Sets the midpoint
// Divide and repeat
setMidpointDisplacement(x1, midX, roughness);
setMidpointDisplacement(midX, x2, roughness);
return true;
}
Additionally, and this may or may not be directly related to my major question, but I've noticed that the code adds the sum of the y-values to the "delta" (change amount) and divides this by 2
Their way has the advantage of doing it with a single division. As you work with ints, the accumulated truncation errors will be smaller with a single div (not to mention slightly faster).