Si retrocede un poco y considera qué es un laberinto, puede ver que es solo una red que se aplica típicamente a una cuadrícula regular (o rectangular). Cada celda tiene uno o más vecinos, y se crean pasajes entre esos vecinos para formar el laberinto. Suficientemente simple.
Esto funciona para cualquier configuración de celdas. Puede hacerlos hexagonales, triangulares o cualquier otra cosa, y siempre que pueda describir qué celdas son adyacentes a qué otras celdas, puede pasar a unir celdas adyacentes a través de pasajes.
¡Hasta aquí todo bien!
Esto nos lleva a las redes polares . Estos son círculos concéntricos, con “radios” que irradian hacia afuera desde el origen.
- ¿Por qué el WiFi de mi hogar se sigue desconectando de mi computadora portátil HP con Windows 8.1 Pro?
- Quiero jion ebiz es mejor no?
- Mi instinto sigue cambiando. ¿Qué tengo que hacer?
- Tengo un almacén lleno de registros antiguos en perfecto estado. La mayoría nunca abrió. Cientos de miles de ellos. Me gustaría venderlos a todos por un precio justo. ¿Cuál sería su mejor consejo para encontrar un comprador?
- Estoy usando Python 3. ¿Cómo puedo devolver una copia de la lista 1 con la lista 2 que se inserta en la posición indicada por el índice?
Los radios dividen los círculos concéntricos en –¡lo adivinaste! – células, cada una de las cuales tiene vecinos en sentido horario, antihorario, exterior e interior. ¡Ya que conoces a los vecinos, puedes unirte a esos vecinos con pasajes para formar un laberinto!
Sin embargo, las cuadrículas polares son un poco especiales, porque sin ninguna otra modificación, las celdas se ensanchan cada vez más a medida que te alejas del origen. Para mantener las celdas aproximadamente del mismo tamaño en todo el laberinto, debe introducir una subdivisión adaptativa, dividiendo las celdas cuando se ensanchan demasiado. Esto complica un poco la cuadrícula, ya que algunas celdas pueden tener dos vecinos (¡o más!) En dirección hacia afuera, y otras tendrán solo uno.
Pero eso es esencialmente todo. Si conoce un algoritmo de generación de laberintos (como Growing Tree, Prim’s, Kruskal’s, Recursive Backtracker, etc.), puede hacer un laberinto en una cuadrícula polar. La parte difícil es realmente descubrir la mejor manera de representar la cuadrícula polar.
(Por cierto, hay un capítulo completo sobre este tema en mi libro, “Laberintos para programadores” – https://pragprog.com/book/jbmaze….)
¡Buena suerte! Los laberintos son muy divertidos.