Midpoint Displacement 2D algorithm producing unusual patterns

Question

I'm having difficulties with the Midpoint Displacement Algorithm using Haxe. I am implementing this by following the steps found here.

First, create an array that represents a blank map. You begin by giving the four corners a random value.

In this square, create the middle point by averaging the four corners and adding a small 'error', or random value. Then create the midpoints of the 4 sides by averaging the two corners each is between. After these steps, you are left with 4 squares. Repeat the steps:

1. Create the middle point by averaging the four corners and adding a small 'error'.

2. Create the midpoint of each side by averaging the two corners each point is between.

Each iteration, make the range of the RNG smaller. That way the original few points can have pretty large variation, but the later points only get tiny adjustments. This ensures the right amount of detail in an image.

Here is the function I've written to perform these steps and then normalize the values:

public static function generateFloatMatrix(Columns:Int, Rows:Int, RangeModifier:Float = 0.65):Array<Array<Float>>
{
    //Blank 2D Array
    var matrix:Array<Array<Float>> = InitFloatMatrix(Columns, Rows);
    var range:Float = 1;
    
    //Set Values for all four corners
    matrix[0][0] = Math.random() * range;
    matrix[Rows-1][0] = Math.random() * range;
    matrix[0][Columns-1] = Math.random() * range;
    matrix[Rows - 1][Columns - 1] = Math.random() * range;
    
    //Calculates the amount of segments in base 2
    var length = Math.sqrt((Columns * Columns) + (Rows * Rows));
    var power:Int = Std.int(Math.pow(2, Math.ceil(Math.log(length) / Math.log(2))));
    
    //Stores largest calculated value for normalization
    var max:Float = 0;
    
    var width:Int = Std.int(Columns);
    var height:Int = Std.int(Rows);
    
    var i:Int = 1;
    while (i < power)
    {
        //Segment Size
        width = Std.int(Columns / i);
        height = Std.int(Rows / i);
        
        for (y in 0...i)
        {
            for (x in 0...i)
            {
                //Top Left Coordinates per segment
                var left = width * x;
                var top = height * y;
                
                //Find Midpoint
                var xMid = Math.ceil(left + (width / 2));
                var yMid = Math.ceil(top + (height / 2));
                
                //Make sure right and bottom do not go out of bounds
                var right:Int = (left + width < Columns ? left + width : Columns - 1);
                var bottom:Int = (top + height < Rows ? top + height : Rows - 1);
                
                //Sets midpoint value to average of all four corners.
                matrix[yMid][xMid] = 
                    (matrix[top][left] + 
                        matrix[bottom][left] + 
                        matrix[bottom][right] + 
                        matrix[top][right]) / 4;
                        
                //trace ("Top: " + top + " - Left: " + left + " - Bottom: " + bottom + " - Right: " + right);
                
                //Adds random value to midpoint
                matrix[yMid][xMid] += Math.random() * range;
                
                //Set side values to average of adjacent corners
                matrix[top][xMid] = (matrix[top][left] + matrix[top][right]) / 2;
                matrix[bottom][xMid] = (matrix[bottom][left] + matrix[bottom][right]) / 2;
                matrix[yMid][left] = (matrix[top][left] + matrix[bottom][left]) / 2;
                matrix[yMid][right] = (matrix[top][right] + matrix[bottom][right]) / 2;
                
                max = Math.max(matrix[top][left], max);
            }
        }
        
        //Reduces range
        range *= RangeModifier;
        i *= 2;
    }
    
    //Normalizes all values in matrix
    for (y in 0...Rows)
    {
        for (x in 0...Columns)
        {
            matrix[y][x] /= max;
        }
    }
    
    return matrix;
}

These are the images it is producing if I use each value to render each pixel to the specified coordinate. All the pixels that are rendered white have the value 0, black is value 1.

Answer 1

Your problem is that you don't necessarily hit the already populated pixels with your calculations if your map dimensions are not a power of two. For example if your map is 30 units wide, your grid width is 15 in the first pass and 7 in the second pass, where it bases its calculations on the yet untouched unit 14.

A solution is to do all calculations with floating-point arithmetic until you determine the unit indices, which must of course be integer:

while (i < power)
{
    var width:Float = Columns / i;    // Floating-point division
    var height:Float = Rows / i;

    for (y in 0...i)
    {
        for (x in 0...i)
        {
            var left:Int = Math.floor(width * x);
            var top:Int = Math.floor(height * y);

            var xMid:Int = Math.floor(width * (x + 0.5));
            var yMid:Int = Math.floor(height * (y + 0.5));

            var right:Int = Math.floor(width * (x +1));
            var bottom:Int = Math.floor(height * (y + 1));

            //Make sure right and bottom do not go out of bounds
            if (right > Columns - 1) right = Columns - 1;
            if (bottom > Rows - 1) bottom = Rows - 1;

            // Do offset and interpolation stuff
        }
    }
}

This should give you a random map, graph-paper effect and all.

(Caveat: I'm not familiar with Haxe, but have tested this in Javascript, which doesn't have an integer type. I've used Math-floor throughout, where you'll want to do it the Haxe way.)

Finally, it looks to me that you do too many passes. I'd base the power on the maximum of the two dimensions instead of the diagonal. You can also skip the last step where wthe width is near one.