Mittelpunktverschiebungsalgorithmus

14

MDPMDP

Diese Frage ist hauptsächlich aus purer Verzweiflung entstanden , nachdem ich mehrere Stunden damit verbracht hatte, das Problem herauszufinden.

Wenn Sie das obige Bild betrachten, sollten Sie feststellen, dass mein Algorithmus für die Verschiebung des Mittelpunkts (etwas) erfolgreich funktioniert. bei der Erzeugung eines etwas kohärenten Rauschmusters.

Es hinterlässt jedoch ein schwarz gepunktetes Gitter auf dem Bild, und ich habe keine Ahnung warum. Ich kann voraussehen, dass dies ein Problem in der Mathematik ist, aber ich kann es einfach nicht sehen. Dies wurde auch in Online-Ressourcen nicht als mögliches Problem herausgestellt. Daher ist jede Hilfe bei der Suche nach diesem Bug willkommen.

unsigned char** mdp(unsigned char** base, unsigned base_n, unsigned char r) {
    size_t n = (2 * base_n) - 1;

    unsigned char** map = new unsigned char*[n];
    for (unsigned i = 0; i < n; ++i) map[i] = new unsigned char[n];

    // Resize
    // 1 0 1
    // 0 0 0
    // 1 0 1
    for (size_t i = 0; i < n; i += 2) {
        for (size_t j = !(i % 2 == 0); j < n; j += 2) {
            map[i][j] = base[i / 2][j / 2];
        }
    }

    // Diamond algorithm
    // 0 0 0
    // 0 X 0
    // 0 0 0
    for (size_t i = 1; i < n; i += 2) {
        for (size_t j = 1; j < n; j += 2) {
            unsigned char& map_ij = map[i][j];

            unsigned char a = map[i - 1][j - 1];
            unsigned char b = map[i - 1][j + 1];
            unsigned char c = map[i + 1][j - 1];
            unsigned char d = map[i + 1][j + 1];
            map_ij = (a + b + c + d) / 4;

            unsigned char rv = std::rand() % r;
            if (map_ij + r < 255) map_ij += rv; // EDIT: <-- thanks! the bug! `map_ij + rv`, not `r`
            else map_ij = 255;
        }
    }

    // Square algorithm
    // 0 1 0
    // 1 0 1
    // 0 1 0
    for (size_t i = 0; i < n; ++i) {
        for (size_t j = (i % 2 == 0); j < n; j += 2) {
            unsigned char& map_ij = map[i][j];

            // get surrounding values
            unsigned char a = 0, b = a, c = a, d = a;
            if (i != 0) a = map[i - 1][j];
            if (j != 0) b = map[i][j - 1];
            if (j + 1 != n) c = map[i][j + 1];
            if (i + 1 != n) d = map[i + 1][j];

            // average calculation
            if (i == 0) map_ij = (b + c + d) / 3;
            else if (j == 0) map_ij = (a + c + d) / 3;
            else if (j + 1 == n) map_ij = (a + b + d) / 3;
            else if (i + 1 == n) map_ij = (a + b + c) / 3;
            else map_ij = (a + b + c + d) / 4;

            unsigned char rv = std::rand() % r;
            if (map_ij + r < 255) map_ij += rv;
            else map_ij = 255;
        }

    }

    return map;
}

Wenn Sie andere Tipps oder Ressourcen als http://www.gameprogrammer.com/fractal.html und http://www.lighthouse3d.com/opengl/terrain/index.php?mpd2 für die fraktalbasierte Geländegenerierung haben, würde ich schätze sie auch als Kommentare.

Bearbeiten:

MDP

Dies ist das neue Bild, wie von Fabian vorgeschlagen (ty), es weist jedoch noch einige seltsame Macken auf, die Sie sofort erkennen sollten (überall kleine "Grübchen").

Was könnte dieses seltsame Verhalten verursachen? Aktualisierter Quellcode: http://www.pastie.org/1924223

Bearbeiten:

Vielen Dank an Fabian, der den Fehler beim Überprüfen der Grenzen gefunden hat. Für alle Interessierten ist hier die aktuelle Lösung als 512x512 png. Und aktueller Quellcode (modifiziert von Fabian) . MDP

Bearbeiten (Jahre später): Python-Version https://gist.github.com/dcousens/5573724#file-mdp-py

gebremster Kaviar
quelle
Auf den Bildern sieht es so aus, als ob sich jeder der Punkte auf der gleichen Höhe befindet. Sind auch die Ecken gleich hoch?
deft_code
1
Für das, was es wert ist, sehen Ihre Bilder sehr hübsch aus. :)
ChrisE
scrand (): Ich bin mir nicht ganz sicher, ob ich das verstehe - soll das ein vorzeichenbehaftetes Zeichen im Intervall (-r / 2, r / 2) zurückgeben? Die Grübchen scheinen mir sowieso irgendwie das Ergebnis zu sein Die angrenzenden Bereiche scheinen plötzlich schwarz zu schießen und klettern dann wieder nach weiß. Insgesamt sieht es auch so aus, als ob es scharfe Streifen gibt, die mir wieder suggerieren, dass Sie vielleicht überlaufen Höhere Genauigkeit (z. B. Ganzzahl) und anschließende Begrenzung der Werte auf den Bereich [0,256] oder [-128,127]
ChrisE
Das Problem wurde unten gelöst, weil ich den Bereich des Zufallswerts und nicht dessen tatsächlichen Wert überprüfte. Die scrand () war eine vorübergehende 'Rauschen' Funktion ideal Rückkehr [-128, 127]
deceleratedcaviar
Achso cool! Freut mich zu hören, dass es jetzt funktioniert.
ChrisE

Antworten:

12

Der Algorithmus addiert rekursiv einen Wert, aber der Wert kann positiv oder negativ sein (normalerweise + -1 / (2 ^ Oktave))

Wenn Sie bei Null beginnen und nur positive Werte hinzufügen, können Sie nur nach oben gehen, und aus diesem Grund werden die Scheitelpunkte nach unten gezogen.

Versuchen Sie, für die vier Ecken bei 127 anstatt bei Null zu beginnen, und versuchen Sie auch, ein Zeichen mit Vorzeichen zu verwenden (überprüfen Sie dann Ihre Grenzen oben und unten).

BEARBEITEN

Es müssen also noch zwei Dinge im Hauptbereich (64 >> i) geändert werden, um den halben Effekt bei jeder Oktave zu erzielen, und auch Ihre Ausgangsfunktion (diejenige, die das endgültige [] [] bis zum imgdta [] abbildet, Sie gerade hineinstecken müssen

imgdta [(i * n) + j] = 128 + final [i] [j];

eher als der if else Block.

Eine andere Sache, ich bin mir nicht sicher warum, aber Ihre Begrenzungsprüfung schlägt fehl (das sind die Zeilen 38 und 65). Wenn Sie die Prüfung vollständig entfernen, bemerken Sie auch einige neue dunkle Flecken, so dass Sie wahrscheinlich auf einen größeren Typ umsteigen müssen bevor Sie die Schranken ziehen, prüfen Sie, ob Sie mit "64 / i" ein rauschärmeres Bild erhalten möchten.

EINE ANDERE BEARBEITUNG

Ich habe gerade herausgefunden, was es war, und Sie vergleichen es mit 'r' und nicht mit 'rv' in der Schrankenprüfung. Hier ist der feste Code: http://pastie.org/1927076

Richard Fabian
quelle
Dies war definitiv der bessere Weg, aber es gibt noch keine Zigarre. Es scheint, dass mein Bild immer noch einige "Macken" hat. Ich habe den ursprünglichen Beitrag aktualisiert.
verzögerte
nicht sicher, aber Zeile 93 sieht falsch aus, 64 / i muss möglicherweise 64 >> i sein (wie Sie die Hälfte des Effekts pro Oktave)
Richard Fabian
Ähhh!! Vielen Dank, das kann ich nicht glauben, ich wusste, dass es für dieses zweite Problem etwas Dummes sein würde. Liebte Ihren notdürftigen TGA-Code, sorry, ich hätte Ihnen den Ärger ersparen und den Header aufsetzen sollen.
verzögerte
3

Zwei Dinge, die herausspringen:

  1. Haben Sie einen zwingenden Grund, dies in Festkomma zu tun? Es ist an sich nichts Falsches daran und es gibt viele Gründe für die Verwendung (vor allem Speicherbedarf, wenn Sie vorhaben, auf eine RIESIGE Karte umzusteigen), aber ich würde definitiv mit einer Gleitkommaversion des Algorithmus beginnen und konvertieren Sie es in einen festen Punkt, nachdem Sie es zum Laufen gebracht haben; das sollte, wenn nichts anderes, eine plausible Fehlerquelle beseitigen (insbesondere vermute ich, dass Ihre Klemmung Probleme verursacht und die Bedingungen für das Hinzufügen / Entfernen von rv).
  2. An dem Code, den ich sehe, ist es zwar schwer zu erkennen, aber es scheint nicht so, als ob Ihre zufällige Höhenverschiebung mit dem Level skaliert. In Kombination mit dem Problem in (1) kann dies zu einigen Problemen führen - das sollten Sie nicht Verdrängung um den gleichen Betrag auf jeder Ebene.

Oh, und eine nicht algorithmische Sache: Ich empfehle dringend, keine Zuweisungen in Ihrer mdp () - Funktion vorzunehmen. Übergeben Sie zwei verschiedene, bereits zugewiesene Arrays, und führen Sie die Iteration direkt von einem zum anderen durch. Wenn nichts anderes, können Sie beim Durchführen der Ebenen Ping-Pong spielen, anstatt jedes Mal ein neues Array zuweisen zu müssen.

Steven Stadnicki
quelle
Einige gute Punkte, offensichtlich versuche ich nur, den Algorithmus richtig zu machen, die Implementierung ist alles andere als ideal, ich räume an dieser Stelle nicht einmal den Speicher auf: P.
verlangsamt
Zu diesem Zeitpunkt beträgt die Skalierung über die Durchläufe 64 / i. Dies werde ich natürlich später ändern, aber es erklärt nicht wirklich den gegenwärtig erlebten Grübcheneffekt. : S
verzögerte
0

Darüber hinaus löschen Sie derzeit nicht den zugewiesenen Speicher. Um dies zu beheben, ändern Sie Zeile 104 von:

for (unsigned i = 1; i < 6; ++i) final = mdp(final, n, 64 / i);

zu

for (unsigned i = 1; i < 6; ++i) {
  signed char** new_final = mdp(final, n, 64 / i);
  for (unsigned i = 0; i < n; ++i)
    delete[] final[i];
  delete[] final;
  final = new_final;
}

und fügen Sie dies hinzu, nachdem Sie in die tga-Datei geschrieben haben:

for (unsigned i = 0; i < n; ++i)
  delete[] final[i];
delete[] final;
dma
quelle
Ich bin mir sehr bewusst, wie man den Speicher aufräumt, aber da dies nur ein Algorithmusprototyp war und neu geschrieben werden würde, um Vektoren zu verwenden, wollte ich nur sicherstellen, dass er korrekt ist.
verzögerte