Algoritmo de desplazamiento del punto medio

14

MDPMDP

Esta pregunta surgió principalmente por pura desesperación , después de pasar varias horas tratando de resolver el problema.

Si echas un vistazo a la imagen de arriba, deberías ver que mi algoritmo de algoritmo de desplazamiento del punto medio funciona (algo) con éxito; en producir un patrón de ruido algo coherente.

Sin embargo, está dejando una cuadrícula de puntos negros en la imagen, y no tengo idea de por qué. Puedo prever que esto sea un problema en las matemáticas, pero simplemente no puedo verlo; ni se señaló esto en ningún recurso en línea como posible problema; entonces cualquier ayuda será apreciada en la búsqueda de este error.

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

Si tiene algún consejo o recurso que no sea http://www.gameprogrammer.com/fractal.html y http://www.lighthouse3d.com/opengl/terrain/index.php?mpd2 para la generación de terreno basada en fractales, lo haría los aprecio como comentarios también.

Editar:

MDP

Esta es la nueva imagen, según la sugerencia de Fabians (ty), sin embargo, todavía tiene algunas peculiaridades extrañas, que debería poder ver de inmediato (pequeños 'hoyuelos' en todas partes).

¿Qué podría estar causando este extraño comportamiento? Código fuente actualizado: http://www.pastie.org/1924223

Editar:

Muchas gracias a Fabian por encontrar el error de verificación de límites, para aquellos interesados, aquí está la solución actual como 512x512 png. Y el código fuente actual (modificado por Fabian) . MDP

Editar (años después): versión de Python https://gist.github.com/dcousens/5573724#file-mdp-py

caviar desacelerado
fuente
En las imágenes, parece que cada uno de los puntos está a la misma altura. ¿Están las esquinas a la misma altura también?
deft_code
1
Por lo que vale, sus imágenes se ven muy bonitas. :)
ChrisE
scrand (): no estoy completamente seguro de entender: ¿se supone que esto devuelve un carácter firmado en el intervalo (-r / 2, r / 2]? Los hoyuelos, para mí, de todos modos, parecen algo así como el resultado de desbordamiento. Las áreas adyacentes parecen dispararse repentinamente en negro, y luego subir de nuevo a blanco. En general, también parece que hay bandas agudas, sugiriéndome nuevamente que está desbordando, tal vez. ¿Le importaría hacer las matemáticas en un mayor precisión (por ejemplo, entero), y luego ajustar los valores al rango [0,256] o [-128,127]
ChrisE
El problema se resolvió a continuación, fue porque estaba comprobando los límites contra el rango del valor aleatorio, no su valor real. El scrand () es una función temporal 'ruido' idealmente regresar [-128, 127]
deceleratedcaviar
¡Ah, guay! Me alegra saber que está funcionando ahora.
ChrisE

Respuestas:

12

El algoritmo agrega recursivamente un valor, pero el valor puede ser positivo o negativo (normalmente + -1 / (2 ^ octava))

Si comienza en cero y solo agrega valores positivos, entonces solo puede subir, y es por eso que está viendo los vértices hacia abajo.

intente comenzar en 127 en lugar de cero para las cuatro esquinas, y también intente firmar char (luego verifique sus límites tanto arriba como abajo)

EDITAR

entonces, dos cosas más necesitan cambiar en el principal (64 >> i) para obtener el efecto medio en cada octava, y también su función de salida (la que mapea el final [] [] tp el imgdta [], usted simplemente necesita poner

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

en lugar del bloque if else.

Otra cosa, no estoy seguro de por qué, pero su verificación de límites está fallando (es decir, las líneas 38 y 65) si elimina la verificación por completo, también nota algunas manchas oscuras nuevas, así que creo que es posible que necesite promocionar a un tipo más grande antes de hacer los límites, verifique si desea obtener una imagen más ruidosa con "64 / i".

OTRA EDICIÓN

acabo de descubrir de qué se trataba, estás comparando con 'r', no 'rv', en la verificación de límites. Aquí está el código fijo: http://pastie.org/1927076

Richard Fabian
fuente
Definitivamente, esta era la mejor manera de hacerlo, pero aún no hay cigarro, parece que mi imagen todavía tiene algunas 'peculiaridades', actualicé la publicación original.
Caviar desacelerado
No estoy seguro pero la línea 93 se ve mal, 64 / i que tenga que ser 64 >> I (a medida que la mitad del efecto cada octava)
Richard Fabian
Ahhh !! Muchas gracias, no puedo creer eso, sabía que sería algo estúpido para ese segundo problema. Me encantó tu improvisado código TGA, lo siento, debería haberte ahorrado el problema y poner el encabezado.
deceleratedcaviar
3

Dos cosas que saltan a la vista:

  1. ¿Tiene una razón convincente para hacer esto en punto fijo? No tiene nada de malo en sí mismo, y hay muchas razones para usarlo (especialmente los requisitos de memoria si planea subir a un mapa ENORME), pero definitivamente comenzaría con una versión de coma flotante del algoritmo y conviértalo a punto fijo después de que lo tenga funcionando; eso debería, si nada más, eliminar una fuente plausible de errores (en particular, sospecho que su sujeción puede estar causando problemas y las condiciones para cuándo agregar / restar rv).
  2. Si bien es difícil saberlo por el código que veo, no parece que su desplazamiento de altura aleatorio esté escalando con el nivel, y eso combinado con el problema en (1) puede estar causando algunos de los problemas: no debería desplazándose por la misma cantidad en cada nivel.

Ah, y una cosa no algorítmica: recomiendo no hacer asignaciones en su función mdp (); pase dos matrices diferentes ya asignadas y realice la iteración 'en el lugar', yendo de una a la otra. Por lo menos, esto te permitirá hacer ping-pong de un lado a otro mientras haces las capas en lugar de tener que asignar una nueva matriz cada vez.

Steven Stadnicki
fuente
Algunos puntos buenos, obviamente, solo estoy tratando de obtener el algoritmo correcto, la implementación está lejos de ser ideal, ni siquiera limpio la memoria en este punto: P.
Caviar desacelerado
En este punto, la escala sobre los pases es 64 / i, obviamente cambiaré eso más tarde, pero en realidad no explica el efecto de hoyuelos que se experimenta actualmente. : S
deceleratedcaviar
0

Además de lo anterior, actualmente no está eliminando la memoria que está asignando. Para remediar esto, cambie la línea 104 de:

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

a

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

y agregue esto después de escribir en el archivo tga:

for (unsigned i = 0; i < n; ++i)
  delete[] final[i];
delete[] final;
dma
fuente
Soy muy consciente de cómo limpiar la memoria, pero dado que este era solo un prototipo de algoritmo y se volvería a escribir para usar vectores, solo quería asegurarme de que fuera correcto.
Caviar desacelerado