Midpoint Displacement 1D - How to properly reduce my random number range?

Question

So I'm trying to implement this http://www.gameprogrammer.com/fractal.html#midpoint algorithm, to generate myself a terrain. In the tutorial is said:

OK, before we go into 2D fractal surfaces, you need to know about the roughness constant. This is the value which will determine how much the random number range is reduced each time through the loop and, therefore, will determine the roughness of the resulting fractal. The sample code uses a floating-point number in the range 0.0 to 1.0 and calls it H. 2(-H) is therefore a number in the range 1.0 (for small H) to 0.5 (for large H). The random number range can be multiplied by this amount each time through the loop. With H set to 1.0, the random number range will be halved each time through the loop, resulting in a very smooth fractal. With H set to 0.0, the range will not be reduced at all, resulting in something quite jagged.

Let's say rand_start and rand_end are the starting and ending values that a random number can be generated by using for example random.uniform(rand_start, rand_end) or random.uniform(-1.0, 1.0)

Then I must reduce the number range so I do:

rand_start *= H * (pow(2, -H))

rand_end *= H * (pow(2, -H))

With H set to 1.0 for example.Both rand_start and rand_end will be lowered by half and in the next iteration the random value will be between -0.5 and 0.5. All clear, just like the tutorial said it.

Here is the problem:

My x coordinate starts at 0 in the left side of the window, and y coordinate in the top of the window, in Pygame

I draw my line at this coordinates:

line_start = (0, 300)

line_end = (WINDOWWIDTH, 300)

How to reduce my random range if start and end values are initialized like that:

rand_start = 400

rand_end = 200

Again, my line starts at y coordinate 300 and the highest the midpoint can be displaced is 200, the lowest - 400.

Any code required will be provided asap.

Answer 1

I'm not sure what your actual problem is (I first thought it was that you wanted to bias the initial midpoint range, but it looks like you actually don't), but here's a simple midpoint displacement implementation in Python:

# generic midpoint displacement routine   
def displace ( points, max_disp ):
    last_point = points[0]
    new_points = [ last_point ]

    for next_point in points[1:]:
        midpoint_x = 0.5 * ( last_point[0] + next_point[0] )
        midpoint_y = 0.5 * ( last_point[1] + next_point[1] )
        midpoint_y += random.uniform( -max_disp, +max_disp )

        new_points.append( (midpoint_x, midpoint_y) )
        new_points.append( next_point )
        last_point = next_point

    return new_points

# initialize the endpoints
points = [ (0, 300), (window_width, 300) ]

# set the initial displacement range and scaling factor
max_disp = 100
scale = 0.5

# repeat the displacement process 10 times
for i in xrange(0, 10):
    points = displace( points, max_disp )
    max_disp *= scale

If you do want to bias the first midpoint selection, the easiest way to do that is to cheat — just start with a three-point list, and reduce the iteration count by one:

# initialize the endpoints and first midpoint
points = [ (0, 300), (0.5 * window_width, 200), (window_width, 300) ]

# set the initial displacement range and scaling factor
max_disp = 50
scale = 0.5

# repeat the displacement process 10 times
for i in xrange(0, 9):
    points = displace( points, max_disp )
    max_disp *= scale

This code, using the same displace routine as above, will ensure that the middle point of the line will always be at height 200, while the endpoints are at height 300. Adding some randomness to the middle point is left as an exercise.