Cómo crear un laberinto de pacman aleatorio

Question

Hola He estado trabajando en un algoritmo para generar un laberinto de pacman aleatorio. He visto un par de artículos pero no pude desglosar la lógica. Estoy usando la primera búsqueda de profundidad del algoritmo laberinto y luego reflejo el laberinto para simétrico cada laberinto. Me estoy encontrando con problemas como limpiar los callejones sin salida. Si esto no es posible, también intentaría otro algoritmo si alguien tiene su propia lógica para generar el laberinto aleatorio. Cualquier ayuda es apreciada. Gracias

Answer 1

Me gustaría hacer una caminata aleatoria por dfs en el área limpia (sin ninguna pared, en n * n matriz de 0), después de eso llenan las áreas que no están cubiertas por la caminata aleatoria (hacerlas como pared), esto también podría causar espacios no utilizados, pero esto garantiza tener una larga caminata. puede establecer el tamaño de caminata arbitraria (por ejemplo, cuando su tamaño de caminata llegó a (n^2)/2, podría detener la caminata).

Answer 2

Resolví mi problema y quería compartir. Para empezar, configuré la fila superior y la primera columna y la última columna como un obstáculo de pared, luego establecí un camino en la segunda columna, de la penúltima a la segunda fila para que rodee la pared exterior. También ten en cuenta que solo estoy creando el 50% del laberinto, así que cuando termine copio el laberinto para que ambos lados estén iguales. Luego creé una sección central rodeada por una pared para el área donde aparecen los fantasmas. Entonces, cualquier parte del laberinto que no se haya analizado generé rutas usando el primer algoritmo de búsqueda de profundidad. Después de hacer esto, sé que en un laberinto de pacman no hay callejones sin salida. Lo que hice fue verificar cada celda que es parte del camino que pacman puede recorrer. Si alguna celda tiene solo 1 celda contigua, entonces es un callejón sin salida. Si es un callejón sin salida mira si puede conectarse a otra ruta. Si no, establece el callejón sin salida como una pared y revisa el laberinto de nuevo en busca de callejones sin salida. Después de seguir estos pasos, tendrás un laberinto aleatorio sin callejones sin salida que se asemeja al típico laberinto de pacman.

Answer 3

Creé un generador de laberintos PacMan al azar hace mucho tiempo en la C = 64 usando la profundidad primero y la eliminación de callejones sin salida, pero recientemente mi amigo me desafió a hacerlo nuevamente. Encontré una mejor manera. Échale un vistazo al my site

Esencialmente, creé una grilla de habitaciones con cada dirección teniendo una puerta abierta (cerrada en el borde excepto donde va el túnel), luego empiezo a cerrar las puertas al azar de acuerdo con la regla de que nunca ser más de 1 puerta cerrada en una habitación contigua si se cierran 2 puertas, una tercera crearía un callejón sin salida. Solo sigue haciendo esto al azar hasta que todas las puertas potenciales estén cerradas o abiertas por la regla.

La duplicación fue un poco más laboriosa, pero comencé con los conceptos básicos y simplemente construí las reglas para permitir la creación de reflejos, la ubicación de la casa fantasma, la longitud mínima de pared (sin rotondas amuralladas) y la longitud máxima de pared, etc.