Generando procesalmente un edificio de área específica

15

Yo y un equipo estamos trabajando en un juego de construcción de fábricas que le da al jugador una fábrica aleatoria al comienzo del juego. Para tratar de asegurarse de que haya una sensación de "justicia", idealmente la fábrica generada al azar tendría un área dentro de unas pocas unidades de (valor de marcador de posición) 30.

Es relativamente sencillo escribir un generador de rectángulo aleatorio básico para cumplir con estas especificaciones, pero nuestro objetivo es que la fábrica sea más compleja, quizás compuesta de 2, 3 o incluso 4 rectángulos que se crucen, produciendo formas más complejas (piense en L, Edificios en forma de U y O).

Intenté generar un rectángulo aleatorio y luego usar álgebra básica para completar un segundo rectángulo, pero hasta ahora no he tenido suerte al implementar más de 2 rectángulos, e incluso entonces no estoy satisfecho con los resultados de solo un diseño de 2 rectángulos. .

Información más relevante: 2D de arriba hacia abajo Algunas de las mecánicas son de estilo factorio, por lo que las habitaciones deben tener una longitud y un ancho razonables para dejar espacio para maquinaria Actualmente en Java y Lua (puede usar bibliotecas integradas de cualquiera de las dos si es necesario)

¡Gracias por adelantado!

EDITAR: Cuando digo salidas "buenas" o "malas", una salida mala sería cualquier salida que tenga espacio inutilizable por el jugador. La forma de fábrica limita dónde el jugador puede colocar máquinas de fábrica, como cintas transportadoras. Idealmente, la fábrica no debería tener áreas que tengan solo 1-2 bloques de ancho, la forma no debería ser uno o dos rectángulos grandes con una línea de 1-2 bloques "colgando" a un lado. Un buen resultado sería donde todo el espacio del piso es "viable", por lo que todas las áreas tienen al menos 3-4 bloques de ancho. Un buen resultado no siempre tiene que ser complejo (1 o 2 rectángulos está bien), pero debe tener una buena posibilidad si se compone de más de 1-2 rectángulos.

usuario2129189
fuente

Respuestas:

7

Podrías usar pregenerado polyominoes pregenerados como metaformas para construir una variedad de edificios.

Digamos que su distancia mínima aceptable es de 3 bloques. Entonces, la unidad de construcción aceptable más pequeña que consideraremos es 3x3. Por conveniencia, voy a llamar a eso un celular y da un área de 9 bloques. Luego, tome su área de inicio objetivo y divídala por el área de la celda. Usando el valor inicial que dio, obtenemos 3.333; entonces 3 celdas te darían un poco menos de lo que deseas y 4 celdas te darían más.

Desde aquí tienes un par de opciones. Si es flexible en su área de inicio, use el método que funcione mejor para elegir el número de celdas que le da una cantidad aceptable (es decir, redondee al valor más cercano, redondee, etc.). Voy a llamar a esto el recuento celular.

A continuación, seleccione al azar el poliomino con el recuento de células deseado. Reemplace cada cuadrado en el polyomino con una celda de construcción y tendrá su forma final.

Para ilustrar, digamos que elegimos redondear hacia abajo. Aquí están todos los poliominoes de tamaño 3 (sin incluir rotaciones / volteos):

ingrese la descripción de la imagen aquí

Supongamos que elegimos al azar la forma de L y aplicamos una rotación aleatoria, su edificio tendría el siguiente diseño:

ingrese la descripción de la imagen aquí

Un par de problemas Primero, hay un límite en la cantidad de celdas que puede usar. Wikipedia te dará todos los poliominós hasta el tamaño 8 ( octomino ). Incluye datos de resumen para hasta el tamaño 12, pero no sé si hay una lista en línea para todos ellos. En segundo lugar, la solución anterior solo funciona exactamente para tamaños de edificios que son múltiplos de 9. Hay algunas maneras de solucionar algunos de estos problemas:

1) Use un tamaño de celda diferente. Por ejemplo 3x4, 4x4, etc.

2) Agregue células adicionales a un poliomino inicial. Esto puede ser complicado si debe asegurarse de que todas las formas sean igualmente probables, pero es probable que para la mayoría de los propósitos de desarrollo del juego no necesite una distribución verdaderamente uniforme de las formas de construcción.

3) Rellene un edificio para hacerlo más grande. Volviendo al ejemplo, si usó 3 celdas, su edificio tendría un área de 27 cuadrados que lo dejaría corto por 3. Luego, podría escanear el perímetro en busca de una ubicación para pegar un grupo de cuadrados de tamaño 1x3. Siempre que su grupo de maquillaje sea al menos AxB donde A sea al menos su distancia mínima aceptable, su resultado no violará su restricción de distancia mínima aceptable. A partir del ejemplo anterior, aquí hay una ilustración de un posible resultado:

ingrese la descripción de la imagen aquí

4) En lugar de rellenar un edificio que es demasiado pequeño, puede recortar un edificio que es demasiado grande. Asegurarse de que se siga su restricción de distancia mínima aceptable es más complejo que la opción de relleno, pero le daría más alternativas para considerar.

Algunos otros comentarios:

El hecho de que pueda usar todos los poliominós posibles de un tamaño determinado no significa que deba hacerlo. Si algunos de ellos no son divertidos, rompa su tema, sean ofensivos para su audiencia (patrones de esvástica) o causen algún otro problema, elimínelos. Además, podría ponderar su rutina de selección si algunos patrones son interesantes, pero demasiado extraños para aparecer de forma rutinaria. Finalmente, podría usar esta solución en combinación con su estrategia actual. Tal vez el 70% del tiempo genera edificios rectangulares y el 30% del tiempo utiliza el enfoque poliomino. O tal vez comience con un edificio rectangular y pegue un pequeño poliomino al exterior.

Pikalek
fuente
16

Una manera simple de construir un generador de procedimientos es:

  1. Construye cosas al azar
  2. Ejecute una función que verifique si la salida es buena
  3. Si el resultado no es bueno, vaya al paso 1

Incluso si toma miles de ejecuciones en completarse, la mayoría de los generadores simples funcionan bien con este enfoque. La ventaja es que no se requiere mucha inteligencia en el generador, y dado que verificar si algo es bueno es mucho más fácil que construir algo que sea bueno el 100% del tiempo, este enfoque es muy fácil.

Ha enumerado algunas medidas objetivas sobre si un resultado es bueno; eso debería ser suficiente para crear un generador rápido y sucio. Coloque rectángulos al azar dentro de un área y rechace la salida si, por ejemplo, hay áreas que tienen solo 1-2 bloques de ancho.

Comience con eso, mejore y optimice después.

congusbongus
fuente
¡Gracias! Recuerdo haberlo considerado, pero la idea de que hubiera una posibilidad de varios segundos de carga + me detuvo. Ahora me doy cuenta de lo increíblemente pequeña que es esa posibilidad. Tendré que probar eso, pero podría esperar para ver si alguien tiene una solución más directa primero.
user2129189
@ user2129189 Cuando puso en marcha su generador, aún puede ajustar sus rangos de números aleatorios para evitar generar diseños que es poco probable que pasen la prueba. También es posible paralelizar este algoritmo de generación de prueba y error en múltiples núcleos haciendo que cada núcleo genere un diseño a la vez.
Philipp
3
Yo no soy fanático de los métodos de generación de rechazo y reintento. Son lo suficientemente rápidos cuando su generador está haciendo solo una cosa simple, pero para los niveles de juego generalmente comenzamos a superponer más características y pasos de generación para hacer mapas más ricos. En ese punto, la probabilidad de golpear un mapa viable es el producto de la probabilidad de que cada paso tenga éxito, que puede reducirse rápidamente. Esto no es solo una preocupación académica: he hablado con desarrolladores que tuvieron que implementar un sistema de almacenamiento en caché de semillas bueno / malo para evitar tiempos de generación excesivos, cuando un generador de paso único correcto por construcción hubiera sido más fácil.
DMGregory
@DMGregory, sí, definitivamente puedo ver eso. Un generador aleatorio básico funcionaría como el 99% del tiempo en unos pocos pases para mi caso, pero si quiero agregar más complejidad más adelante, podría disminuir significativamente. ¿Alguien sabe de alguna aplicación de programación / juego de la vida real del modelo de conjetura y verificación?
user2129189
Tal vez pueda haber niveles y funciones de generaciones y comprobaciones, teniendo cuidado de hacer coincidir la formulación de las condiciones con el nivel actual de generación. De esta forma, no es necesario volver a generar todo el nivel solo a partir del error encontrado al colocar un elemento de forma ligeramente incorrecta.
Pysis
7

Dada una restricción de "todas las áreas tienen al menos 3-4 bloques de ancho", la primera idea que se me ocurre es algo como lo siguiente:

  1. elige uno de 3x3, 3x4, 4x3 o 4x4
  2. colocar un bloque de ese tamaño en el centro de la cuadrícula
  3. elegir una dirección (arriba, izquierda, derecha, abajo)
  4. intente colocar un bloque de 3x3 junto a los bloques previamente colocados en esa dirección
  5. Si tiene éxito, con cierta probabilidad, intente expandir el bloque a un bloque de 4x3 en una de las direcciones que no eligió
  6. con cierta probabilidad, mueva un borde aleatorio de los bloques rellenados
  7. repita los pasos 3 a 6 hasta que el área sea lo suficientemente grande

La idea básica es que, dado que desea que todas las áreas tengan al menos un tamaño determinado, solo trabaje en áreas que tengan ese tamaño. En términos más generales, si desea que algo sea cierto para todas las salidas generadas, vea si puede hacerse realidad para todas las salidas parcialmente generadas.

Ryan1729
fuente
44
Simplificaría las cosas siempre comenzando desde un bloque de 3x3, luego agregando bloques de 3x1 en posiciones aleatorias donde cada cuadrado es adyacente a uno existente. Agregando a un bloque 3x3, hay cuatro posiciones posibles. Todos te dan un bloque de 3x4, con seis posibles posiciones para el siguiente. A partir de ahí se vuelve más complicado, pero no tan malo.
JollyJoker
0

Considere usar booleanos NOT y UNION y elegir entre ellos al azar.

  1. Coloca un rectángulo al azar.
  2. Coloca un segundo rectángulo aleatorio.
  3. Elija aleatoriamente si UNIRlos o RESTAR el segundo del primero.
  4. Repita para varios rectángulos. Aunque, solo dos o tres podrían dar resultados lo suficientemente razonables.

Luego, calcularía el área y la escalaría hacia arriba o hacia abajo para que coincida más estrechamente con el tamaño aproximado que busca, y luego probaría que no hay dimensiones inferiores a la cantidad mínima requerida.

Pulpo
fuente
Su idea de escala para obtener el área deseada es realmente inteligente y silenciosa. Podría implementar algo silencioso un poco como esto.
user2129189