Problem bei der Erzeugung von Diamant-Quadrat-Gelände

11

Ich habe einen Diamant-Quadrat-Algorithmus gemäß diesem Artikel implementiert: http://www.lighthouse3d.com/opengl/terrain/index.php?mpd2

Das Problem ist, dass ich diese steilen Klippen überall auf der Karte habe. Es passiert an den Rändern, wenn das Gelände rekursiv unterteilt ist:

Geben Sie hier die Bildbeschreibung ein

Hier ist die Quelle:

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

}}

Parameter: (x1, y1), (x2, y2) - Koordinaten, die einen Bereich auf einer Höhenkarte definieren (Standard (0,0) (128,128)). Reichweite - grundsätzlich max. Höhe. (Standard 32)

Hilfe wäre sehr dankbar.

Kafka
quelle
Ohne genau auf Ihren Code zu schauen, haben Sie wahrscheinlich die falschen Ecken in den falschen Aufrufen in den 4 rekursiven Aufrufen am Ende. Die Karte sieht so aus, als würde jedes Quadrat gedreht / gespiegelt, bevor der nächste Satz berechnet wird, wodurch die Karte auf seltsame Klippen unterteilt wird. Die Unterkante des oberen rechten Quadrats sieht so aus, als würde sie mit der rechten Kante des oberen linken Quadrats übereinstimmen, und so weiter.
DampeS8N
Ich bin mir nicht sicher was du meinst. Der Mittelpunkt des Koordinatensystems befindet sich in der oberen linken Ecke, die x-Achse zeigt nach rechts und y nach unten. In der ersten Iteration (x1 = 0, y1 = 0) ist (x2 = 128, y2 = 128) und (x1 + hx = 64, y1 + hy = 64) die Mitte des Quadrats. Das Quadrat ist somit in 4 Teilquadrate unterteilt: ((0,0) (64,64)), ((64,0) (128,64)), ((0,64) (64,128)) und ((64,) 64) (128, 128)). Sieht gut aus für mich ...
Kafka

Antworten:

11

In jeder Unterteilungsebene beruht der "quadratische" Schritt auf den Ergebnissen des "Diamantschritts". Es berücksichtigt aber auch den Diamantschritt, der in der benachbarten Zelle erzeugt wird und den Sie nicht berücksichtigen. Ich würde die DiamondSquare-Funktion neu schreiben, um die Breite zuerst zu wiederholen, anstatt die Tiefe zuerst, wie Sie sie derzeit haben.

Ihr erstes Problem ist, dass Sie den Beitrag des benachbarten Mittelpunkts ignorieren, da Sie die quadratischen Kanten zweimal neu berechnen. In dem Artikel, auf den Sie verweisen,

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

aber Ihr Code tut effektiv

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

dh es wird der aktuelle Mittelpunkt zweimal berücksichtigt, nicht der benachbarte Mittelpunkt. Aus diesem Grund müssen Sie zuerst die Breite festlegen, damit die vorherigen Mittelpunkte berechnet werden.

Hier ist mein Code und die Ausgabe :.

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);
}

http://i.imgur.com/laBhN.png

Jimmy
quelle
Ja, ich habe auch nach dem Vorbild der Breite gedacht. Diese Fraktale verursachen mir immer Probleme. So war es auch mit Perlin Noise und L-Systemen. Du bist unglaublich.
Kafka
3

Eine Möglichkeit besteht darin, dass Sie mit Ihrer Implementierung eine Verknüpfung verwenden, die der Algorithmus auf Ihrer verlinkten Seite nicht verwendet.

Für die quadratische Bühne berechnen Sie die Höhe der Punkte mit

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

Der Algorithmus der Seite gibt an, dass er verwendet werden soll, wenn Sie Ihre Karte einpacken. Dies gibt den Anschein, dass Sie den Höhenwert des "nächsten Quadrats über" verwenden, um diesen zu berechnen. Im einfachsten ersten Fall wird der Mittelpunkt (mit der Höhe 'e') sowohl auf der linken als auch auf der rechten Seite verwendet, um f zu berechnen.

Bei dem Algorithmus, auf den Sie verweisen, verwenden Sie jedoch die tatsächlichen Werte der anderen Quadrate / Diamanten, um den Wert der Höhe dieses quadratischen Punkts zu berechnen. In ihrem Algorithmus wird der Punkt der zweiten Ebene mit der folgenden Formel berechnet:

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

Beachten Sie das Fehlen einer doppelten Wertschöpfung?

Ich denke, Sie möchten vielleicht versuchen, die nicht umhüllenden Versionen der angegebenen Formeln zu verwenden. Diese werden sich meiner Meinung nach besser wiederholen.

F = (A + C + E)/3 + ...
    instead of
F = (A + C + E + E)/4 + ...
fnord
quelle
Danke, das war eine hilfreiche Beobachtung. Ich glaube, ich habe meine Läsion gelernt, nicht direkt zur Codierung zu springen, wenn ich die Gleichungen sehe.
Kafka
Du bist immer willkommen. Ich mache es auch selbst viel Zeit ... "Schau, etwas, das ich codieren kann. Muss. Code. Jetzt!"
Fnord