Generación de mapas

Con ciertas técnicas se pueden generar mapas tan maravillosos como este. (Amit Patel)

La generación de mapas de forma automática es una tarea realmente fascinante, donde se pueden desarrollar y aplicar muy diversas técnicas matemáticas y de computación (análisis de grafos, reconocimiento de patrones, fractales, etc.) Es uno de esos casos en los que muy diversas materias se reúnen en la resolución de un problema tan concreto y aparentemente lúdico.

Lo primero que se nos viene a la cabeza preguntar es: ¿quién necesita mapas imaginarios? Son clásicos los mapas de ficción que aparecen (generalmente como hoja desplegable) en los libros de género fantástico, con los cuales el autor nos presenta el imaginario mundo en el que se desarrolla la historia. Lo normal ha sido encargar a un dibujante que plasme las calenturientas ideas del autor en un mapa más o menos detallado. De lo primero que se dan cuenta quienes intentan semejante cosa es lo difícil que resulta crear desde cero un mapa mínimamente creíble.

La Tierra Media de J.R.R. Tolkien es un ejemplo "de libro" de un mapa inverosímil.

Los juegos de rol y de estrategia son otros clientes habituales de los mapas imaginarios. Pero ha sido la llegada de los juegos por ordenador la que ha disparado la necesidad de generar infinitos mapas automáticamente, usando la potencia computacional y todo un arsenal de técnicas relacionadas con la Inteligencia Artificial.

Juegos como Sid Meier's Civilization usan intensivamente los mapas generados automáticamente.

Aparte de todos estos usos, como tantos problemas interesantes, se puede abordar la generación de mapas por el simple placer intelectual y, por qué no negarlo, convertirla en una afición bastante friki. Esto es lo que hace el maravilloso bot de Twitter (@unchartedatlas), creado por Martin O'Leary, que me ha inspirado esta serie de artículos.

The Outer Plains of West nou-Soal pic.twitter.com/O58vKeBBY5

— Uncharted Atlas (@unchartedatlas) 28 de agosto de 2017

Este fascinante programa genera cada hora automáticamente un nuevo mapa aleatorio completo con sus ríos, mares, montañas, ciudades e incluso topónimos. Yo de mayor querría hacer algo lo mitad de bueno que esto.

Fractal o no fractal, esa es la cuestión

António Miguel de Campos - Wikipedia

Si la propia naturaleza en muchas ocasiones utiliza fractales, ¿por qué no aprovecharlos para nuestros mapas imaginarios? Los fractales son, en términos muy simples, objetos matemáticos cuya estructura se repite a diferentes escalas.

Para la creación de un paisaje fractal, generalmente se usan polígonos que se van subdividiendo en otros similares, desplazando aleatoriamente el punto central que comparten. Esto se muestra muy bien en la imagen animada anterior, en la que se usan triángulos como base para la generación del terreno.

A pesar de que los fractales imitan bastante bien las formas naturales, hay autores que sostienen que no representan correctamente ciertos procesos clave, como la erosión. Otro incoveniente es que distintas formas del terreno tienen distintas propiedades fractales, por lo que el uso de una función fractal general para todo el mapa no siempre es posible.

Atacando el problema sin fractales

Existen muchas formas de afrontar este problema sin usar fractales. Es un área bastante autodidacta, donde cada autor va modelando a su manera personal, aunque, como ocurre a menudo, las soluciones van convergiendo a una serie de técnicas. Cada una de estas técnicas intenta imitar un proceso, formación o erosión natural, y se van aplicando paso a paso, de manera acumulativa, hasta que finalmente obtenemos el mapa terminado. Es, por tanto, un proceso mucho más "dirigido" por la mano del creador que el proceso fractal que, al menos aparentemente, sería una solución puramente matemática.

Rejilla base

Rejilla hexagonal

Lo más sencillo es crear una rejilla ortogonal (de "cuadraditos") o hexagonal (como un panal de abejas). Si queremos más realismo, tendremos que irnos a una rejilla más compleja de polígonos irregulares (el bot de O'Leary lo hace precisamente de esta manera).

Un caso especial son los mapas para juegos de estrategia, en los que la dinámica del juego suele restringir el tipo de rejilla que se puede usar. También es posible en estos casos, primero generar el mapa con una rejilla irregular y luego adaptarle otra rejilla para los movimientos del juego.

Una forma común de realizar la distribución de la rejilla es mediante diagramas de Voronói. En este caso, las "semillas" serían unos puntos distribuidos más o menos aleatoriamente, y la forma de cada celda se adaptaría hasta ocupar el área más cercana a cada punto.

Caracterización de las celdas

Diagrama de Voronói correspondiente al mapa que se ve al principio de este artículo, con las celdas caracterizadas como tierra, mar y lagos. (Amit Patel)

El siguiente paso va a ser la asignación de distinta naturaleza ("tierra", "mar", etc.) a las celdas de la rejilla. Esto crea la distribución general del mapa.

Una distribución completamente aleatoria daría lugar a mapas muy extraños, por lo que se suelen usar ciertas estrategias, las cuales van a tender a darnos con más probabilidad un tipo de mapa frente a otros (por ejemplo, islas en lugar de continentes). También se puede partir de una forma base creada por un diseñador, si se trata de un encargo para un juego, por ejemplo.

Mapa de elevación

Mapa de elevación (Erik Nordeus)

Un paso clave para hacer un mapa es asignar a cada celda su elevación o altura de terreno. Esto, a la larga, va a definir todos los accidentes geográficos del mapa (cordilleras, ríos, etc.) e indirectamente también la ubicación de las ciudades y otros elementos extra.

Las celdas de mar tendrán elevación cero y, a partir de ahí habrá que ir asignando las alturas siguiendo una cierta estrategia. Aquí tampoco sería realista dejarlo todo al azar. Esta nueva caracterización del terreno es muy similar en concepto a la que hemos visto en el anterior punto, pero distinta en cuanto al algoritmo y parámetros a utilizar. Estos parámetros van a depender de en qué medida queremos generar terrenos preferentemente montañosos o llanos.

Distribución del agua

Los grafos dirigidos nos permiten representar el flujo del agua.

La consecuencia directa del mapa de elevación es la pendiente que van a seguir los flujos de agua. Será necesario crear un grafo dirigido (conjunto de nodos con aristas que tienen una dirección asignada) sobre el mapa de elevación, que irá indicando el camino siempre desde las celdas más altas a las más bajas. Luego aplicaremos algún tipo de algoritmo que simule la "inundación del terreno" y vaya marcando las celdas por las que discurriría el agua.

Los ríos y lagos aparecerán en las zonas donde la humedad supera un cierto umbral. Una vez establecidas estas zonas húmedas, será fácil asignar a cada celda un nivel de humedad decreciente según lo lejos que esté del agua. La caracterización de humedad va a ser clave para el siguiente punto.

Biomas

En Biología, es común agrupar los biomas según temperatura y precipitaciones.

Vamos a tomar prestado de la Biología el concepto de bioma, de una manera bastante laxa, en este caso para representar en diferentes colores o texturas distintas formas de vegetación (pradera, bosque, tundra, etc.)

Usando las elevaciones y los grados de humedad que hemos calculado, no es difícil hacer una correlación entre cada pareja (altura, humedad) y un color en el mapa. También es posible incluir representaciones más artísticas de cada bioma, aunque esto es más propio de la generación de paisajes que de simples mapas.

Añadiendo ruido

Celda con ruido (Amit Patel)

Después de todo lo explicado anteriormente, nuestro mapa parecerá más bien un conjunto de polígonos con colores que un verdadero terreno. Hay que darle alguna forma de irregularidad que lo haga más natural a la vista. Esto es lo que llamamos "ruido", y se hace mediante distintos algoritmos que incluyen alguna forma de aleatoriedad.

En el ejemplo de la imagen, se ha subdividido una diagonal y se han ido moviendo de su lugar los puntos de división de manera aleatoria. También es posible añadir ruido sin cambiar la forma, haciendo que los colores de celdas adyacentes se mezclen en los bordes.

Para saber más

Muchísima información interesante se puede obtener siguiendo a @redblobgames en Twitter. Tiene una demo online donde se pueden experimentar en tiempo real muchos de los conceptos que he introducido en este artículo.

El creador del Uncharted Atlas tiene un tutorial con mucha información sobre cómo está hecho ese bot.

En la Voronoi Wiki hay enlaces a multitud de artículos sobre el uso de este tipo de diagramas.

También es muy recomendable este fascinante generador online de mundos fractales.