Algorytm przesunięcia punktu środkowego

Pytanie to wynikało głównie z desperacji , po kilku godzinach próbowania rozwiązania problemu.

Jeśli spojrzysz na powyższy obrazek, powinieneś zobaczyć, że mój algorytm przesunięcia punktu środkowego działa (nieco) z powodzeniem; w tworzeniu dość spójnego wzoru szumu.

Pozostawia jednak na obrazie czarną kropkowaną siatkę i nie mam pojęcia, dlaczego. Mogę przewidzieć, że jest to problem matematyczny, ale po prostu tego nie widzę; nie zostało to również wskazane w żadnych zasobach internetowych jako możliwy problem; więc każda pomoc będzie doceniona w tropieniu tego błędu.

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

Jeśli masz jakieś wskazówki lub zasoby inne niż http://www.gameprogrammer.com/fractal.html i http://www.lighthouse3d.com/opengl/terrain/index.php?mpd2 do generowania terenu na podstawie fraktali, doceniam je również jako komentarze.

Edytować:

Jest to nowy obraz, zgodnie z sugestią Fabian (ty), jednak wciąż ma pewne dziwne dziwactwa, które powinieneś natychmiast zobaczyć (wszędzie małe wgłębienia).

Co może być przyczyną tego dziwnego zachowania? Zaktualizowany kod źródłowy: http://www.pastie.org/1924223

Edytować:

Ogromne podziękowania dla Fabiana za znalezienie błędu sprawdzania granic, dla zainteresowanych, oto aktualne rozwiązanie jako 512x512 png. I aktualny kod źródłowy (zmodyfikowany przez Fabiana) .

Edytuj (lata później): wersja Python https://gist.github.com/dcousens/5573724#file-mdp-py

Algorytm rekurencyjnie dodaje wartość, ale wartość może być dodatnia lub ujemna (zwykle + -1 / (2 ^ oktawy))

Jeśli zaczniesz od zera i dodasz tylko wartości dodatnie, możesz tylko iść w górę, i dlatego widzisz ściągnięte wierzchołki.

spróbuj zacząć od 127 zamiast zera dla czterech rogów, a także spróbuj podpisać znak (następnie sprawdzając swoje granice zarówno na górze, jak i na dole)

EDYTOWAĆ

więc dwie główne rzeczy muszą się zmienić w głównym (64 >> i), aby uzyskać efekt połowy w każdej oktawie, a także funkcję wyjściową (tę, która odwzorowuje końcową [] [] tp na imgdta [], po prostu trzeba włożyć

imgdta [(i * n) + j] = 128 + końcowy [i] [j];

zamiast bloku if else.

jeszcze jedno, nie jestem pewien, dlaczego, ale sprawdzenie limitu kończy się niepowodzeniem (to jest linie 38 i 65), jeśli całkowicie go usuniesz, zauważysz również kilka nowych ciemnych plam, więc myślę, że może być konieczne wypromowanie do większego typu przed wykonaniem granic sprawdź, czy chcesz uzyskać bardziej hałaśliwy obraz za pomocą „64 / i”.

KOLEJNA EDYCJA

właśnie dowiedziałem się, co to jest, porównujesz z „r”, a nie „rv”, w kontroli granic. Oto poprawiony kod: http://pastie.org/1927076

Dwie rzeczy, które wyskakują:

1. Czy masz ważny powód, aby to zrobić w punkcie stałym? Nie ma w tym nic złego i istnieje wiele powodów, aby z niego korzystać (przede wszystkim wymagania dotyczące pamięci, jeśli planujesz przejść do OGROMNEJ mapy), ale na pewno zacznę od wersji zmiennoprzecinkowej algorytmu i przekonwertuj go do stałego punktu po uruchomieniu; powinno to, jeśli nic innego, wyeliminować jedno prawdopodobne źródło błędów (w szczególności podejrzewam, że twoje zaciskanie może powodować problemy i warunki, kiedy należy dodać / odjąć rv).
2. Chociaż trudno jest stwierdzić na podstawie kodu, który widzę, nie wydaje się, aby twoje losowe przesunięcie wysokości skalowało się wraz z poziomem, a to w połączeniu z problemem w (1) może powodować niektóre problemy - nie powinieneś być wypieranie o tę samą kwotę na każdym poziomie.

Aha, i jedna nie algorytmiczna rzecz: Zdecydowanie odradzam przydzielanie w twojej funkcji mdp (); przekaż dwie różne już przydzielone tablice i wykonaj iterację „w miejscu”, przechodząc od jednej do drugiej. Jeśli nic więcej, pozwoli ci to ping-ponga do przodu i do tyłu podczas wykonywania warstw, zamiast konieczności przydzielania nowej tablicy za każdym razem.

W związku z powyższym obecnie nie usuwasz przydzielanej pamięci. Aby temu zaradzić, zmień wiersz 104 z:

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

do

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

i dodaj to po zapisaniu do pliku TGA:

for (unsigned i = 0; i < n; ++i)
  delete[] final[i];
delete[] final;