Como se escribió en
publicaciones de blog
recientes , luché por obtener el detalle correcto de la costa en mi juego
Dragons Abound . Mi decepción surgió durante la implementación de las
islas barrera . Para crear la isla más angosta posible, les hice una ubicación amplia: en la figura a continuación, cada ubicación es un triángulo de Delaunay:
Esto fue bastante desagradable, tanto porque la isla estaba muy rota como porque el tamaño de las partes era demasiado grande. Parecía que con un gran aumento en el número de triángulos de Delaunay (es decir, con una fuerte disminución en su tamaño), este problema se resolvería, pero la densidad de triángulos que necesitaba condujo a un bloqueo del navegador.
Resolví este problema separando los contornos de la tierra de la representación interna de las ubicaciones. Esto me permitió dibujar islas de cualquier tamaño o forma, independientemente de la cuadrícula de ubicación subyacente:
¡Entonces el problema está resuelto! Esto me permitió dibujar las islas de barrera, y dado que la línea costera ya no es necesaria para seguir la cuadrícula básica, si es necesario, se podría crear una línea costera más detallada de la manera habitual y luego agregar detalles.
Pero ... ¿cómo agregamos detalles a la costa? No es tan fácil como podrías pensar. Como quería crear una línea costera fractal, consideré usar
fractales para agregar detalles a la línea costera:
Después de experimentar con la configuración, pude agregar muchos detalles y cosas interesantes a la costa. Sin embargo, el sistema no pudo crear algo parecido a ese mapa:
El ruido de Perlin
puede crear este tipo de terreno con una cuadrícula de base suficientemente detallada, pero ¿puede hacerse
sin almacenar las alturas de elevación en la cuadrícula de base con la resolución deseada (después de todo, sé que esto romperá mi código)? Hasta que descubrí cómo hacerlo. El litoral es esencialmente un camino a través de todos los puntos en los que la función de ruido Perlin tiene un valor cero. Aunque podemos aprender directamente de la función de ruido Perlin el valor en una ubicación específica (X, Y), no podemos encontrar (por ejemplo) "todas las ubicaciones en las que la función tenga un valor cero". Es decir, es difícil ver cómo dibujar un contorno de alturas sin una cuadrícula básica.
Peor aún, le pregunté a
Amit cómo hacer esto, y él tampoco sabía la respuesta. Una cosa es cuando no puedo decir esto, pero cuando incluso una persona tan inteligente no puede dar una respuesta, empiezo a pensar que esto no se puede hacer. Es triste Puedo darle a la costa cualquier forma que necesite, pero no puedo obtener las formas que necesito sin una cuadrícula de base muy detallada.
Entonces, ¿cómo obtengo una cuadrícula de alta resolución sin romper el código?
Una de las soluciones que se me ocurrió me recuerda lo que
hizo Azgaar en su generador de mapas: las células Voronoi de tamaño variable. La idea principal es aumentar la densidad (y disminuir el tamaño) de la malla base a lo largo de las costas y mantener una densidad más baja en los océanos y otras áreas que no requieren detalles. Con esta opción, tendré muchas celdas de malla solo en aquellas áreas donde necesite detalles. Este cambio será bastante difícil de implementar en
Dragons Abound , pero quiero meditarlo. Por otro lado, Azgaar en sí
no estaba muy satisfecho con este enfoque , por lo que también es necesario tenerlo en cuenta.
Paralelamente, quería investigar las causas de un bloqueo del navegador al procesar un montón de triángulos. Las herramientas de desarrollador en Chrome me proporcionaron información detallada sobre el rendimiento. De ninguna manera soy un experto en el uso de estas herramientas, pero muchas funciones son lo suficientemente simples para que cualquiera las entienda. En caso de que desee averiguar la cantidad total de memoria utilizada en el programa, la pestaña Memoria contiene información sobre la capacidad utilizada actual:
En este caso, abrí la página web de Azgaar, y ocupa unos modestos 20 MB de memoria. Puede usar esta herramienta para averiguar cuánta memoria ocupa
Dragons Abound y para determinar cuándo se bloquea la pestaña.
El parámetro básico que controla la resolución de la malla subyacente en
Dragons Abound se llama inteligentemente "npts" (Número de puntos). Para cada unidad de área del mapa (los mapas de regiones que generalmente uso como ejemplos tienen un área de 1 unidad)
Dragons Abound crea un número determinado de ubicaciones de la cuadrícula base. Usualmente uso 16K (16384) para npts, lo que significa que cada ubicación de cuadrícula corresponde a aproximadamente 70 píxeles cuadrados de la pantalla en una escala de zoom estándar.
Por supuesto, la cantidad exacta de memoria utilizada depende de la tarjeta, pero para la tarjeta que se muestra arriba con 16K puntos necesita aproximadamente 92 MB:
Esto es menos de lo que esperaba y, para ser sincero, una cifra bastante modesta.
Si duplica el número de puntos en la cuadrícula base, la capacidad de memoria aumentará a 138 MB:
El tamaño de la memoria ocupada no se ha duplicado, porque parte de esta memoria está ocupada por recursos y otras estructuras de datos cuyo tamaño no ha cambiado. 16K puntos adicionales "pesan" unos 50 MB de memoria, es decir, cada punto ocupa aproximadamente 3 KB de memoria. Esto es más de lo que esperaba, pero en general el volumen sigue siendo bastante modesto. En una computadora con 64 GB de memoria, apenas se notan 150 MB.
Después de hacer algunos dobles más, descubrí que la pestaña con
Dragons Abound generalmente se bloquea en aproximadamente 128K puntos. Si lo detectamos antes de que salga volando y verifiquemos la memoria, veremos lo siguiente:
Supuse que la pestaña se bloquea debido a la memoria ocupada, pero generalmente el problema no está en la memoria. ¿Por qué se bloquea la pestaña? La única pista es que la pestaña no se bloquea antes de que finalice el mapa, y esto es probablemente una indicación de que se produce un bloqueo durante el renderizado.
Es lógico suponer que el SVG que creo sobrecarga el renderizador del navegador debido a su tamaño o complejidad. Para comenzar, puedo averiguar cuántos elementos SVG creo. En D3, puedo obtener el número total de elementos SVG creados usando
svg.selectAll('*').size() .
Ejecutar desde 16K puntos y verificar la cantidad de elementos SVG me mostró lo siguiente:
32K puntos tienen 65457 elementos, y 128K puntos tienen 258823. Cada punto agregado a la cuadrícula base agrega dos elementos al mapa. Creo que encontré una fuente de desgracia.
Cada punto en la cuadrícula base agrega elementos SVG debido a la forma en que
Dragons Abound representa la tierra (y el agua). El terreno se representa al representar cada ubicación base como un polígono relleno, seguido de desenfocarlos a todos. Esto permite que
Dragons Abound le dé a la tierra un patrón hermoso o use la altura de la tierra para renderizar la tierra con sombreado 3D, como se muestra aquí:
Puede desactivar la visualización de la tierra y el océano para verificar cuántos elementos SVG se crean. En 256K puntos:
Wow, la cantidad de elementos SVG ha disminuido significativamente. Como esperaba, ¡ahora el mapa se muestra sin fallar! Es decir, si evita usar una cuadrícula para representar la tierra y el agua, puede crear una cuadrícula mucho más densa que antes.
Ahora que tengo una cuadrícula de Voronoi mucho más densa, quiero verificar si me permite generar los elementos de socorro que necesito, como las islas costeras. La densa malla de Voronoi crea otros problemas (especialmente con los ríos), así que apagaré todo excepto las costas para acelerar las pruebas y enfocarme en ellas. Aquí está el render original de algunas costas a 256K píxeles y con ruido estándar:
Resulta que el mapa se renderiza bien y ya crea una costa mucho más hermosa.
Incluso sin un ajuste cuidadoso, el resultado es mucho mejor. El ruido crea los tipos de costas fractales e islas costeras que indiqué en el mapa de arriba.
Aquí están las islas con un aumento del 300%:
Con este aumento, puede observar artefactos de triángulos desde la cuadrícula base, pero aun así, las islas pueden crear formas interesantes. Puede usar el suavizado (como lo hago en la versión actual de los mapas) para deshacerse de algunos de los artefactos más notables de los triángulos. Con un aumento estándar, esto proporciona una costa menos accidentada, pero también elimina algunos pequeños detalles:
Probablemente tenga que sintonizar para obtener un término medio.
La mayoría de los generadores de sushi procesales usan el ruido Perlin para crear un mapa de altura. Necesitamos encontrar los parámetros de ruido apropiados, seleccionar una semilla y luego usar el valor de ruido en cada ubicación (x, y) para establecer la masa de tierra. Un aspecto conveniente de hacer tierra es que si necesita más detalles sobre la costa, simplemente puede ajustar los parámetros de ruido.
Sin embargo,
Dragons Abound no crea tierra de esta manera. (O al menos crea más que eso).
Dragons Abound utiliza muchos métodos diferentes para crear sushi. Aunque todos usan el ruido en un grado u otro, muy pocos crean tierra directamente del ruido. Por ejemplo, el juego tiene un procedimiento para crear una isla que crea una máscara para la isla (generalmente una elipse), usa ruido para darle a la elipse una forma más natural y luego aplica un ruido diferente para llenar la máscara de manera aproximada. Cada mapa particular generalmente se crea mediante una combinación de varios procedimientos diferentes. Por lo tanto, agregar detalles ajustando los parámetros de ruido para
Dragons Abound no
es muy adecuado.
Para mis propósitos, es mejor abordar el problema desde un ángulo ligeramente diferente. Si tengo un mapa de elevación específico que define las masas de tierra, ¿cómo agrego detalles a los bordes de estas masas de tierra? Esto puede llevarnos a la idea de que necesitamos reconocer los bordes de las masas de tierra y enmascarar el resto del mapa, etc. Pero, por otro lado, no estoy en contra de agregar detalles adicionales al resto del mapa. Si la tierra es un poco más desigual o el fondo del océano es un poco más áspero, entonces esto es normal.
¿Qué significa agregar detalles a la costa? Una línea costera es simplemente una línea de contorno en la que un mapa de altura tiene un valor cero. (El valor es arbitrario, pero este principio se usa en todos los generadores de tierra procesales). Para hacer esta línea más detallada, debe cambiar ligeramente la tierra al lado de esta línea de contorno un poco hacia arriba y hacia abajo, para que las costas simples se vuelvan más complejas, partes de la tierra sobresalgan en el océano y se vuelvan islas, y así sucesivamente. Pero esto no debería suceder por casualidad, quiero que los cambios parezcan naturales. Resumimos todo esto, y parece que necesita agregar una pequeña cantidad de ruido a todo el mapa. Y en realidad esto es exactamente lo que hice en el ejemplo original que se muestra arriba.
Por supuesto, esto debe hacerse con cuidado para no borrar las masas de tierra creadas y crear otros problemas. Esencialmente, necesito configurar tres parámetros.
El primero es la escala del ruido. Una escala es simplemente un intervalo de valores para este ruido. En nuestro caso, quiero reducir algunas áreas hacia abajo y aumentar algunas, por lo que el rango de valores debe ser de negativo a positivo. Sin embargo, no quiero agregar nuevas montañas o crear un océano lejos de la costa existente, por lo que haré que el valor máximo (absoluto) del ruido sea una pequeña fracción de la altura estándar de la tierra.
El segundo parámetro es la frecuencia principal del ruido. La frecuencia determina qué tan rápido cambia el ruido dentro de la ubicación. El ruido de baja frecuencia cambia muy lentamente, por lo que un área positiva con ruido de baja frecuencia puede (por ejemplo) cubrir todo el mapa. El ruido de alta frecuencia cambia rápidamente, por lo que una región positiva con ruido de alta frecuencia puede (por ejemplo) tener el tamaño de una isla pequeña. En nuestro caso, la frecuencia de ruido principal determina los elementos de relieve más grandes que veremos en el ruido. Es decir, si quiero que el ruido agregue (digamos) pequeñas islas (pero nada más grandes que ellas) al mapa, entonces debo seleccionar la frecuencia principal del tamaño de una pequeña isla.
Puede pensar que esto es fácil de hacer (solo mida una isla pequeña y asigne este tamaño a la frecuencia principal). Sin embargo, la frecuencia se mide en las coordenadas de la función de ruido, no en las coordenadas del mapa. Una función de ruido típica puede tener un intervalo de 0 a 255 en cada coordenada, y un mapa puede tener un intervalo de -1 a 1. En cada coordenada. Peor aún, las coordenadas de ruido están colapsadas y muchos usuarios que usan ruido ni siquiera se dan cuenta de esto. La traducción de una unidad a otra y la determinación de frecuencias adecuadas es confusa, por lo que generalmente es más fácil experimentar con intervalos de frecuencia y elegir el que crea los elementos de la tarjeta del tamaño correcto.
El tercer parámetro es el número de octavas de ruido. Las octavas son capas adicionales de ruido. Cada capa generalmente duplica la frecuencia y reduce a la mitad la escala de ruido. Es decir, cada nueva capa agrega elementos de relieve dos veces menos que la capa anterior, pero también dos veces más débil. Es decir, debe seleccionar el número de octavas que dan los elementos más pequeños que necesitamos, y para esto puede que necesite ajustar la escala de ruido, ya que todavía es lo suficientemente fuerte en la octava más alta para aparecer en el mapa. Como intencionalmente hago esto para hacer que las costas sean muy complejas, usaré bastantes octavas de ruido.
Comencemos con la configuración. Para comenzar, generaré un mapa de ejemplo sin ruido adicional:
Obviamente, esta es una costa aburrida, con líneas suaves y solo un par de islas grandes. Aquí está la misma costa con la muestra de ruido original:
El ruido cambió significativamente la forma del mapa, convirtiendo grandes fragmentos de tierra en un océano, y viceversa. También aparecieron muchas islas, incluso lejos en el mar. Todo esto indica que la escala de ruido es demasiado grande. Los elementos de relieve individuales más grandes añadidos por el ruido deben ser del tamaño de las pequeñas islas del mapa original. Este es probablemente el nuevo tamaño máximo de los elementos, lo que demuestra que la frecuencia principal del ruido se elige aproximadamente correctamente. Finalmente, aparecieron muchos pequeños detalles, hasta los límites del tamaño de la pantalla, y esto muestra que hay suficientes octavas. (Sin embargo, el número de octavas puede ser más de lo necesario. Esto no afecta la apariencia de la tarjeta, pero es ineficiente). Parece que básicamente necesita ajustar la escala de ruido.
Ajustar el ruido es una operación bastante complicada porque quiero que este ruido afecte principalmente a la tierra y al agua en una línea de contorno con una altura = 0. Es decir, necesito una escala relativamente pequeña, pero no está claro cómo elegir el número correcto, porque En diferentes mapas, la distribución de las alturas varía. La solución es encontrar la escala correcta sobre la marcha. Puede tomar todos los valores absolutos de las alturas en el mapa, ordenarlos y encontrar el punto de corte que selecciona (digamos) el 10% de las ubicaciones alrededor de cero. Todos estos lugares caen en el intervalo (por ejemplo) [-0.05, 0.05], y luego puedo usar el valor 0.05 para determinar la escala del ruido agregado.
(Escribo "definiciones" porque por varias razones no puedes usar 0.05. Primero debes convertir la tierra en agua y viceversa. Agregar (digamos) 0.002 a -0.05 no hará ningún cambio visible en el mapa. Es decir, el intervalo debería ser mucho más que 0.05 si quiero convertir una proporción significativa de ubicaciones con una altura de -0.05 del agua a la tierra. En segundo lugar, las funciones de ruido no están
distribuidas uniformemente , por lo que con una escala de 0.05 la función de ruido nunca devolverá 0.05. En la práctica, la dificultad es que la escala debería ser mucho mayor que los valores más grandes que queremos ver con suficiente frecuencia).
Después de experimentar, encontré un valor que agrega complejidad a las costas, sin cambiarlas significativamente, y también crea un pequeño número de islas:
Como siempre, estos parámetros en el juego pueden tomar un intervalo de valores, por lo que puedo obtener una amplia gama de tarjetas: desde tarjetas con costas bastante suaves hasta tarjetas con bancos rotos y complejos. Dejando que el programa seleccione los valores, obtuve el siguiente resultado:
Las costas están en el lado más liso, pero aún existe la mayor parte de la complejidad añadida de la escala media y un número suficiente de nuevas islas.
Al implementar costas fractales, me di cuenta de la capacidad de controlar el nivel de fractalización utilizando la función de ruido, por lo que algunas áreas tendrán costas suaves, mientras que otras tendrán costas complejas. Pensé que esto aumentaría en gran medida el interés del mapa, y se vería menos "generado", por lo que agregaré esta característica aquí. La idea es bastante simple: antes de agregar ruido costero al mapa, lo multiplico por la salida de la segunda función de ruido, que varía de cero a 1. Cuando esta función es pequeña, se agregarán pequeños detalles a las costas. Cuando esté cerca de 1, se agregarán detalles adicionales en su totalidad. Al seleccionar la escala de la segunda función de ruido, que varía lentamente a lo largo del mapa, obtendré algunas áreas con costas complejas, algunas con costas simples y transiciones lógicas entre ellas:
Aquí hice grandes los parámetros costeros, para que la diferencia sea más visible. Vemos costas salvajes y escarpadas en el noreste, y playas más suaves en el oeste.
Por lo tanto, hemos mejorado significativamente la generación de costas, pero aún no puedo generar completamente un mapa con tantos triángulos Delaunay. Solo muestro mapas de esquema porque muchos otros elementos del mapa están rotos. Necesita ser reparado.
El resto del programa no funciona bien con tantos triángulos de Delaunay (con configuraciones actuales de 256K). El principal problema es que
Dragons Abound dibuja tierra y agua dibujando todos los triángulos individuales, y tantos elementos SVG hacen que el navegador se bloquee. Así que tuve que deshabilitar completamente el renderizado de sushi. Probablemente hay una forma de evitar este problema, pero tener tantos triángulos crea otros problemas. Por ejemplo, algunas partes del programa deben procesar todo el mapa. Cada uno de ellos se vuelve dieciséis veces más lento en ubicaciones de 256K que en ubicaciones de 16K. También en el código hay partes (por ejemplo, un nuevo modelo de precipitación) que se rompen cuando se trabaja con tantos triángulos. Y a partir de la creación de una cuadrícula de ubicaciones tan detallada, no ganamos nada: después de generar el litoral, nada mejora de la complejidad añadida. Por lo tanto, aunque podría revisar el programa y corregir aquellas áreas donde una gran cantidad de ubicaciones se ralentiza o rompe demasiado el código, parece más fácil reducir la resolución de la cuadrícula del mapa después de crear costas.
Como se indicó anteriormente, Azgaar ya ha realizado
trabajos para cambiar la resolución de la cuadrícula Voronoi subyacente en el mapa. Se dio cuenta de la posibilidad de cambiar la resolución de la cuadrícula sobre la marcha en el proceso de generación, es decir, podría (por ejemplo) aumentar la densidad de ubicaciones a lo largo de la costa. Sin embargo, un cambio local en la densidad tiene sus inconvenientes, en particular, crea extraños triángulos a lo largo de la frontera. Más tarde, Azgaar
sugirió que el sistema es demasiado complejo y no vale la pena el esfuerzo. Azgaar generalmente sabe de lo que está hablando, por lo que aceptaré su palabra y no intentaré volver a embalar la malla terminada.
En cambio, creé una segunda cuadrícula con la resolución deseada (más baja) y luego copié el mapa de elevación a esta nueva cuadrícula. (No olvide que
Dragons Abound ahora almacena las costas por separado de la cuadrícula, por lo que después de que se crean, ya no dependen del ajuste exacto de la cuadrícula. Hacer esto es un poco complicado. Dado que la cuadrícula original tiene una resolución mucho más alta que la nueva, muchas ubicaciones en el original la cuadrícula se superpondrá en una ubicación en la nueva cuadrícula. Cada una de estas ubicaciones de origen tiene una altura diferente en el mapa de altura, ¿cómo puedo copiarlas? ¿Usar el promedio o la altura máxima (mínima)?
Para comenzar, solo selecciono una ubicación aleatoria para ver si la nueva cuadrícula funciona con el resto del programa:
Todo resultó sorprendentemente bien. Se produce un error menor cuando las nuevas ubicaciones no están marcadas correctamente como tierra, costa o agua, pero después de resolver este problema, la generación del mapa funcionó bien. Debe limpiar defectos menores (por ejemplo, la etiqueta Palmanor que salió al agua), pero en general se ve bien. Incluso las pequeñas islas resultaron hermosas.
Al final, decidí que con una disminución en la resolución de la cuadrícula Voronoi, cada ubicación sería el promedio de las ubicaciones base. Esto parece una decisión acertada, y si es necesario, siempre se puede cambiar. Esta imagen muestra cómo, como resultado, las costas se separaron de la malla terminada:
Para resumir: en
Dragons Abound , se utiliza una cuadrícula de triángulos Delone de muy alta resolución al generar el mapa de altura. Después de su finalización,
Dragons Abound define las costas mediante el seguimiento de las transiciones de valores negativos a positivos en el mapa de altura. Luego, el juego copia la cuadrícula de alta resolución en una cuadrícula de resolución mucho más baja, promediando las ubicaciones que se encuentran en una ubicación de la nueva cuadrícula. A continuación, la cuadrícula de alta resolución se descarta y el resto de la generación y visualización de procedimientos continúa en la cuadrícula de baja resolución. Una pregunta interesante es si el uso de la malla Delaunay tiene algún valor en esta etapa; podría valer la pena copiarlo en una cuadrícula de hexágonos o algo similar.