Diamond Square Algorithm

For my project, I’ve implemented the Diamond Square algorithm to create a height map (currently out of quads) for me, but there are some bugs I can’t identify in the code.

It seems that ONE value on top of the height map (shown here) doesn’t get set, causing the black spot, and I can’t figure out what causes the blocky appearance of the map either.

Any help is appreciated, and tips on increasing performance would be a great help too.

Edit: The black spot is supposed to be created on the “square” part of the function, but I can’t find any problems with it as is.

Edit2: Ha! It seems I need to do “int level = squareSize.x - 1” to account for the extra space, so the black spot is solved. Code updated accordingly. Blocky problem still exists, however.

Example Height Map:

[30890-height+map.png|30890]

Algorithm Code:

    public static float[,] DiamondSquare(int x, int y)
    {
        //Get the square + 1 size for our algorithm, to be cut down to x,y size at end.
        Point squareSize = FindSquareSize(x,y);

        float[,] squareValues = new float[squareSize.x, squareSize.y];

        //Set the corner values.
        squareValues[0, 0] = 0.5f;
        squareValues[squareSize.x - 1, 0] = 0.5f;
        squareValues[0, squareSize.y - 1] = 0.5f;
        squareValues[squareSize.x - 1, squareSize.y - 1] = 0.5f;


        float variation = 0.5f; //Roughness of the map. Decreases as the algorithm creates the map.
        int level = squareSize.x - 1; //The current chunk the algorithm is working on. Whole, half, quaters, eighths, etc.
        //Debug.Log("Initial level is: " + level);

        //Do the algorithm here.
        while(level > 1)
        {
            int halfstep = level / 2;
            //Debug.Log("Half Step is: " + halfstep);

            //Do Diamond.
            for (int i = halfstep; i < squareSize.x; i += level)
            {
                for (int j = halfstep; j < squareSize.x; j += level)
                {
                    //Bottom left is (0,0)
                    float a = squareValues[i - halfstep, j - halfstep]; //Bottom left.
                    float b = squareValues[i + halfstep, j - halfstep]; //Bottom Right.
                    float c = squareValues[i - halfstep, j + halfstep]; //Top Left.
                    float d = squareValues[i + halfstep, j + halfstep]; //Top Right.

                    float e = ((a + b + c + d) / 4f) + Random.Range(0f, 1f) * variation; //Center

                    squareValues[i, j] = e;

                    //Debug.Log("Did a Diamond!");
                }
            }

            int currentColumn = 0;

            //Do Square.
            for (int i = 0; i < squareSize.x; i += halfstep)
            {
                currentColumn++;
                //If this is an odd column.
                if (currentColumn % 2 == 1)
                {
                    for (int j = halfstep; j < squareSize.y; j += level)
                    {
                        float a, b, c, d, e;

                        bool threePoints = false;

                        try { a = squareValues[i, j + halfstep]; } //Top
                        catch { a = 0; threePoints = true; }

                        try { b = squareValues[i, j - halfstep]; } //Bottom
                        catch { b = 0; threePoints = true; }

                        try { c = squareValues[i - halfstep, j]; } //Left
                        catch { c = 0; threePoints = true; }

                        try { d = squareValues[i + halfstep, j]; } //Right
                        catch { d = 0; threePoints = true; }

                        if (threePoints)
                        {
                            e = ((a + b + c + d) / 3f) + Random.Range(0f, 1f) * variation;
                        }
                        else
                        {
                            e = ((a + b + c + d) / 4f) + Random.Range(0f, 1f) * variation;
                        }

                        squareValues[i, j] = e;

                        //Debug.Log("Did a Square!");
                    }
                }
                //Else this is an even column.
                else
                {
                    for (int j = 0; j < squareSize.y; j += level)
                    {
                        float a, b, c, d, e;

                        bool threePoints = false;

                        try { a = squareValues[i, j + halfstep]; } //Top
                        catch { a = 0; threePoints = true; }

                        try { b = squareValues[i, j - halfstep]; } //Bottom
                        catch { b = 0; threePoints = true; }

                        try { c = squareValues[i - halfstep, j]; } //Left
                        catch { c = 0; threePoints = true; }

                        try { d = squareValues[i + halfstep, j]; } //Right
                        catch { d = 0; threePoints = true; }

                        if (threePoints)
                        {
                            e = ((a + b + c + d) / 3f) + Random.Range(0f, 1f) * variation;
                        }
                        else
                        {
                            e = ((a + b + c + d) / 4f) + Random.Range(0f, 1f) * variation;
                        }

                        squareValues[i, j] = e;

                        //Debug.Log("Did a Square!");
                    }
                }
            }

            //Reduce range and variation.
            level /= 2;
            variation /= 2;
            
        }

Quad Maker:

    private IEnumerator createHeightMap(float[,] heightArray)
    {
        for(int i = 0; i < heightArray.GetLength(0); i++)
        {
            for(int j=0; j < heightArray.GetLength(1); j++)
            {
                GameObject thisObject = GameObject.CreatePrimitive(PrimitiveType.Quad);
                thisObject.transform.position = new Vector3(i, j, 0);
                float value = heightArray[i,j];
                thisObject.renderer.material.color = new Color(value, value, value, 1);
            }
            yield return new WaitForEndOfFrame();
        }
        yield return null;
    }

Apologies, if this isn’t the right place to post this.

Changing the line int level = squareSize.x into int level = squareSize.x - 1 fixed the black spot problem, and tweaking the “variation” variable (start at a higher number, and drop off more quickly) seemed to fix the blocky-ness too, so enjoy the free code!

[30896-height+map+2.png|30896]