Infinite Labyrinths

English    Spanish

In a previous article (Truchet Tilings) I showed a way to represent labyrinths in a sphere and at the end, in a plane. In this one I'm going to show a way to represent infinite labyrinths in a plane.

Usually these labyrinths are finite sets of triangles. One of the problems in this type of representations is that you can see boundings.

One way to solve this is replicating the figure. Sooner or later you'll be able to see a periodic shape, noticing an artificial behaviour.

So, if you want to show infinite labyrinths, you'll have to find a method that satisfy these conditions:

• Covers all the visible domain.
• Absence of periodicity in the image.

The way that I present here in order to do this task is the next one:

• Split the plane (in an algorithmic manner) in square regions of unit size (a grid of infinite squares, each one with one unit of side length).
• Asign to each square region a tridimensional figure (for example, a wall in a side).

When a ray step inside a region, it will intersect with the associated shape in that region. When, by reflexion or traversing, it changes the region, a new intersection will be computed with the new form associated to the new region.

Here I show a sample using always the same shape.



This method presents a set of decissions:

• How many types of shape should I use.
• How I assign to each region a concrete shape.

The first point is chosen by the user. For example, my set of shapes will be:

• A wall of 0.1 units width and 1 unit length arranged in a north face of the region.
• Another similar wall arranged in the west face.

For the second point we have to think a bit. To each coordinate (integer) of the space I have to assign a random number. The function will be f(i,j)->n. Being i and j integer numbers and n a real number from 0 to 1. This function has to return values highly distinct of 'n' using slight variations of i and j. This is either a hashing function or a pseudorandom generator. Esentially are the same.
The generator will be a LCM (Linear Congruent Method) generator. We run the risk of having the Marsaglia effect. It will appear, and the user might see a certain periodicity but will be very dificutl to distinguish.

Each shape has a certain probability for appearing (for example: 1/number_of_figures). It will choose the figure using the method of the Russian roulette depending on the generated random number. As the number is pseudorandom and depends on the input paramaters, it always return the same value for the same input parameters.

The results are these:


And with a different probability distribution:


As you can see, choosing this kind of figures, as the norwest corner is always occupied, the aspect seems to be a growing figures in the same direction.

It can be resolved by adding another figure that is a double wall south and east. So using this way the distribution of corners is uniform and doesn't seem to grow in any direction. Althoug this adds more holes and makes the maze looks more closed.


This is with a figure with a column in the middle of the region:


Making simplier walls appears problems of double corners and doesn't seems very well.

Finaly there is a more complex method than the previous one. Consists on chosing figures randomly only in pair coordinates (i,j) which sum i+j are even (from this point, even regions). That yields a checker pattern. In the even regions we assign one shape selected by the pseudorandom generator. In the other hand, in the odd regions the shape is assigned by a shape that matchs with the shapes that are sharing each face. That is, if the north face of the figure that I have in the south has a wall, my south face should have a wall. So, both walls match together.

Choosing correctly the shapes and with a little extra programming we can achieve these images:




Using non linear cameras:


Using some procedural textures and phong materials:


If we use the first proposed method the labyrinth looks like this:

That's wrong but nice to test global illumination.

Obviously changing slightly the hashing function (adding a sum operation, in example) we can make labyrinths totaly indistinguishable ones with each others. We have graphically represented the hashing function.

En un artículo anterior (Truchet Tesellations) mostré una forma de representar laberintos en una esfera y por el final, en un plano. En este voy a mostrar otra forma de representar laberintos infinitos en un plano.

Normalmente estos laberintos son conjuntos finitos de triangulos. Uno de los principales problemas en este tipo de representaciones es que se pueden ver límites.

Una manera de resolver esto es replicando la figura. Tarde o temprano se puede intuír una figura periódica, notándose un comportamiento artificial.

Por lo tanto si se desea representar laberintos infinitos habrá que buscar una manera que cumpla las siguientes condiciones:

• Cubra todo el dominio visible.
• Ausencia de periodicidad en la imagen.

La manera que presento para realizar este cometido es el siguiente:

• Dividase el plano (de forma algorítmica) en regiones cuadradas de dimension unitaria (una rejilla de infinitos cuadros, en los que cada cuadro mide una unidad de lado).
• Asígnese a cada region cuadrada una figura tridimensional (por ejemplo, un muro en una pared).

Cuando un rayo incida en una región, intersectará con la forma asociada a esa región. Cuando, por reflexión o atravesamiento, cambie de región se computará la intersección con la asignada a ésta.

Aquí muestro un ejemplo usando siempre la misma forma.



Este método presenta una serie de decisiones:

• Cuántos tipos de figuras uso.
• Cómo asigno cada región una figura determinada.

El primer punto lo elije el usuario. Por ejemplo, mi conjunto de figures será:

• Un muro de 0.1 unidades de ancho por 1 unidad de largo puesto en la cara norte de la región.
• Otro muro similar orientado en la cara oeste.

Para el segundo punto hay que pensar un poco. A cada coordenada (entera) del espacio le he de asignar un número aleatorio. La función sería f(i,j)->n. Siendo i y j números enteros y n un número real de 0 a 1. Esa función ha de devolver valores muy dispares de 'n' para valores cercanos de i y j. Esto es o una función de hashing o un generador de números pseudo-aleatorios. Esencialmente son lo mismo.
El generador será un LCM o congruente lineal. Corremos el riesgo de que se de el efecto Marsaglia. Se dará, y el usario quizás vea una cierta periodicidad, pero dificil de ver.

Cada figura tiene una probabilidad de aparición determinada (por ejemplo, 1/número_de_figuras). Se seleccionará la figura usando la técnica de la ruleta rusa según el número aletorio generado. Como el número es pseudoaleatorio y depende de los parámetros de entrada siempre devolverá el mismo valor para mismos valores de entrada.

Los resultados son los siguientes:


Y con una distribución de probabilidad diferente:


Como puede verse, al escoger este tipo de figuras, hace que la esquina noroeste siempre esté ocupada por lo tanto el aspecto es de figuras que parece que crecen en una misma dirección.

Se pueden resolver añadiendo otra figura más que es un muro doble este-sur. De esta manera la distribución de esquinas es uniforme y no se ve que "crezca" en ninguna dirección. Esto añade más huecos y hace que el laberinto esté mas cerrado.


Esta es con una figura con una columna en el medio de la región:


Haciendo muros simples aparecen problemas de esquinas dobles y no queda bien.

Finalmente hay un método más complicado que el anterior. Consiste en elegir figuras aleatoriamente sólo para coordenadas (i,j) cuya suma i+j sea par (a partir de ahora, regiones pares). Lo que produce un patrón ajedrezado. A las regiones pares se les asigna una figura según el generador de números aleatorios (o función de hashing). En cambio, a las regiones impares se les asigna una figura que case con las figuras con las que comparte una cara. Esto es, si la cara norte de la figura que tengo al sur tiene muro, mi cara sur ha de tener muro.

Eligiendo correctamente las figuras y con un poco de codificación extra se producen estas imágenes:




Usando cámaras no lineales:


Usando algunas texturas procedurales y materiales de phong:


Si usamos el primer método propuesto para el laberinot aparece así:

Esto es incorrecto pero queda bien para iluminación global

Obviamente cambiando ligeramente la función de hashing (añadiendo una suma, por ejemplo) se pueden construir laberintos totalmente indistinguibles unos de otros. Hemos representado gráficamente una función de hashing.