¿Se puede resolver el laberinto de mapas de la casa con ascensores?

13

En mi juego vemos los pisos de una casa desde un costado, y el héroe puede tomar ascensores: un ascensor sube (al siguiente ascensor hacia arriba) o hacia abajo (al siguiente ascensor hacia abajo), dependiendo de la flecha como se muestra, y siempre hay un par de exactamente dos ascensores conectados. Esa es la única forma en que el héroe puede moverse verticalmente, aunque puede moverse libremente horizontalmente. El mapa de la casa es una cuadrícula aleatoria de 11x5 con diferentes elementos y paredes que no se pueden pasar a la izquierda, a la derecha y, a veces, en una de las dos posiciones centrales:

ejemplo de ascensores

Mi pregunta: ¿cómo puedo asegurarme de que el mapa esté siempre aleatorizado pero siempre solucionable y que el héroe, comenzando en el lado izquierdo del piso inferior, siempre pueda dejarlo a través de un elevador que apunta hacia arriba en el piso superior?

Por lo que vale, estoy usando el lenguaje Lua para el desarrollo. ¡Muchas gracias!

2d maze Philipp Lenssen
fuente

Respuestas:

14

Lo que desea hacer es crear un gráfico de manera que cada nodo sea una posición de ascensor, y los bordes entre ellos significan que puede caminar / levantar allí. Una vez que haya hecho el gráfico, puede usar dfs / bfs para ver si puede llegar desde el nodo inicial hasta el nodo final.

Usando su ejemplo anterior, hice una imagen de cómo se vería el gráfico. Los círculos verdes significan que hay un elevador allí, y las líneas verdes significan que puede viajar de un nodo a otro.

nodos

Luis Estrada
fuente
Gracias, eso es muy útil! Debería haber enfatizado más en mi pregunta que el mapa también necesita ser generado en primer lugar. Lo que ahora estoy reflexionando es si podría no ser más fácil, en lugar de generar combinaciones de elevación / pared completamente aleatorias una y otra vez y verificar su capacidad de solución, que el algoritmo atraviese la casa, como lo haría el héroe, y de esta manera generar elevaciones y puertas aleatorias (tomando distancias de elevación aleatorias y giros de izquierda a derecha, así como agregando paredes, por ejemplo). Como en "Camina a la derecha ya sea 0, 4 u 8 vueltas; crea una elevación hacia arriba, sube de 1 a 4 pisos ..."
Philipp Lenssen
@PhilippLenssen Ese es esencialmente el enfoque de "búsqueda aleatoria de profundidad primero" para la generación de laberintos en un gráfico.
Kevin Reid
5

La diferencia entre lo que tienes y un laberinto normal es simplemente que tiene conexiones no adyacentes verticalmente. Creo que lo que debería mirar son los algoritmos de generación de laberintos basados en gráficos . Simplemente necesita tener un conjunto más grande de "habitaciones adyacentes" o "paredes posibles" que un laberinto 2D común, ya que cada par verticalmente alineado de celdas de piso-cuadrícula que aún no tiene un ascensor intermedio es adyacente. Podría modelar esto como un gráfico en el que agregar bordes de elevación definidos elimina accidentalmente otros posibles bordes de elevación; Esto podría confundir algunos algoritmos, pero no otros.

Kevin Reid
fuente