Procedimiento ... casa con generador de habitaciones

74

He estado mirando algunos algoritmos y artículos sobre la generación procesal de una mazmorra. El problema es que estoy tratando de generar una casa con habitaciones, y no parecen cumplir con mis requisitos.

Por un lado, las mazmorras tienen pasillos, donde las casas tienen pasillos. Y aunque inicialmente pueden parecer lo mismo, un pasillo no es más que el área que no es una habitación, mientras que un corredor está específicamente diseñado para conectar un área con otra.

Otra diferencia importante con una casa es que tiene un ancho y una altura específicos, y tiene que llenar todo con habitaciones y pasillos, mientras que con una mazmorra, hay espacio vacío.

Creo que los pasillos en una casa es algo entre un corredor de mazmorra (te lleva a otras habitaciones) y un espacio vacío en la mazmorra (no está explícitamente definido en el código).

Más específicamente, los requisitos son:

  • Hay un conjunto de habitaciones predefinidas
    que no puedo crear paredes y puertas sobre la marcha.
  • Las habitaciones se pueden rotar pero no cambiar su tamaño.
    Nuevamente, debido a que tengo un conjunto predefinido de habitaciones, solo puedo rotarlas, no redimensionarlas.
  • Las dimensiones de la casa están establecidas y deben estar completamente llenas de habitaciones (o salas). Es
    decir, quiero llenar una casa de 14x20 con las habitaciones disponibles, asegurándome de que no haya espacio vacío.

Aquí hay algunas imágenes para aclarar esto un poco:

Generador de mazmorras típico Mazmorra sin pasillos Resultado generador de la casa

Como puede ver, en la casa, el "espacio vacío" todavía es transitable y lo lleva de una habitación a otra.

Entonces, habiendo dicho todo esto, tal vez una casa es solo una mazmorra realmente muy apretada con pasillos. O es algo más fácil que una mazmorra. Tal vez hay algo por ahí y no lo he encontrado porque realmente no sé qué buscar.

Aquí es donde me gustaría su ayuda: ¿ podría darme consejos sobre cómo diseñar este algoritmo? ¿Alguna idea sobre qué pasos tomará? Si has creado un generador de mazmorras, ¿cómo lo modificarías para que se ajuste a mis requisitos? Puedes ser tan específico o genérico como quieras. Estoy buscando elegir tu cerebro, de verdad.

pek
fuente
2
Una recomendación extraña: recomiendo consultar los libros de Christopher Alexander The Timeless Way Of Building y A Pattern Language , los libros de arquitectura que formaron la base original de la noción de un patrón (software); esencialmente describen un lenguaje explícito para edificios y espacios habitables que se puede convertir en un método de construcción de procedimiento de arriba hacia abajo.
Steven Stadnicki
Personalmente, trataría de hacer un algoritmo como la respuesta de egarcias. Comience generando marcadores de posición de habitación (áreas grandes que se pueden llenar con un número variable de habitaciones. Se requiere que cada marcador de posición de habitación tenga un espacio de tamaño específico (o aleatorio con límites más bajos) entre ellos. El espacio de "espacio" es lo que sería considerado un pasillo, es decir, un espacio que está en la casa pero no en una habitación, y los marcadores de posición de la habitación se llenarían con habitaciones de tamaño aleatorio similar a su ejemplo de 'mazmorra sin pasillos'.
Benjamin Danger Johnson el
@pek Cree una respuesta para su solución, no la ponga en la pregunta.
MichaelHouse
@ Byte56 Hecho. Para ser claros, lo hice porque no quería obtener crédito ya que solo hice lo que otras personas sugirieron. Sin embargo, entiendo por qué eso no es ideal para el formato del sitio, así que agregué mi respuesta.
Pek
Gracias @pek. No se preocupe por obtener crédito, es merecido y es útil para las personas que visitan el sitio para ver la solución (y verla donde se espera que sea mejor).
MichaelHouse

Respuestas:

50

Creo que este es un buen caso para usar la partición de espacio binario o ternario.

En el primer pase, divida el espacio de la casa en pasillos y {bloques de habitaciones}. Obtenga el próximo fragmento grande, divídalo en {hall and chunk} o {2 trozos y hall entre ellos}. En cada paso, gire la dirección de corte en 90 grados. Deténgase cuando {no queden más trozos grandes} o {el área total de la sala alcance el límite}.

En el segundo pase, divide los trozos restantes en habitaciones. Obtenga el próximo gran trozo y divídalo. Omita dividir algunos fragmentos no tan grandes al azar, para tener algunas habitaciones grandes.

Si alguna sala está orientada hacia una sala mucho más antigua, coloque la pared (o pared con puerta) allí.

Conecte habitaciones con pasillos directamente o a través de otras habitaciones ya conectadas.

Por ejemplo, puede ver mi resultado creado manualmente o C ++, como un pseudocódigo parcialmente hecho . Disparo final:

tiro final

Sombras en la lluvia
fuente
Ahí es donde mi investigación resultó, en la división del espacio. Su ejemplo con código me dio un muy buen comienzo. Actualmente estoy leyendo sobre algoritmos. Sin embargo, una pregunta: uno de mis requisitos es que las habitaciones estén predefinidas (es decir, hay habitaciones 2x2 con una puerta, 1x1 con dos puertas, pero no 2x2 con tres puertas), por lo que no puedo comenzar a dividir y luego decidir dónde colocaré las puertas . Creo que tengo que tener en cuenta mis limitaciones mientras particiono. ¿Tiene alguna sugerencia sobre cómo haría esto? En cualquier caso, ¡muchas gracias por su respuesta y esfuerzo!
Pek
@pek No estoy seguro de si un simple mortal puede encontrar una solución académica para este problema. Puede intentar establecer condiciones adicionales para el divisor de fragmentos y el divisor de caja, y luego generar y soltar niveles hasta que encuentre uno donde se puedan cumplir todas las condiciones.
Shadows In Rain
Sí, esperaba que me faltara algo. Mi primer enfoque fue usar A * para descubrir cómo encajar las habitaciones en un espacio dado, pero carecía de lógica para los pasillos. Ahora estoy pensando que puedo usar BSP para colocar pasillos y luego usar A * para los bloques. Lo que más me preocupa es que puede ser demasiado costoso y no siempre produce un resultado. Pero tendré que probar esto primero. Tal vez no será tan malo?
Pek
2
@pek Encontré algo útil, si aún estás interesado. Mira esto , también google L-system.
Sombras en lluvia
24

Puede aprovechar el hecho de que su diseño deseado agrupa las habitaciones en habitaciones rectangulares rodeadas de pasillos. Con eso en mente, haría esto:

  1. Diseñar los pasillos y los "grandes espacios" para las habitaciones.
  2. Complete cada "gran espacio" con habitaciones

2 pasos

Llenar los grandes espacios con habitaciones se puede hacer fácilmente si comienza con las habitaciones en los bordes: tienen limitaciones específicas, por ejemplo, las habitaciones que dan a un pasillo pueden tener una puerta en esa pared, pero las habitaciones que dan a las "paredes exteriores" no puede (podrían tener ventanas, tal vez). Las habitaciones "dentro" de los grandes bloques de habitaciones necesitarán al menos una entrada.

egarcia
fuente
15

Entonces, así es como resolví este problema. Pero primero, me gustaría agradecer a @Shadows In Rain y @egarcia por sus respuestas. Me dieron una buena dirección que me ayudó a obtener algunos resultados.

Utilicé la partición espacial de Shadows In Rain para generar una casa básica y luego seguí los consejos de egarcia para llenar el área con habitaciones.

La partición del espacio fue bastante sencilla ya que el 90% del código fue realizado por Shadows. La parte de "llenar las habitaciones" fue un poco más desafiante. Decidí usar un pseudo sistema de planificación de IA que usa A * para colocar las habitaciones de manera adecuada. Lo bueno de usar la planificación en lugar de solo A * es que las condiciones previas ayudan a reducir significativamente el espacio de búsqueda.

Aquí hay algunas capturas de pantalla con los resultados:

Fase de generación de planta Fase de generación de planta

Fase de colocación de sala Fase de colocación de sala

¡Ahora con puertas comunicantes!
¡Ahora con puertas comunicantes!

pek
fuente
11

Dahl y Rinde tienen un documento de tesis sobre Generación procesal de ambientes interiores que utiliza un enfoque de esqueleto y regiones para llenar los interiores de los edificios con habitaciones y pasillos. El documento incluye diagramas de clase para su prototipo. También hay algunas buenas referencias en su bibliografía, incluido el A Pattern Language antes mencionado .

Su trabajo fue diseñado en torno a los siguientes supuestos simplificadores:

  • solo se ocupa de edificios de apartamentos
  • sin niveles divididos
  • limitar la forma de los edificios (envolvente) debe ser poligonal
  • sin agujeros en el sobre
  • grosor de envoltura similar o que cambia linealmente (es decir, sin formas de reloj de arena)
  • solo se ocupa de edificios que necesitan pasillos

Aquí hay una breve descripción de su proceso:

  • Encuentra el esqueleto para el sobre. Luego, los corredores se colocan a lo largo del esqueleto en función de la distancia desde la envoltura, la proximidad a las puertas o escaleras y la proximidad a los corredores previamente ubicados.
  • A continuación, el espacio restante sin corredor se divide en áreas conectadas máximas, cada una con un único límite continuo. En algunos casos, esto requerirá la inserción de una pared.
  • Estas regiones se dividen en apartamentos que intentan asignar al menos una ventana por apartamento. En algunos casos, las divisiones más pequeñas se fusionarán para evitar apartamentos demasiado pequeños. Las regiones sin ventanas simplemente se ignoran.
  • Finalmente, los apartamentos se dividen en habitaciones utilizando un diagrama ponderado tipo Voronoi como base de la siguiente manera:

    • Los pesos de las semillas se utilizan para influir en el tamaño de la habitación. Se agregan semillas en las puertas y ventanas. Se agregan semillas adicionales, generalmente una por habitación deseada; Si bien no se indica explícitamente, parece que las semillas se colocan a lo largo de las paredes exteriores del apartamento.
    • Comenzando con el punto más lejano, se calcula una línea entre la semilla dada y todos los demás puntos y luego se biseca una distancia relativa a los pesos respectivos de los puntos finales (por ejemplo, si A y B tenían pesos de 1 y 4, el punto de bisección sería 1/4 del camino de A a B). La colección de líneas bisectantes, junto con la pared exterior, forman la celda para la semilla.
    • A continuación, se crea un esqueleto de pared S-Space (según Peponis et al 1997) al dividir el área con líneas originadas perpendicularmente desde los puntos medios entre pares vecinos de características de la pared exterior (ventanas o puertas).
    • Finalmente, las paredes se seleccionan del esqueleto del espacio S que 'corresponde lo mejor posible a las paredes celulares de Voronoi'.
Pikalek
fuente
3
¿Puedes incluir fotos? Eso seria genial. Leí el papel y las habitaciones que generaron se veían bien desde un punto de vista arquitectónico.
congusbongus
Método muy interesante, tendré que examinarlo más de cerca por si tengo alguna idea que pueda sacar de él.
Draco18s
Vine aquí para relajarme del trabajo ... Sorprende que salga mi tema de investigación. Soy demasiado vago para escribir una respuesta basada en mi propia investigación (todavía solo he diseñado los huesos del algoritmo, así que no vale la pena de todos modos) o describo los enfoques de Danil Nagy para el problema, así que lo dejaré aquí autodeskresearch.com/publications/…
Felipe Gutiérrez