Unexpected Diamond square Algorithm results

Question

I'm currently trying to implement the Diamond Square algorithm and while the thing is somewhat working, I'm confused by the HeightMap.

Here it is :

As you can see the squares are clearly outlined by brighters values, while the losanges are outlined by darker values. I really cant understand why. I know that the size of the map is really small but I don't think that's the expected result anyway, and I got the same behavior with larger sizes.

Here's my code :

public class TerrainBuilder
{
    private Terrain Terrain = null;
    private Random r = new Random();

    private int espace;

    public void Init(Terrain _terrain)
    {
        Terrain = _terrain;
        espace = Terrain.SIZE - 1;
    }

    public void DiamondAlgoritm()
    {
        if (Terrain == null)
            return;
        //Initialization
        Terrain.HeightMap[0, 0] = r.Next() % 255;
        Terrain.HeightMap[0, Terrain.SIZE - 1] = r.Next() % 255;
        Terrain.HeightMap[Terrain.SIZE - 1, 0] = r.Next() % 255;
        Terrain.HeightMap[Terrain.SIZE - 1, Terrain.SIZE - 1] = r.Next() % 255;

        //randominess
        int decalage = 128;

        while (espace > 1)
        {
            int demiSpace = espace / 2;
            //diamond phase
            for (int i = demiSpace; i < espace; i = i + espace)
            {
                for (int j = demiSpace; j < espace; j = j + espace)
                {
                    var avg = Terrain.HeightMap[i + demiSpace, j + demiSpace] + Terrain.HeightMap[i + demiSpace, j - demiSpace] + Terrain.HeightMap[i - demiSpace, j + demiSpace] + Terrain.HeightMap[i - demiSpace, j - demiSpace];
                    avg /= 4;
                    Terrain.HeightMap[i, j] = Normalize(avg + r.Next() % decalage);
                }
            }
            //carre phase
            for (int i = 0; i < Terrain.SIZE; i += demiSpace)
            {
                int delay = 0;
                if (i % espace == 0)
                    delay = demiSpace;


                for (int j = delay; j < Terrain.SIZE; j += espace)
                {
                    double somme = 0;
                    int n = 0;

                    if (i >= demiSpace)
                        somme = somme + Terrain.HeightMap[i - demiSpace, j];
                    n = n + 1;

                    if (i + demiSpace < Terrain.SIZE)
                        somme = somme + Terrain.HeightMap[i + demiSpace, j];
                    n = n + 1;

                    if (j >= demiSpace)
                        somme = somme + Terrain.HeightMap[i, j - demiSpace];
                    n = n + 1;

                    if (j + demiSpace < Terrain.SIZE)
                        somme = somme + Terrain.HeightMap[i, j + demiSpace];
                    n = n + 1;


                    Terrain.HeightMap[i, j] = Normalize(somme / n + r.Next() % decalage);
                }
            }
            espace = demiSpace;
        }



    }

    private double Normalize(double value)
    {
        return Math.Max(Math.Min(value, 255), 0);
    }
}

I would like some help to understand this problem.

Answer 1

During the diamond phase, you don't iterate over the whole map. You only calculate the first square (equal to espace).

Change your loop termination conditions like this:

for (int i = demiSpace; i < Terrain.SIZE; i = i + espace)        
{
    for (int j = demiSpace; j < Terrain.SIZE; j = j + espace)
    {
        var avg = Terrain.HeightMap[i + demiSpace, j + demiSpace] +
                    Terrain.HeightMap[i + demiSpace, j - demiSpace] +
                    Terrain.HeightMap[i - demiSpace, j + demiSpace] +
                    Terrain.HeightMap[i - demiSpace, j - demiSpace];
        avg /= 4;
        Terrain.HeightMap[i, j] = Normalize(avg + r.Next() % decalage);
    }
}

Also, you never adjust your randomness variable (decalage), which should get smaller as you reduce the size of espace.