Problème de génération de terrain diamant carré

J'ai implémenté un algorithme de diamant carré selon cet article: http://www.lighthouse3d.com/opengl/terrain/index.php?mpd2

Le problème est que j'ai ces falaises abruptes partout sur la carte. Cela se produit sur les bords, lorsque le terrain est subdivisé récursivement:

Voici la source:

void DiamondSquare(unsigned x1,unsigned y1,unsigned x2,unsigned y2,float range)
    {      
    int c1 = (int)x2 - (int)x1;
    int c2 = (int)y2 - (int)y1;
    unsigned hx = (x2 - x1)/2;
    unsigned hy = (y2 - y1)/2;
    if((c1 <= 1) || (c2 <= 1))
            return;

// Diamond stage
float a = m_heightmap[x1][y1];
float b = m_heightmap[x2][y1];
float c = m_heightmap[x1][y2];
float d = m_heightmap[x2][y2];
float e = (a+b+c+d) / 4 + GetRnd() * range;

m_heightmap[x1 + hx][y1 + hy] = e;

// Square stage
float f = (a + c + e + e) / 4 + GetRnd() * range;
m_heightmap[x1][y1+hy] = f;
float g = (a + b + e + e) / 4 + GetRnd() * range;
m_heightmap[x1+hx][y1] = g;
float h = (b + d + e + e) / 4 + GetRnd() * range;
m_heightmap[x2][y1+hy] = h;
float i = (c + d + e + e) / 4 + GetRnd() * range;
m_heightmap[x1+hx][y2] = i;

DiamondSquare(x1, y1, x1+hx, y1+hy, range / 2.0);   // Upper left
DiamondSquare(x1+hx, y1, x2, y1+hy, range / 2.0);   // Upper right
DiamondSquare(x1, y1+hy, x1+hx, y2, range / 2.0);   // Lower left
DiamondSquare(x1+hx, y1+hy, x2, y2, range / 2.0);       // Lower right

}

Paramètres: (x1, y1), (x2, y2) - coordonnées qui définissent une région sur une carte de hauteur (par défaut (0,0) (128,128)). plage - essentiellement max. la taille. (par défaut 32)

De l'aide serait grandement appréciée.

Dans chaque niveau de subdivision, l'étape "carré" s'appuie sur les résultats de "l'étape diamant". Mais cela tient également compte du pas de diamant produit dans la cellule adjacente, dont vous ne tenez pas compte. Je réécrirais la fonction DiamondSquare pour itérer la largeur en premier, au lieu de la profondeur en premier comme vous l'avez actuellement.

Votre premier problème est que, puisque vous recalculez deux fois les bords carrés, il ignore la contribution du point central adjacent. Par exemple, dans l'article que vous référencez,

P = (J + G + K + E)/4 + RAND(d)

mais votre code fait effectivement

P = (J + G + J + E)/4 + RAND(d)

c'est-à-dire qu'il tient compte deux fois du point central actuel , et non du point central correspondant. C'est pourquoi vous devez aller en premier, afin que les points centraux précédents soient calculés.

Voici mon code et la sortie:.

void DiamondSquare(unsigned x1, unsigned y1, unsigned x2, unsigned y2, float range, unsigned level) {
    if (level < 1) return;

    // diamonds
    for (unsigned i = x1 + level; i < x2; i += level)
        for (unsigned j = y1 + level; j < y2; j += level) {
            float a = m_heightmap[i - level][j - level];
            float b = m_heightmap[i][j - level];
            float c = m_heightmap[i - level][j];
            float d = m_heightmap[i][j];
            float e = m_heightmap[i - level / 2][j - level / 2] = (a + b + c + d) / 4 + GetRnd() * range;
        }

    // squares
    for (unsigned i = x1 + 2 * level; i < x2; i += level)
        for (unsigned j = y1 + 2 * level; j < y2; j += level) {
            float a = m_heightmap[i - level][j - level];
            float b = m_heightmap[i][j - level];
            float c = m_heightmap[i - level][j];
            float d = m_heightmap[i][j];
            float e = m_heightmap[i - level / 2][j - level / 2];

            float f = m_heightmap[i - level][j - level / 2] = (a + c + e + m_heightmap[i - 3 * level / 2][j - level / 2]) / 4 + GetRnd() * range;
            float g = m_heightmap[i - level / 2][j - level] = (a + b + e + m_heightmap[i - level / 2][j - 3 * level / 2]) / 4 + GetRnd() * range;
        }

    DiamondSquare(x1, y1, x2, y2, range / 2, level / 2);
}

Une possibilité est que vous preniez un raccourci avec votre implémentation que l'algorithme sur votre page liée ne fait pas.

Pour la scène carrée, vous calculez la hauteur des points avec

float f = (a + c + e + e) / 4 + GetRnd() * range;
m_heightmap[x1][y1+hy] = f;

que l'algorithme de la page indique à utiliser si vous enveloppez votre carte. Cela donne l'impression que vous utilisez la valeur de hauteur du "carré suivant" pour calculer celle-ci. Dans le premier cas le plus simple, le point central (avec la hauteur «e») est utilisé à gauche et à droite pour calculer f.

Cependant, l'algorithme que vous référencez vous permet d'utiliser les valeurs réelles des autres carrés / diamants pour vous aider à calculer la valeur de la hauteur de ce point carré. Dans leur algorithme, le deuxième point de niveau est calculé avec la formule suivante:

N = (K + A + J + F)/4 + RAND(d)

Remarquez l'absence de duplication d'une valeur là-dedans?

Je pense que vous voudrez peut-être essayer d'utiliser les versions non enveloppantes des formules données, celles-ci résumeront mieux, je pense.

F = (A + C + E)/3 + ...
    instead of
F = (A + C + E + E)/4 + ...