Chismes del Lince 61: laberinto aleatorio

Es de noche en Sierra Bermeja. El Lince de la Noche está sentado a la entrada de su cueva, repasando los casos que los Centuriones de la Verdad tienen abiertos. Hoy hacemos un laberinto aleatorio.

—Esta semana, un dron perdido. La siguiente, una pista falsa. Y la otra… quién sabe —resopla—. Cada vez es una prueba distinta.

La Gata Montesa lo mira desde lo alto de una roca.

—Exacto. Las pruebas son infinitas, Lince. Nadie se las sabe de memoria. Por eso hay que entrenar el cerebro, no solo las patas.

—Ya entreno. Corro por la sierra todas las mañanas.

—Eso es para las patas —dice la Gata, y señala una puerta de piedra al fondo de la cueva, con un panel que parpadea—. Esto es para la cabeza.

El Lince se acerca. Sobre el panel se lee, en letras azules: Cámara de la Verdad.

—Es una simulación de los Centuriones —explica la Gata—. Una realidad virtual que se inventa un reto nuevo cada vez. Hoy, un laberinto. Paredes de luz, una salida y ningún mapa.

—¿Y quién dibuja un laberinto nuevo cada vez? ¿Un ejército de arquitectos?

—Un programa. Y hoy lo vas a leer.

El Lince se pone las gafas, se enciende la cámara y las paredes aparecen como hilos de luz azul. Da un paso. Choca con un muro invisible.

—Está todo hecho de números —dice la Gata—. Y a veces, para llegar al fondo, solo hay que inclinar el móvil hacia donde quieres ir.

El Lince inclina la cabeza, por si acaso.

Introducción: un laberinto aleatorio para entrenar la cabeza

En este chisme construimos un laberinto aleatorio: un mini-juego en el que cada prueba es un laberinto nuevo, creado por un programa.

Se juega con el teclado, con el dedo o inclinando el móvil. Hay niebla, límite de tiempo y un botón para pasar a una prueba más grande, así que el entrenamiento no se acaba.

Lo importante es lo de siempre: a la vez que juegas ves el programa real que hace cada cosa. Crear el laberinto, dar un paso, resolverlo y leer el sensor del móvil son cinco funciones cortas que puedes leer.

Es el chisme de diseño de mini-juegos de 1º de Bachillerato. El alumnado juega un rato, pero también responde a la pregunta de verdad: ¿cómo está hecho esto por dentro?

Todo ocurre en tu navegador. No se sube nada y no hay que instalar nada.

Cómo crea el ordenador un laberinto aleatorio

La Gata plantea el problema: «¿Cómo le explicas a un ordenador qué es un muro?»

La solución es una tabla de casillas. Un laberinto de 11 × 11 son 121 casillas, y cada una guarda un número que dice qué muros tiene.

Muro	Valor
Arriba	1
Derecha	2
Abajo	4
Izquierda	8

El número de la casilla es la suma de sus muros. Un 15 es una casilla cerrada (1 + 2 + 4 + 8). Un 0 es una casilla sin muros. Un 13 (1 + 4 + 8) tiene muro arriba, abajo y a la izquierda, y solo deja salir a la derecha.

En binario, cada muro es un bit encendido o apagado. Para comprobar un muro, el programa usa un operador de bits: if (casilla & 2) pregunta si hay muro a la derecha.

Derribar muros

El programa empieza con todas las casillas en 15 y va derribando muros:

1. Se coloca en la casilla de arriba a la izquierda.
2. Elige al azar una vecina que aún no ha visitado y derriba el muro entre las dos.
3. Se mueve a esa vecina y guarda en una pila el camino que lleva.
4. Si no hay vecinas libres, saca casillas de la pila para volver atrás.
5. Cuando la pila se vacía, el laberinto está terminado.

Es una búsqueda en profundidad. El resultado es un laberinto «perfecto»: entre dos casillas cualesquiera hay un camino y solo uno.

¿Aleatorio de verdad?

No. Un ordenador no tira dados: calcula una serie de números que lo parece. Si empiezas por el mismo número, la semilla, obtienes la misma serie y, por tanto, el mismo laberinto.

Eso es una ventaja. Cada sala tiene un código (por ejemplo 11-1234: tamaño 11, semilla 1234) y dos alumnos con el mismo código juegan el mismo laberinto.

La Gata resuelve el laberinto

El Lince lleva diez minutos dando vueltas. La Gata bosteza y pulsa un botón.

En pantalla aparecen casillas rosas que se extienden desde donde está el Lince, como una mancha de tinta. Cuando la mancha toca la salida, se dibuja una línea rosa: el camino más corto.

—¿Cómo lo hace? —pregunta el Lince.

—Mira primero las casillas a un paso, luego las que están a dos, luego a tres… Cuando llega a la salida, ya sabe que lo ha hecho por el camino más corto.

Es una búsqueda en anchura. Usa una cola (lo primero que entra es lo primero que sale) y apunta de qué casilla ha llegado a cada una. Para dibujar el camino, lo reconstruye hacia atrás desde la salida.

Las casillas rosas son todas las que la Gata tuvo que mirar, no solo las del camino. Ese es el precio de estar segura: explora mucho más de lo que usa.

En la pantalla verás también la eficiencia del Lince: el camino mínimo dividido entre los pasos que ha dado de verdad.

Moverse inclinando el móvil

El Lince quiere dejar el teclado. La Gata propone usar lo que ya lleva el móvil: un sensor que sabe hacia dónde está inclinado.

Es el mismo principio del nivel de burbuja con micro:bit. Aquí el navegador nos da dos ángulos en grados:

• gamma: inclinación a izquierda o derecha.
• beta: inclinación hacia delante o hacia atrás.

El evento deviceorientation los manda unas 60 veces por segundo. La función inclinacion hace tres cosas:

1. Resta la calibración. Cada persona sujeta el móvil distinto. Al pulsar Calibrar, esa postura pasa a ser el cero.
2. Aplica un umbral. Si ningún ángulo supera 14°, el Lince se queda quieto. Sin umbral, el temblor de la mano lo movería sin parar.
3. Elige un eje. Gana el ángulo mayor, y el signo decide la dirección.

Mientras sigas inclinado, el Lince da un paso cada 170 milisegundos. Si no esperara entre pasos, atravesaría el laberinto en un parpadeo.

En iPhone, el navegador pide permiso para leer el sensor y hay que concederlo con un toque. En Android, normalmente, no hace falta.

La Cámara de la Verdad: el juego

La herramienta es una página web que ya hemos preparado. No hay que instalar nada ni escribir código. Puedes usarla aquí mismo:

<iframe src="https://montesteam.org/app/chisme61-laberinto.html"
  width="100%" height="1700" style="border:0"
  allow="accelerometer; gyroscope" loading="lazy"
  title="La Cámara de la Verdad del Lince: laberinto aleatorio"></iframe>

Si la inclinación no funciona dentro de la entrada, abre la página del juego en una pestaña aparte desde el móvil. Para leer el sensor hace falta https.

Tres pasos:

1. Prepara la sala. Elige tamaño y semilla, o entra con un código de otra sala. Activa niebla o tiempo si quieres más dificultad.
2. Juega. Con flechas o WASD, arrastrando el dedo, con la cruceta o inclinando el móvil.
3. Mira por dentro. Pulsa los botones del apartado El programa que hace cada cosa y lee el código. Despliega la tabla de números del laberinto.

El botón Siguiente prueba crea un laberinto más grande con una semilla nueva, y La Gata resuelve desde aquí muestra la solución.

Aviso de privacidad. El juego se calcula en tu navegador. Los datos del sensor no se guardan ni salen de tu dispositivo.

Qué estamos midiendo realmente

Pseudoaleatorio no es azar. Los números del laberinto salen de una fórmula. Parecen azar, pero son predecibles si conoces la semilla. Para un juego sirve. Para guardar contraseñas, no.

El ángulo del móvil es una medida con error. Beta y gamma salen de un acelerómetro y, según el modelo, de un giróscopo y un magnetómetro. Cada sensor tiene ruido y deriva. Dos móviles sujetos en la misma postura pueden dar ángulos distintos.

Por eso hay calibración y umbral. La calibración elimina el «cero» propio de cada sensor y de cada mano. El umbral de 14° evita que el ruido y el temblor muevan al Lince. Es un valor elegido por prueba y error, no una verdad física.

Un dato no es una medida buena. El móvil siempre da un número. Eso no garantiza que sea correcto: con la pantalla girada, o con el móvil casi horizontal, los ejes cambian y las lecturas dejan de significar lo mismo.

La Gata explora más de lo que usa. En un laberinto de 11 × 11 tiene 121 casillas. En uno de 31 × 31, 961: ocho veces más casillas, no el triple. El trabajo crece con el área, no con el lado.

La eficiencia mide un solo aspecto. Un 100 % significa que no diste ningún paso de más. No mide si exploraste con inteligencia ni cuánto tardaste.

Para el aula

• Misma semilla, mismo laberinto. Dos alumnos entran con el mismo código. ¿Se parecen los laberintos? Ahora cambian un solo dígito de la semilla. ¿Qué ocurre? ¿Por qué?
• Estrategia. Antes de jugar, escribe tu estrategia. Después compara tu eficiencia con la de la clase. ¿La mano derecha pegada a la pared siempre funciona?
• Tabla de bits. Con un laberinto de 5 × 5, dibuja a mano cada casilla a partir del número de la tabla. Después haz lo contrario: dibuja un laberinto y escribe sus números.
• Medir el ruido. Deja el móvil sobre la mesa con la inclinación activada y anota los ángulos durante un minuto. ¿Son exactamente 0°? ¿Cuánto varían?
• Dos móviles. Pon dos móviles sobre la misma tabla inclinada. ¿Dan el mismo ángulo? ¿Qué diferencia hay?
• Calibrar o no. Juega con la calibración y sin ella. ¿Qué cambia? ¿Por qué?
• Cambia un número. En el código de la inclinación cambia UMBRAL y prueba. ¿Con qué valor es injugable? ¿Y aburrido?
• Complejidad. Mide con un cronómetro cuánto tarda la Gata en resolver laberintos de 11, 21 y 31. ¿Crece lineal o más rápido?

Retos

1. Reto 1. Haz que funcione. Entra en la Cámara de la Verdad y llega a la salida con el teclado o con el dedo.
2. Reto 2. Modifica algo. Juega con el móvil inclinado. Busca el valor de UMBRAL con el que te sientas más cómodo.
3. Reto 3. Cambia los parámetros. Consigue una eficiencia de 100 % en un laberinto de 15 × 15 con niebla a 3.
4. Reto 4. Retos entre compañeros. Cada uno elige una semilla difícil y escribe su código de sala. Se intercambian y compiten por el menor tiempo.
5. Reto 5. Representa los datos. Anota el tiempo y la eficiencia de diez salas y haz una gráfica. ¿Hay relación entre tamaño y eficiencia?
6. Reto 6. Mejora el juego. Añade una llave que haya que recoger antes de abrir la salida. Cambia en mover la condición de victoria.
7. Reto 7. Otro algoritmo. Cambia la búsqueda en profundidad por otra forma de derribar muros y compara cómo son los laberintos.
8. Reto 8. Pequeña investigación. ¿Cuántos grados de umbral prefiere la mayoría de la clase? Diseña la prueba, recoge datos y escribe la conclusión.

Qué hemos aprendido

Un laberinto es una tabla de números: cada casilla suma los muros que tiene, y cada muro es un bit. Un programa con una pila y una semilla lo dibuja entero, y otro con una cola lo resuelve.

Hemos visto también que el «azar» del ordenador es una fórmula, y que el ángulo de un móvil es una medida con ruido que hay que calibrar y filtrar con un umbral.

El Lince salió de la Cámara de la Verdad con la eficiencia justa y un dolor de cuello por inclinar la cabeza. Pero en la siguiente prueba, cuando el laberinto era otro, ya no chocaba con la primera pared.

Para seguir investigando

• Simón dice con gestos: otro juego, con la micro:bit.
• Reflejos de Repálago: un juego que mide tu tiempo de reacción.
• El nivel de burbuja: ángulos de inclinación.
• Documentación oficial del evento deviceorientation en MDN, que usa el juego para leer el sensor.