¿Cómo crear laberintos en el plano hiperbólico?

Question

Estoy interesado en construir estructuras laberínticas en el mosaico [5, 4] del plano hiperbólico, donde por laberinto me refiero a algo parecido a un árbol de extensión del entramado subyacente: un subgrafo del entramado que sigue estando conectado (cada celda puede llegar a todas las demás) pero con una especie de efecto de "multiplicador de distancia" en el que desde cualquier celda dada en el entramado, es probable que haya celdas cercanas en el mosaico original con un largo "camino más corto" a través del subgrafo para llegar a ese punto. (Se trata de una noción ciertamente imprecisa, pero dudo que haya resultados explícitos sobre este tipo de cosas). Podría utilizar cualquiera de los algoritmos estándar de generación de laberintos, pero implican un "prepaso" que mantiene todo el grafo de la celosía en la memoria y, por lo tanto, no son realmente prácticos para celosías infinitas (o funcionalmente infinitas); estoy buscando algo que pueda generar paredes (o, equivalentemente, cortar aristas del grafo subyacente) de forma "local" sin necesidad de mirar explícitamente la estructura global.

Si estuviera en el plano, hay formas relativamente sencillas de hacerlo: por ejemplo, para cada celda, colocar un muro al azar en el borde sur o este de esa celda. Con una probabilidad de 1, esto creará un árbol de extensión del plano. No es un árbol de extensión "aleatorio" (en particular, por supuesto, es imposible que cualquier celda tenga tanto su lado sur como su lado este "amurallados", lo que imagino que ocurre con una probabilidad 0 para un árbol de extensión aleatorio del plano), pero es un árbol, aun así. Por ejemplo, aquí hay dos $5\times 5$ rejillas de celdas con sus lados este o sur amurallados al azar:

Del mismo modo, si el proceso de generación utiliza una moneda de tres caras con las mismas probabilidades de sacar una pared sur, una pared este o ninguna pared, entonces las cuadrículas resultantes no son árboles de distribución (pueden existir múltiples caminos disjuntos entre los nodos), pero siguen teniendo claramente el tipo de multiplicación de distancia que estoy buscando:

Desgraciadamente, estas técnicas no funcionan tan bien para la malla hiperbólica que me interesa; obtener una noción canónica de los bordes exteriores es un poco más difícil, y la "vaguedad" del resultado es mucho más difícil de controlar. ¿Alguien conoce un esquema similar a las técnicas de lanzamiento de monedas en el que sólo se genere/utilice información local que pueda aplicarse a mallas regulares arbitrarias?

Answer 1

Su método para la malla cuadrada euclidiana introduce una asimetría entre el sureste y el noroeste que da lugar a dos características cruciales:

• Desde cada punto, hay una pared que va al norte o al oeste. Estos muros forman infinitas obstrucciones contiguas hacia el noroeste; su curso, partiendo de un punto cualquiera, es un paseo aleatorio cuya dirección converge hacia el noroeste. Así, en cada punto, independientemente de lo que ocurra al sureste del mismo, el plano al noroeste del punto está dividido en dos mitades, y hay que volver al sureste del punto para llegar de una mitad a la otra.

• En cambio, hacia el sureste, todas las plazas están abiertas hacia el sur o el este. Por lo tanto, desde cada casilla se puede realizar un paseo aleatorio infinito hacia el sureste. Si empiezas en dos lugares diferentes, estos paseos aleatorios infinitos se encontrarán con la probabilidad $1$ por lo que todo es un árbol de expansión con probabilidad $1$ .

Para trasladar esta idea al plano hiperbólico, tenemos que introducir una asimetría similar. Para ello, podemos señalar un punto y distinguir entre los pasos que se dirigen hacia el punto o se alejan de él. Mientras que en el caso euclidiano podríamos intercambiar los papeles de sureste y noroeste, en el caso hiperbólico el método sólo funcionará en un sentido. Si dejamos que las paredes contiguas corran hacia el punto elegido y los caminos contiguos se alejen de él, los caminos divergirán más rápidamente de lo que fluctúan aleatoriamente entre sí, y generalmente no habrá caminos entre todos los sitios. Sin embargo, si dejamos que las paredes contiguas se alejen del punto elegido y los caminos contiguos corran hacia él, entonces se garantiza que todos los sitios estén conectados, y las paredes contiguas obligarán a que las conexiones entre los sitios cercanos en lados opuestos vayan todo el camino "hacia adentro" hasta donde comienza la pared.

Aquí hay una imagen de un laberinto en el $[5,4]$ mosaico del plano hiperbólico creado de esta manera, visualizado mediante el modelo de disco de Poincaré. Los segmentos rectos, que no se alejan ni se acercan al centro, están todos amurallados, excepto los más interiores. Para los segmentos arqueados, cada baldosa "posee" los que se dirigen hacia el centro desde esa baldosa, es decir, aquellos para los que la baldosa está en el interior del círculo del que el segmento es un arco. Para cada baldosa, exactamente uno de los segmentos que posee está abierto, elegido al azar con una distribución uniforme, y los demás están amurallados.

Más adelante crearé algunas imágenes más de cómo se ve el laberinto si colocamos el centro del disco en un punto diferente (es decir, no el utilizado como centro para la construcción del laberinto). Avísame si quieres que publique el código que he utilizado para crear esto.

Answer 2

Los laberintos se pueden crear en el plano hiperbólico muy fácilmente: sólo hay que asegurarse de que los puntos de partida y de llegada sean alcanzables desde regiones infinitas, y conectar las celdas al azar con una probabilidad suficientemente alta, y se garantiza que el laberinto es resoluble. No estoy seguro de que esto sea exactamente lo que quiere Steven Stadnicki, pero genera laberintos interesantes. Estoy usando esto en HyperRogue -- la idea es la más fácil de explicar con el laberinto de Princess Quest.

Este es el patrón periódico utilizado, que consiste en habitaciones heptagonales (que tienen siete puertas) e infinitos pasillos en forma de árbol. Las puertas se abren o se cierran aleatoriamente; si están cerradas, se pueden abrir pisando las placas verdes cercanas (que pueden no existir, o pueden existir en el otro lado). Normalmente empiezas a 100 pasos en la dirección de las 12, y tu objetivo es liberar a la princesa pisando la placa verde (a las 7 en la imagen).

Se garantiza que es posible liberar a la Princesa:

• la placa de apertura siempre aparece en un pasillo, por lo que su componente conectada es infinita (y de forma similar para el punto de partida),
• si se considera el obstáculo (es decir, la prisión de la princesa y todas las demás salas heptagonales que hay que sortear mientras se intenta llegar a ella), tiene una estructura de árbol: para sortear la sala heptagonal dada $H$ También hay que sortear cada una de las 6 salas heptagonales adyacentes a $H$ (6 porque no incluimos al padre). La probabilidad de que una habitación determinada tenga hijos depende de las probabilidades de que se abran/cierren las puertas y se abran las placas. Esta probabilidad es lo suficientemente alta como para que el laberinto sea interesante, pero lo suficientemente baja como para asegurar que el proceso de ramificación obtenido genere un árbol finito con probabilidad 1. (La geometría hiperbólica es importante en este argumento - de lo contrario habría ciclos en el gráfico de obstáculos; bueno, supongo que podría ajustarse a la geometría euclidiana, pero la situación es mucho más complicada, y los laberintos generados son menos interesantes OMI).

Esta es la Búsqueda de Yendor en el Infierno: tienes que llegar a una celda a 100 pasos de distancia, para encontrar la llave para abrir el Orbe púrpura de Yendor. Esta construcción de obstáculos es muy sencilla (basta con elegir algunas baldosas al azar como centros de "grandes estrellas", y todas las baldosas adyacentes a ellas son infranqueables), pero un razonamiento similar garantiza que genera un laberinto resoluble. (HyperRogue no garantiza que las regiones de inicio/clave sean infinitas, porque de todos modos es extremadamente improbable que sean finitas, pero sería fácil garantizarlo).