First entry and frequent questions / Primera entrada y preguntas frecuentes

English:

Click here to read all entries in chronological order.

Welcome to the Tectonic Tiles development blog! You probably have several questions, and I’ll do my best to answer them!

What is Tectonic Tiles? Tectonic Tiles is an algorithm for random terrain generation inspired in natural processes. It’s also the name of a small application/library I’m making to show it working and show its potential.

How does it work? The gist of it is that it tessellates a terrain into tectonic plates and for each tectonic plate it randomly selects two tiles. These two tiles represent the movement vector of the tectonic plate, which is used to create a crease in the direction of the movement. Repeat for all tectonic plates and you get a nice terrain. Here’s a more detailed explanation.

Why would that concern me? Tectonic Tiles is more customizable and realistic than simple noise based terrain generators but it’s much simpler to implement and efficient than the more realistic terrain simulators, making it an option to consider when random terrain generation is needed in videogames such as 4X and city building games. Here’s a list of ways in which the algorithm can be expanded and customized for your needs.

How do I use it? In the GitHub repository there are instructions to use the Java application/library. If you want to implement the algorithm by yourself (which if you plan to use it for your videogame projects you honestly should so you can tailor the algorithm to your specific needs), here’s the entry explaining how the algorithm works and here’s the entry showing some ways in which it can be extended and customized.

And if you still have any doubts, well, my email address is jacenve@telefonica.net and I’ll try to answer you as soon as possible!

Español:

Pincha aquí para leer todas las entradas en orden cronológico.

¡Bienvenidos al blog de desarrollo de Casillas Tectónicas! Probablemente tenéis varias preguntas y trataré de responderlas.

¿Qué es Casillas Tectónicas? Casillas Tectónicas es un algoritmo para la generación de terreno aleatoria inspirando por procesos naturales. También es el nombre de una pequeña aplicación/librería en la que estoy trabajando para mostrar su potencial.

¿Cómo funciona? La idea básica es teselar un terreno en placas tectónicas y por cada placa tectónica seleccionar dos casillas. Estas dos casillas representan el vector de movimiento de la placa tectónica que es usado para crear un pliegue en la dirección del movimiento. Repite para todas las placas tectónicas y acabas con un buen terreno. Aquí hay una explicación más detallada.

¿Por qué debería interesarme? Casillas Tectónicas es más personalizable y realista que simples generadores basados en ruido pero es mucho más simple de implementar y efficiente que los simuladores de terreno más realistas, haciendo de él una opción que considerar cuando es necesario generar terreno en videojuegos como videojuegos de construcción de imperios y de ciudades. Aquí hay una lista de maneras en las que el algoritmo puede ser extendido y adaptado a tus necesidades.

¿Cómo puedo usarlo? En el repositorio de GitHub hay instrucciones para usar la aplicación/librería Java. Si quieres implementar el algoritmo tú misma/o (que deberías hacerlo si planeas usarlo para videojuegos para poder adaptar el algoritmo a tus necesidades específicas), aquí está la entrada que explica cómo funciona el algoritmo y aquí está la entrada que muestra algunas maneras en las que el algoritmo puede ser extendido y adaptado a tus necesidades.

Y si aún tienes dudas, bueno, mi dirección de correo electrónico es jacenve@telefonica.net y trataré de responderte lo antes posible.

Advertisement

How the algorithm works / Cómo funciona el algoritmo

English:

In this entry I’ll explain how the algorithm works. This explanation only covers the most basic form of the algorithm which is a good starting point but doesn’t exploit its full potential. If you’re interested in the possibility of using this algorithm, here’s a small Python implementation you can check out and here’s a list of ways the algorithm can be expanded and customized to suit your needs.

A terrain as generated by the algorithm consists of tiles. Each tile indicates the value of the parameters of the terrain at its coordinates. The most basic form of the algorithm has only one parameter: land, which indicates the height of the land.

The tiles are grouped into tectonic plates. In this example, we see a terrain consisting of 25×15 square tiles, grouped into 5×5 square tectonic plates.

For each tectonic plate, we pick two tiles (typically part of the tectonic plate, but they can be picked with any criteria). These tiles represent the start point and end point of the movement of the tectonic plate. Here we see the example terrain with start and end points chosen as the center of the tectonic plate and a random tile of the tectonic plate respectively. The movement is represented as an arrow going from the start point to the end point.

This movement is used to generate the terrain. For that purpose, we define a function called a crease function which takes the coordinates of the start point, the end point and a point in the terrain and returns the height at the given point of the crease caused by the movement going from the start point to the end point.

Typically, the crease defined by the crease function is centered on the end point and it’s bigger the bigger the distance between the start point and the end point is.

Here we see the results of a crease function for the coordinates of each tile and the shown start and end points expressed as a shade of gray, with darker colors representing higher values.

Finally, for each tectonic plate we add to each tile of the terrain the result of the crease function for the coordinates of the tile and the start tile and end tile of the tectonic plate.

Here we see the example terrain with the added up creases.

Español:

En esta entrada explicaré cómo funciona el algoritmo. Esta explicación solo cubre la forma más básica del algoritmo que es un buen punto de inicio pero no aprovecha todo su potencial. Si estás interesada/o en la posibilidad de usar este algoritmo, aquí hay una pequeña implementación en Python en la que te puedes fijar y aquí hay una lista de maneras en las que el algoritmo puede ser extendido y adaptado a tus necesidades.

Un terreno tal y como es generado por el algoritmo consiste en casillas. Cada casilla indica el valor de los parámetros del terreno en sus coordenadas. La forma más básica del algoritmo tiene solo un parámetro: tierra, que indica la altura de la tierra.

Las casillas están agrupadas en placas tectónicas. En este ejemplo, vemos un terreno que consiste en 25×15 casillas cuadradas agrupadas en placas tectónicas cuadradas de 5×5 casillas.

Por cada placa tectónica, escogemos dos casillas (típicamente parte de la placa tectónica, pero pueden ser escogidas con cualquier criterio). Estas casillas representan los puntos de inicio y fin del movimiento de la placa tectónica. Aquí vemos el terreno de ejemplo con puntos de inicio y fin escogidos como el centro de la placa tectónica y una casilla aleatoria de la placa tectónica, respectivamente. El movimiento está representado como una flecha yendo del punto de inicio al punto de fin.

Este movimiento se usa para generar el terreno. Para ese propósito, definimos una función llamada función de pliegue que toma las coordenadas del punto de inicio, el punto de fin y un punto en el terreno y devuelve la altura en el punto dado del pliegue causado por el movimiento que va desde el punto de inicio al punto de fin.

Típicamente, el pliegue definido por la función de pliegue está centrado en el punto de fin y es mayor cuanto mayor sea la distancia entre el punto de inicio y el punto de fin.

Aquí vemos los resultados de una función de pliegue para las coordenadas de cada casilla y los puntos de inicio y fin mostrados expresados como un tono de gris, con colores más oscuros representando valores mayores.

Finalmente, por cada placa tectónica añadimos a cada casilla del terreno el resultado de la función de pliegue para las coordenadas de la casilla y las casillas de inicio y fin de la placa tectónica.

Aquí vemos el terreno de ejemplo con los pliegues añadidos.

A tiny implementation / Una pequeña implementación

English:

Here I offer an implementation of the most basic form of algorithm to show a simple, easy to follow working implementation and give anyone trying to make their own implementations a starting point.

This implementation is made in Python using Pyplot to display the generated terrain. This is unrelated to the more complete implementation in the GitHub. At the bottom of this entry I show the code.

Here’s an output of the code:

Español:

Aquí ofrezco una implementación de la forma más básica del algoritmo para enseñar una implementación funcional simple y fácil de seguir y dar a cualquiera tratando de hacer sus propias implementaciones un punto de partida.

Esta implementación está hecha en Python usando Pyplot para mostrar el terreno generado. Esto no está relacionado con la implementación más completa en el GitHub. Al final de esta entrada muestro el código.

Aquí hay una salida del código:

Annex: tectonic_tiles_basic.py / Anexo: tectonic_tiles_basic.py

import random

# Size of a tectonic plate along the x axis in number of tiles
plate_size_x = 10
# Size of a tectonic plate along the y axis in number of tiles
plate_size_y = 10
# Size of a terrain along the x axis in number of tectonic plates
number_of_plates_x = 20
# Size of a terrain along the y axis in number of tectonic plates
number_of_plates_y = 10
# Factor by which the radius of the mountains is multiplied
mountain_radius_factor = 1.5

# Total size of the terrain along the x axis in number of tiles
terrain_size_x = plate_size_x * number_of_plates_x
# Total size of the terrain along the y axis in number of tiles
terrain_size_y = plate_size_y * number_of_plates_y
# Total number of plates in the terrain
number_of_plates = number_of_plates_x * number_of_plates_y

# Calculate the euclidean distance between point a and point b
# Given the coordinates of the points along the x and y axes
def euclidean_distance(a_x, a_y, b_x, b_y):
  return ((b_x - a_x) ** 2 + (b_y - a_y) ** 2) ** 0.5

# SmoothStep interpolation function
# Defined as 0 if x <= 0, 1 if x >= 1, 3x^2 - 2x^3 otherwise
def smoothstep(x):
  if x <= 0:
    return 0
  elif x >= 1:
    return 1
  else:
    return 3 * x ** 2 - 2 * x ** 3

# Crease function
def crease(point_x, point_y, start_x, start_y, end_x, end_y):
  if start_x == end_x and start_y == end_y:
    return 0
  mountain_radius = mountain_radius_factor * euclidean_distance(start_x, start_y, end_x, end_y)
  mountain_height = mountain_radius
  x = 1 - (euclidean_distance(point_x, point_y, end_x, end_y) / mountain_radius)
  return mountain_height * smoothstep(x)

terrain = [[0 for x in range(terrain_size_x)] for y in range(terrain_size_y)]

# For each tectonic plate
for plate_x in range(number_of_plates_x):
  for plate_y in range(number_of_plates_y):
    # Select the start and end tiles as the coordinates of random tiles inside the plate
    # x coordinate of start tile
    start_tile_x = random.randint(plate_size_x * plate_x, plate_size_x * (plate_x + 1))
    # y coordinate of start tile
    start_tile_y = random.randint(plate_size_y * plate_y, plate_size_y * (plate_y + 1))
    # x coordinate of end tile
    end_tile_x = random.randint(plate_size_x * plate_x, plate_size_x * (plate_x + 1))
    # y coordinate of end tile
    end_tile_y = random.randint(plate_size_y * plate_y, plate_size_y * (plate_y + 1))
    print("Generating plate {} out of {}".format(\
      plate_x * number_of_plates_y + plate_y + 1, number_of_plates)\
      )
    # Add the results of the crease function for all tiles in the terrain
    for tile_x in range(terrain_size_x):
      for tile_y in range(terrain_size_y):
        terrain[tile_y][tile_x] +=\
          crease(tile_x, tile_y, start_tile_x, start_tile_y, end_tile_x, end_tile_y)

# Plot the terrain
import matplotlib.pyplot as plt
plt.imshow(terrain)
plt.show()

Exploring the potential / Explorando el potencial

English:

While the basic algorithm is neat, it is just a slight improvement over simple noise generators and does a poor job of showing the potential of the algorithm.

One of the major features of the algorithm is how it can be extended to produce better results and adapted to specific needs. Here’s a list of entries going into how to expand the algorithm:

• Layers
• Tectonic plates

Español:

Mientras que el algoritmo básico es interesante, solo es una ligera mejora sobre los simples generadores de ruido y no hace un buen trabajo de mostrar el potencial del algoritmo.

Una de las características más importantes del algoritmo es cómo puede ser extendido para producir mejores resultados y ser adaptado a necesidades específicas. Aquí hay una lista de entradas desarrollando cómo expandir el algoritmo:

• Capas
• Placas tectónicas

Exploring the potential: Layers / Explorando el potencial: Capas

English:

Read other “exploring the potential” entries here.

The simplest way to extend the algorithm consists in the addition of layers. Each parameter that the tiles have is considered a layer.

By default terrains have only one layer, land, whose value is set through applying the crease function. Adding more layers adds to the complexity of the terrain and allows it to support more complex features. Here are some layers that can be added:

• Water: A water layer can represent the height of the water in the tiles. This can be used to represent lakes, seas and oceans (where the water level is higher than the land), wetter or drier land (where the water level is lower than the land; the lower it is relative to the land the drier the land is considered to be) or even rivers, waterfalls and water currents (if the water level is higher than the land and varies relative to neighboring tiles). A way of generating the water level is setting it to a certain level (the sea level) if the land level is below it.
• Magma: A magma layer can represent the height of the magma in the tiles. When it exceeds the height of the land it can form volcanoes. A way of generating magma is to use the same method as to generate land, but swapping the start and end tiles when passing the coordinates to the crease function, mimicking the formation of ridges in divergent plate boundaries just like the crease function in land mimicks the formation of mountain ranges in convergent plate boundaries.
• Temperature: The temperature can be derived from the y coordinate (latitude) and the height of the land.
• Granularity: A terrain granularity layer can represent how weathered the land is. This parameter can be derived from aspects such as slope, curvature, water and temperature, and it can be used to calculate how fertile a terrain is.

Español:

Lee otras entradas de “explorando el potencial” aquí.

La manera más simple de extender el algoritmo consiste en añadir capas. Cada parámetro que tienen las casillas se considera como una capa.

Por defecto, los terrenos solo tienen una capa, tierra, cuyo valor es establecido mediante la aplicación de la función de pliegue. Añadir más capas al terreno aumenta su complejidad y le permite soportar características más complejas. Aquí hay algunas capas que se pueden añadir:

• Agua: Una capa de agua puede representar la altura del agua en las casillas. Esto puede usarse para representar lagos, mares y océanos (donde el nivel del agua es más alto que la tierra), tierra húmeda o seca (donde el nivel del agua es más bajo que la tierra; cuanto más bajo sea relativamente a la tierra lo más seca que se considera la tierra) o incluso ríos, cataratas y corrientes de agua (si el nivel el agua es más alto que la tierra y varía respecto a casillas vecinas). Una manera de generar el nivel de agua es establecerlo a un punto determinado (el nivel del mar) si el nivel de la tierra está por debajo del mismo.
• Magma: Una capa de magma puede representar la altura del magma en las casillas. Cuando excede la altura de la tierra puede formar volcanes. Una manera de generar magma es usar el mismo método que para generar tierra pero intercambiando las casillas de inicio y fin al pasar las coordenadas a la función de pliegue, imitando la formación de dorsales en bordes divergentes igual que la función de pliegue en tierra imita la formación de cordilleras en bordes convergentes.
• Temperatura: La temperatura puede ser derivada por la coordenada y (latitud) y la altura de la tierra.
• Granularidad: Una capa de granularidad de terreno puede expresar cuan meteorizada está la tierra. Este parámetro puede ser derivado de aspectos como la pendiente, la curvatura, el agua y la temperatura y puede ser usado para calcular la fertilidad del terreno.

Exploring the potential: Tectonic plates / Explorando el potencial: Placas tectónicas

English:

Read other “exploring the potential” entries here.

Another aspect of the algorithm that can be changed is how a terrain is divided into tectonic plates. The default way of doing this is to tessellate the terrain into regular tectonic plates with the same shape and size, but it’s worth considering the possibility of irregular plates.

A simple way of dividing the terrain irregularly is using a Voronoi tessellation. The tectonic plates created with such a method would always be convex and with straight sides.

Looking for other ways of dividing a plane, I came across this Stack Overflow question where the user Brenda Holloway describes an interesting alternative.

I did something similar for a game a few months back, though it was a rectangular grid rather than a hex grid. Still, the theory is the same, and it came up with nice contiguous areas of roughly equal size — some were larger, some were smaller, but none were too small or too large. YMMV.

1. Make an array of pointers to all the spaces in your grid. Shuffle the array.

2. Assign the first N of them IDs — 1, 2, 3, etc.

3. Until the array points to no spaces that do not have IDs,

4. Iterate through the array looking for spaces that do not have IDs

5. If the space has neighbors in the grid that DO have IDs, assign the space the ID from a weighted random selection of the IDs of its neighbors.

6. If it doesn’t have neighbors with IDs, skip to the next.

7. Once there are no non-empty spaces, you have your map with sufficiently blobby areas.

I decided to put this algorithm to test by making a Python implementation and using PIL to display the results (I’ll show the code at the bottom of this entry).

For a terrain of 800×400 tiles, these were the results of using Brenda’s algorithm with two plates:

With 6 plates:

With 10 plates:

With 25 plates:

With 100 plates:

And with 1000 plates:

The divisions created by this algorithm seem really similar to real tectonic plates. I added a terrain type to the Java application that uses this algorithm to create plate divisions (irregular square).

Using irregular plates has the potential to create a more natural feeling terrain.

Español:

Lee otras entradas de “explorando el potencial” aquí.

Otro aspecto del algoritmo que se puede cambiar es cómo se divide un terreno en placas tectónicas. La manera por defecto de hacerlo es teselar el terreno en placas tectónicas regulares con la misma forma y tamaño, pero vale la pena considerar la posibilidad de placas irregulares.

Una manera simple de dividir el terreno irregularmente es usar una teselación de Voronoi. Las placas tectónicas creadas con este método serían siempre convexas y con lados rectos.

Buscando otras maneras de dividir un plano, encontré esta pregunta de Stack Overflow donde la usuaria Brenda Holloway describe una alternativa interesante.

I did something similar for a game a few months back, though it was a rectangular grid rather than a hex grid. Still, the theory is the same, and it came up with nice contiguous areas of roughly equal size — some were larger, some were smaller, but none were too small or too large. YMMV.

1. Make an array of pointers to all the spaces in your grid. Shuffle the array.

2. Assign the first N of them IDs — 1, 2, 3, etc.

3. Until the array points to no spaces that do not have IDs,

4. Iterate through the array looking for spaces that do not have IDs

5. If the space has neighbors in the grid that DO have IDs, assign the space the ID from a weighted random selection of the IDs of its neighbors.

6. If it doesn’t have neighbors with IDs, skip to the next.

7. Once there are no non-empty spaces, you have your map with sufficiently blobby areas.

Decidí probar este algoritmo haciendo una implementación en Python y usando PIL para mostrar los resultados (mostraré el código al final de esta entrada).

Para un terreno de 800×400 casillas cuadradas, estos fueron los resultados de usar el algoritmo de Brenda con 2 placas:

Con 6 placas:

Con 10 placas:

Con 25 placas:

Con 100 placas:

Con 1000 placas:

Las divisiones creadas por este algoritmo parecen muy similares a placas tectónicas reales. Añadí un tipo de terreno a la aplicación Java que usa este algoritmo para crear divisiones entre placas (cuadrado irregular).

Usar placas irregulares tiene el potencial para crear un terreno de aspecto más natural.

Annex: brenda.py / Anexo: brenda.py

import random

# Size of a terrain along the x axis in number of tiles
terrain_size_x = 800
# Size of a terrain along the y axis in number of tiles
terrain_size_y = 400
# Total number of plates in the terrain
number_of_plates = 25

terrain = [[0 for x in range(terrain_size_x)] for y in range(terrain_size_y)]
tiles = []
colors = []
# Assign colors to each plate
for i in range(number_of_plates):
	color_number = int(i * 255 * 6 / number_of_plates)
	red = 0
	green = 0
	blue = 0
	if color_number < 255:
		red = 255
		green = color_number
		blue = 0
	elif color_number < 255 * 2:
		color_number = color_number - 255
		red = 255 - color_number
		green = 255
		blue = 0
	elif color_number < 255 * 3:
		color_number = color_number - 255 * 2
		red = 0
		green = 255
		blue = color_number
	elif color_number < 255 * 4:
		color_number = color_number - 255 * 3
		red = 0
		green = 255 - color_number
		blue = 255
	elif color_number < 255 * 5:
		color_number = color_number - 255 * 4
		red = color_number
		green = 0
		blue = 255
	elif color_number < 255 * 6:
		color_number = color_number - 255 * 5
		red = 255
		green = 0
		blue = 255 - color_number
	colors.append((red, green, blue))

# For each tile
for tile_x in range(terrain_size_x):
	for tile_y in range(terrain_size_y):
		tiles.append((tile_y, tile_x))

random.shuffle(tiles)

for i in range(number_of_plates):
	terrain[tiles[i][0]][tiles[i][1]] = i + 1
	tiles.remove(tiles[i])

def get_color(y, x):
	if y < 0 or terrain_size_y <= y:
		return 0
	if x < 0 or terrain_size_x <= x:
		return 0
	return terrain[y][x]

while len(tiles) > 0:
	for tile in tiles:
		if get_color(tile[0] - 1, tile[1]) > 0:
			terrain[tile[0]][tile[1]] = get_color(tile[0] - 1, tile[1])
			tiles.remove(tile)
			print("Remaining tiles: {}".format(len(tiles)))
		elif get_color(tile[0], tile[1] - 1) > 0:
			terrain[tile[0]][tile[1]] = get_color(tile[0], tile[1] - 1)
			tiles.remove(tile)
			print("Remaining tiles: {}".format(len(tiles)))
		elif get_color(tile[0] + 1, tile[1]) > 0:
			terrain[tile[0]][tile[1]] = get_color(tile[0] + 1, tile[1])
			tiles.remove(tile)
			print("Remaining tiles: {}".format(len(tiles)))
		elif get_color(tile[0], tile[1] + 1) > 0:
			terrain[tile[0]][tile[1]] = get_color(tile[0], tile[1] + 1)
			tiles.remove(tile)
			print("Remaining tiles: {}".format(len(tiles)))

import numpy
terrain_image_data = numpy.zeros((terrain_size_y, terrain_size_x, 3), numpy.uint8)

for tile_x in range(terrain_size_x):
	for tile_y in range(terrain_size_y):
		terrain_image_data[tile_y, tile_x] = colors[terrain[tile_y][tile_x] - 1]

from PIL import Image
terrain_image = Image.fromarray(terrain_image_data, 'RGB')

terrain_image.save("terrain.png")