artefacts during heightmap generation using plasma style fractal

Question

I've spent a few hours today researching how random terrain generation tends to be done and after reading about the plasma fractal (midpoint displacement and diamond square algo's) I decided to try and have a go at implementing one. My result was actually not terriable, but I have these horrible square/line/grid type artefacts that I just can not seem to get rid of!

When rendered as a gray scale image my height map looks something like: height map http://sphotos-d.ak.fbcdn.net/hphotos-ak-ash3/535816_10151739010123327_225111175_n.jpg

Obviously there is a fair amount of code involved in this but I will try to post what is only relevant. I've not not posted the code that turns it into a texture for example, but do not worry I have already tried just filling my height array with a smooth gradient and the texture comes out fine :)

I begin by setting the four corners of the map to random values between 0 and 1 and then start the recursive displacement algo:

    public void GenerateTerrainLayer()
    {  
        //set the four corners of the map to have random values
        TerrainData[0, 0] = (float)RandomGenerator.NextDouble();
        TerrainData[GenSize, 0] = (float)RandomGenerator.NextDouble();
        TerrainData[0, GenSize] = (float)RandomGenerator.NextDouble();
        TerrainData[GenSize, GenSize] = (float)RandomGenerator.NextDouble();

        //begin midpoint displacement algorithm...
        MidPointDisplace(new Vector2_I(0, 0), new Vector2_I(GenSize, 0), new Vector2_I(0, GenSize), new Vector2_I(GenSize, GenSize));
    }

TerrainData is simply a 2D array of floats*. Vector2_I is just my own integer vector class. The last four functions are MidPointDisplace which is the recursive function, CalculateTerrainPointData which averages 2 data values and adds some noise, CalculateTerrainPointData2 which averages 4 data values and adds some noise and has a slightly higher scale value (its only used for center points) and finally my noise function which atm is just some random noise and not a real noise like perlin etc. They look like this:

   private void MidPointDisplace(Vector2_I topleft, Vector2_I topright, Vector2_I bottomleft, Vector2_I bottomright)
    {
        //check size of square working on.. if its shorter than a certain amount stop the algo, we've done enough
        if (topright.X - topleft.X < DisplacementMaxLOD)
        {
            return;
        }


        //calculate the positions of all the middle points for the square that has been passed to the function
        Vector2_I MidLeft, MidRight, MidTop, MidBottom, Center;

        MidLeft.X = topleft.X;
        MidLeft.Y = topleft.Y + ((bottomleft.Y - topleft.Y) / 2);

        MidRight.X = topright.X;
        MidRight.Y = topright.Y + ((bottomright.Y - topright.Y) / 2);

        MidTop.X = topleft.X + ((topright.X - topleft.X) / 2);
        MidTop.Y = topleft.Y;

        MidBottom.X = bottomleft.X + ((bottomright.X - bottomleft.X) / 2);
        MidBottom.Y = bottomleft.Y;

        Center.X = MidTop.X;
        Center.Y = MidLeft.Y;

        //collect the existing data from the corners of the area passed to algo
        float TopLeftDat, TopRightDat, BottomLeftDat, BottomRightDat;

        TopLeftDat = GetTerrainData(topleft.X, topleft.Y);          
        TopRightDat = GetTerrainData(topright.X, topright.Y);          
        BottomLeftDat = GetTerrainData(bottomleft.X, bottomleft.Y);          
        BottomRightDat = GetTerrainData(bottomright.X, bottomright.Y);

        //and the center


        //adverage data and insert for midpoints..
        SetTerrainData(MidLeft.X, MidLeft.Y, CalculateTerrainPointData(TopLeftDat, BottomLeftDat, MidLeft.X, MidLeft.Y));
        SetTerrainData(MidRight.X, MidRight.Y, CalculateTerrainPointData(TopRightDat, BottomRightDat, MidRight.X, MidRight.Y));
        SetTerrainData(MidTop.X, MidTop.Y, CalculateTerrainPointData(TopLeftDat, TopRightDat, MidTop.X, MidTop.Y));
        SetTerrainData(MidBottom.X, MidBottom.Y, CalculateTerrainPointData(BottomLeftDat, BottomRightDat, MidBottom.X, MidBottom.Y));
        SetTerrainData(Center.X, Center.Y, CalculateTerrainPointData2(TopLeftDat, TopRightDat, BottomLeftDat, BottomRightDat, Center.X, Center.Y));


        debug_displacement_iterations++;

        //and recursively fire off new calls to the function to do the smaller squares
        Rectangle NewTopLeft = new Rectangle(topleft.X, topleft.Y, Center.X - topleft.X, Center.Y - topleft.Y);
        Rectangle NewTopRight = new Rectangle(Center.X, topright.Y, topright.X - Center.X, Center.Y - topright.Y);
        Rectangle NewBottomLeft = new Rectangle(bottomleft.X, Center.Y, Center.X - bottomleft.X, bottomleft.Y - Center.Y);
        Rectangle NewBottomRight = new Rectangle(Center.X , Center.Y, bottomright.X - Center.X, bottomright.Y - Center.Y);

        MidPointDisplace(new Vector2_I(NewTopLeft.Left, NewTopLeft.Top), new Vector2_I(NewTopLeft.Right, NewTopLeft.Top), new Vector2_I(NewTopLeft.Left, NewTopLeft.Bottom), new Vector2_I(NewTopLeft.Right, NewTopLeft.Bottom));
        MidPointDisplace(new Vector2_I(NewTopRight.Left, NewTopRight.Top), new Vector2_I(NewTopRight.Right, NewTopRight.Top), new Vector2_I(NewTopRight.Left, NewTopRight.Bottom), new Vector2_I(NewTopRight.Right, NewTopRight.Bottom));
        MidPointDisplace(new Vector2_I(NewBottomLeft.Left, NewBottomLeft.Top), new Vector2_I(NewBottomLeft.Right, NewBottomLeft.Top), new Vector2_I(NewBottomLeft.Left, NewBottomLeft.Bottom), new Vector2_I(NewBottomLeft.Right, NewBottomLeft.Bottom));
        MidPointDisplace(new Vector2_I(NewBottomRight.Left, NewBottomRight.Top), new Vector2_I(NewBottomRight.Right, NewBottomRight.Top), new Vector2_I(NewBottomRight.Left, NewBottomRight.Bottom), new Vector2_I(NewBottomRight.Right, NewBottomRight.Bottom));

    }

    //helper function to return a data value adveraged from two inputs, noise value added for randomness and result clamped to ensure a good value
    private float CalculateTerrainPointData(float DataA, float DataB, int NoiseX, int NoiseY)
    {
         return MathHelper.Clamp(((DataA + DataB) / 2.0f) + NoiseFunction(NoiseX, NoiseY), 0.0f, 1.0f) * 1.0f;
    }

    //helper function to return a data value adveraged from four inputs, noise value added for randomness and result clamped to ensure a good value
    private float CalculateTerrainPointData2(float DataA, float DataB, float DataC, float DataD, int NoiseX, int NoiseY)
    {
        return MathHelper.Clamp(((DataA + DataB + DataC + DataD) / 4.0f) + NoiseFunction(NoiseX, NoiseY), 0.0f, 1.0f) * 1.5f;
    }

    private float NoiseFunction(int x, int y)
    {
        return (float)(RandomGenerator.NextDouble() - 0.5) * 0.5f;
    }

Ok thanks for taking the time to look - hopefully someone knows where this grid-like pattern is appearing from :)

*edit - accidently wrote ints, corrected to floats

Answer 1

I identified 3 problems in your code. (2 of which are related)

You don't scale down the randomness in each step. There must be a reduction of the randomness in each step. Otherwise you get white(-ish) noise. You choose a factor (0.5-0.7 worked fine for my purposes) and multiply the reduction by alpha in each recursion and scale the generated random number by that factor.

You swapped the diamond and square step. First the diamonds, then the squares. The other way round is impossible (see next).

Your square step uses only points in one direction. This one probably causes the rectangular structures you are talking about. The squares must average the values to all four sides. This means that the square step depends on the point generated by the diamond step. And not only the diamond step of the rectangle you are currently looking at, also of the rectangles next to it. For values outside of the map, you can either wrap, use a fixed value or only average 3 values.

Answer 2

I see a problem in your CalculateTerrainPointData implementation: you're not scaling down the result of NoiseFunction with each iteration.

See this description of the Midpoint Displacement algorithm:

• Start with a single horizontal line segment.
  • Repeat for a sufficiently large number of times:
    • Repeat over each line segment in the scene:
      • Find the midpoint of the line segment.
      • Displace the midpoint in Y by a random amount.
      • Reduce the range for random numbers.

A fast way to do it in your code without changing too much is by adding some scale parameter to MidPointDisplace (with default set to 1.0f) and CalculateTerrainPointData; use it in CalculateTerrainPointData to multiply result of NoiseFunction; and reduce it with each recursive call to MidPointDisplace(..., 0.5f * scale).

Not sure though if that is the only cause to your image looking wrong or there are other problems.

Answer 3

According to Wikipedia's summary of midpoint displacement, only the average for the center most point get noise added to it - try only adding noise via CalculateTerrainPointData2 & removing the noise in CalculateTerrainPointData.