Se terminó el trabajo de programación, gráficos y sonidos en algunos juegos nuevos , solo quedan niveles. Trabajo fácil y agradable, pero por alguna razón viene con gran dificultad. Quizás el efecto de la fatiga general.
Pensando en cómo simplificar su vida, se me ocurrió la idea de la generación procesal. Por supuesto, también tendrá que escribirse, pero como se dijo en un trabajo bien conocido, "es mejor perder un día y luego volar en cinco minutos".
Atencion Debajo del corte hay mucho texto y gifs "gordos".
Introductorio
Los niveles se seguirán puliendo manualmente, por lo que no hay requisitos especiales para la memoria, la velocidad o incluso la calidad de los niveles resultantes.
Inicialmente, planeé que el generador solo arroje habitaciones y puertas, y todo el refinamiento adicional (trama, escenario y enemigos) se llevará a cabo en modo manual. Pero por ahora, creo que el generador puede hacer mucho más. Sin embargo, la sintonización manual seguirá siendo válida: es necesario que los jugadores sientan que se invierte al menos un poco de amor en los niveles.
Miré mi base de conocimientos sobre desarrollo de juegos y escribí enlaces a artículos sobre generación de procedimientos en un documento separado. La mayoría, por supuesto, se trata de generar laberintos clásicos o de generar terreno (por cierto, los resultados son muy impresionantes), lo que no es adecuado para un tirador 3D. Pero algunos estaban cerca de lo que necesitaba (con un asterisco noté los que me parecían más adecuados):
Decidí comenzar con los dos últimos: solo se están implementando y dan buenos resultados.
Estructura del generador
De hecho, no llegué a esta estructura de inmediato, sino en el proceso de numerosas refactorizaciones y reescrituras, pero escribo sobre ello de inmediato para que quede claro lo que está sucediendo:
- Generación de geometría inicial (para elegir, ya sea "BSP" o diseño de sala).
- Limpieza de secciones de basura (secciones que no pueden existir en el juego).
- Construyendo conexiones.
- Borrado de subgráficos de basura (grupos de secciones que están interconectados, pero no hay conexión con las secciones restantes).
- Eliminación de conexiones innecesarias (al construir un árbol de expansión , se proporciona un enlace al árbol de expansión mínimo , porque hay una imagen allí, pero para el generador no hay necesidad del mínimo).
- La aleatorización de las conexiones es la restauración de algunas conexiones remotas (para un tipo de nivel más "humano"), así como la transformación de algunos otros en pasajes entre secciones (que fusiona varias secciones en una forma más compleja).
- Generación de sala secreta.
- Generación de un "escenario" (dónde estarán las secciones inicial y final, y qué camino tendrá que pasar para pasar de la inicial a la final).
- Optimización de conexión.
- Creación de puertas y ventanas.
- La elección de la acción que se realizará en esta sección (presione el interruptor, levante la tecla o encuentre el muro secreto).
Todavía hay alrededor de 12 puntos, pero aún no se han completado (cuando termine, escribiré una publicación separada sobre ellos).
Generación de geometría inicial: "BSP"
Esta traducción fue tomada como la base. No estoy seguro de cuánto sucede en este algoritmo cerca del BSP real, así que escribo "BSP" entre comillas.
El algoritmo es bastante simple. Inicialmente, cree un rectángulo del tamaño de todo el campo de juego:
Luego lo dividimos aleatoriamente en dos partes, ya sea horizontal o verticalmente. Donde tendrá lugar la línea de separación, también elegimos al azar:
Hacemos lo mismo recursivamente para los nuevos rectángulos:
Y una y otra vez, hasta cierto punto:
Luego, en cada rectángulo seleccionamos una "habitación", un rectángulo del mismo tamaño que el original o más pequeño (pero no menos de 3x3, más sobre eso a continuación).
Luego las habitaciones están conectadas por pasillos. Pero no cada uno, sino un poco complicado, porque están almacenados en una estructura tipo "BSP" (consulte el algoritmo original para obtener más detalles).
El corredor que conecta las secciones moradas y blancas.
En el algoritmo original, tanto las habitaciones como los corredores son del mismo color (es decir, son equivalentes), por lo que los corredores simplemente se dibujan en la parte superior de las habitaciones. En mi caso, las habitaciones originales deben conservarse, de modo que los pasillos se dibujen como "detrás" de las habitaciones.
Además, si la habitación (turquesa en la figura) cruza el corredor, entonces debe dividirla en dos secciones diferentes (por lo tanto, el mismo corredor se puede dibujar en diferentes colores):
Y aquí está el resultado:
Luego comienza la fase de marcar celdas de basura:
Como ya escribí, ningún sector puede ser más pequeño que las celdas 3x3. Esto se debe al hecho de que el sector debe estar rodeado de paredes (al menos 1 celda en cada lado) y debe tener al menos una celda de espacio libre:
Por lo tanto, todas esas celdas que no se ajustan a esta regla están etiquetadas. Pero tómalo y no podrás eliminarlos: desaparecen tantas conexiones y el nivel es muy escaso.
En cambio, para cada celda etiquetada, se busca el sector al que se puede unir (observando la regla 3x3):
Si la celda aún no se puede atribuir a ningún sector, se eliminará (pero no en este caso, todo está bien aquí).
En la última etapa, esta hermosa imagen se vectoriza, y los sectores dibujados se convierten en poliacajas, tales polígonos en los que cada borde es estrictamente vertical u estrictamente horizontal (probablemente haya un nombre más científico):
Generación de geometría inicial: disposición de la sala.
Otro artículo fue tomado como base. Este algoritmo es algo más complicado que el anterior, pero tampoco es ciencia espacial.
Primero, el campo de juego se llena con un cierto valor de detención, y luego se borra al azar un área rectangular:
La etapa de limpieza de un rectángulo aleatorio se lleva a cabo un número más (también aleatorio) de veces, y como resultado, se obtienen los contornos externos del nivel:
En el espacio libre, los puntos de crecimiento de la habitación se dispersan al azar (el tamaño mínimo de la habitación es 3x3):
Comienza la primera etapa de crecimiento de la habitación: para cada habitación se selecciona el lado más grande, que aún puede crecer, y crece en 1 celda (si hay varios lados con la misma longitud, uno aleatorio). Las habitaciones se mueven a su vez para que no haya intersecciones.
Luego las habitaciones se convierten en polyboxes:
Y comienza la segunda etapa de crecimiento: en esta etapa, el lado se puede dividir en varias partes. A diferencia de la primera etapa, no crece una célula a la vez, sino inmediatamente hasta la parada máxima, esto evita la "escalera" en las juntas de las habitaciones. Si después de pasar por todas las habitaciones todavía hay celdas vacías, el ciclo se repite.
El resultado es un espacio completamente lleno:
Luego, los polyboxes se dibujan en forma de ráster y (como en el caso del generador "BSP"), comienza la etapa de marcar celdas "basura":
Y uniéndolos a sectores existentes:
Aquí no fue posible unir todas las celdas; se eliminaron las adicionales.
El resultado se convierte nuevamente en polyboxes:
Limpieza de tramos de basura
A veces surgen secciones dentro de las cuales no se respeta la regla 3x3:
Puede intentar "restaurar" tales secciones, pero fui por el camino más simple y simplemente las eliminé:
Construyendo conexiones
Para cada sección, se buscan sus vecinos, y en los lugares de contacto de dichas secciones, se crean conexiones. Las conexiones se crean en ambos lados: si la sección A está en contacto con la sección B, habrá una conexión de A a B y de B a A. El resultado es un gráfico bidireccional.
Limpieza de subgrafos de basura
A veces, como resultado de la limpieza de secciones de basura, no obtenemos un gráfico, sino varios independientes, como en este ejemplo:
En este caso, el subgrafo se selecciona como el principal, el "área" de las secciones es máximo, y el resto se elimina (el "área" está entre comillas, porque aunque es posible calcular el área real del cuadro de polietileno, simplifiqué la tarea y considero el área del cuadro delimitador) esto está mal, pero es adecuado para un generador).
Eliminar el exceso de compuestos
Si hay un pasaje de cada sector a cada uno con el que está conectado, entonces habrá demasiadas puertas en el nivel, y se sentirá con mayor fuerza que se genera. Por lo tanto, en esta etapa, se eliminan las conexiones en exceso:
Para una mayor aleatorización, no genero un árbol de expansión en el número mínimo de pasadas, sino que elimino un borde aleatorio a la vez (eligiéndolo aleatoriamente de entre todos los posibles en el paso actual).
Aunque, cuando escribo esto, parecía la idea de que sería bastante aleatorio seleccionar el sector inicial y eliminar los bordes, un algoritmo ya más eficiente.
Aleatorización de conexión
En lo sucesivo, las ilustraciones vendrán de otra generación, porque en el anterior hubo un error en el generador, debido a que otras imágenes eran incorrectas.
Pero un nivel en el que no hay una sola conexión superflua tampoco parece muy humano, por lo que se introduce un poco de caos:
- Algunos bordes eliminados se restauran.
- Y algunos se convierten en pasillos.
Además, esas secciones entre las cuales se formaron los pasajes se fusionan en una:
Si le pareció que en esta ilustración reaparecieron las conexiones eliminadas en el paso anterior, le pareció a usted :). Cuando leí el texto, también me pareció así, pero después de mirar cuidadosamente la ilustración anterior, queda claro que todo está bien.
Generación de sala secreta
Los sectores que solo tienen una conexión se seleccionan en el gráfico:
Si hay varios sectores de este tipo, todos se agrupan y se ordenan por "área". Luego, esta matriz se trunca al azar (pero para que al menos un elemento permanezca en ella). Estos sectores se convertirán en salas secretas:
Generación de guiones
Primero, se seleccionan los sectores con el número mínimo de conexiones libres (es decir, los más cercanos al "borde" del gráfico):
En esta ilustración, se selecciona un sector, pero si hubiera más, de todos modos se seleccionaría uno (al azar).
NB. Durante la revisión del artículo, pude llegar a una situación en la que un sector con un número mínimo de conexiones libres no solo no estará al límite, sino que asignarle un script lo llevará a un nivel intransitable. De hecho, puede elegir cualquier sector, pero solo uno, después de lo cual el gráfico no caería en varios subgrafos.
A continuación, seleccione los sectores que están conectados al sector actual y que solo tienen una conexión libre. Ellos, con cierta probabilidad, se utilizarán para continuar el guión. Por ejemplo, si el gráfico fuera el mismo que en la ilustración a continuación, entonces el sector indicado por la pregunta podría incluirse en la lista.
La sala secreta está marcada en gris, las cruces son aquellas conexiones que deberían haberse eliminado en el gráfico original, y el sector de origen es una ventaja.
NB. Durante la revisión del artículo, me pareció que la condición para la presencia de una sola conexión era demasiado estricta, lo mismo que en el paso anterior sería suficiente, de modo que después de eliminar este sector, el gráfico no se rompería.
Luego, el número de script se asigna a esta lista de sectores (solo un número, en esta etapa no significa nada específico), y las conexiones en los bordes de esta lista de sectores están marcadas como cerradas por este script.
En estas ilustraciones, diferentes escenarios tendrán diferentes colores de relleno de sector. No tienen nada que ver con el color del borde del sector (en los próximos pasos se corregirá, pero en este paso es más conveniente para mí).
A continuación, se selecciona el siguiente sector, se compila una lista y esta lista se marca con un nuevo escenario:
Presta atención a los pequeños puntos azules dentro de los cuadrados rojos: así es como se dibuja el abridor de escenarios, es decir En algún lugar dentro de la sección con el guión rojo habrá una tecla o interruptor que abrirá el pasaje a sectores con un guión azul.
Esto continúa hasta que no queden sectores libres:
Al sector más reciente no se le asigna un script, sino solo un abridor de escenarios. Este sector será el sector en el que el jugador comienza el juego.
Para este nivel:
- El jugador comienza en el sector inicial, en algún lugar allí encuentra un "abridor de botellas" para el sector amarillo, va allí.
- En el sector amarillo, abre el sector azul, va allí.
- En el sector azul se abre verde, va allí.
- En el sector verde se abre violeta, se va allí.
- En violeta se abre rojo.
- En rojo - azul.
- Donde encuentra el interruptor de nivel final.
Esquemáticamente, esto se puede mostrar de la siguiente manera:
Un "abridor" puede ser una llave o un interruptor, o algo más, por ejemplo, una tarea para destruir a todos los enemigos en cualquier sector (pero no planeo que en el futuro cercano el generador o el motor lo admitan).
Optimización de conexión
En este paso, para cada conexión se selecciona un lado (como recordará, inicialmente las conexiones se generan en ambas direcciones). Esto es necesario para que el nivel parezca más "manual" y para simplificar los siguientes pasos (pero para un tipo de nivel aún más interesante, en un futuro próximo planeo dar un paso para "des-optimizar" algunas conexiones) .
Creando puertas y ventanas
Para cada sector, se ven todas sus conexiones (que después del paso anterior se ven solo en una dirección), y se colocan puertas y ventanas en cada conexión vista.
- Primero, se selecciona un punto en la unión, preferiblemente más cerca del centro.
- Luego, en este punto, se coloca una puerta o una ventana (y si es una conexión a una habitación secreta, entonces un muro secreto).
- Si se coloca una puerta, puede tener un tamaño de 1 a 3 celdas (una es una puerta normal, dos o tres son una puerta hermética gruesa, que se abre después de presionar un interruptor).
- Además, la conexión se divide en dos partes: la parte anterior al punto seleccionado y la parte posterior. Y, si queda espacio antes o después, la función se llama recursivamente.
Para que el nivel se vea más interesante, en diferentes pasos hay una probabilidad diferente de colocar una puerta o ventana:
- En el primer paso, la puerta siempre se coloca, de qué sirve conectarse si solo hay ventanas allí.
- En el segundo paso, con una mayor probabilidad (75%), se coloca una ventana que una puerta.
- Si hay un tercer paso (por ejemplo, la conexión es larga), entonces se debe colocar una ventana.
- En el caso del cuarto paso, la puerta o ventana se coloca igualmente probable.
- Si la conexión es extra larga, el generador vuelve al segundo paso.
Selección de acción
Aunque esto no está relacionado con la generación, la visualización cambia en este paso: ahora el borde del sector está pintado en el color del guión:
El sector inicial es gris claro, el sector final es azul. También tenga en cuenta que en lugar de la puerta de la habitación secreta (gris oscuro a la izquierda) se dibuja una pared: todo es correcto, esta es una pared secreta.
A continuación, seleccione los sectores en los que puede colocar las claves:
Se seleccionan simplemente:
- Si esta es una habitación secreta, entonces no puede haber un "abridor" y la llave no puede colocarse allí.
- Tampoco puede colocar la clave en el sector final, porque es final.
- Además, la llave no puede abrir puertas dobles y triples: debido a las características del motor, solo se pueden abrir con el interruptor (no hay tales sectores en la ilustración anterior) .
Después de eso, se selecciona aleatoriamente el número de teclas en un nivel (de cero a tres) y luego, aleatoriamente, de la lista de sectores disponibles, se seleccionan aquellas en las que se seleccionarán las teclas.
En los sectores restantes habrá interruptores.