Generación Procedural I: Calabozos y Cavernas

La intención de este post es desmitificar un poco sobre la generación procedural, una de las materias que mas me apasionan sobre desarrollo de videojuegos. El mito mas conocido de la generación procedural es que es algo complejo y requiere muchísimo código.

La verdad es que puede llegar a ser complejo, pero si está bien diseñado, esa complejidad se puede distribuir en capas, permitiendo mucha mantenibilidad y escalabilidad a la generación procedural. Al distribuir nuestra lógica en capas, nos centramos en un solo nivel de la generación a la vez, esto nos ayuda a reducir la dificultad en general de la implementación.

El otro mito de la generación procedural es que un súper script o una súper clase es el efecto colateral del resultado. Pero en realidad si nos ponemos a pensar en el concepto en sí, la palabra “procedural” denota que hay un procedimiento, y casi todo paradigma de programación propone que los procedimientos pueden ser recursivos. A grandes rasgos, esto significa que podemos construir nuestro código para que no quede todo centralizado en una clase.

A lo largo de este post vamos a ver que podemos usar un mismo algoritmo, que a su vez es muy simple, para crear:

  • Calabozos bidimensionales

 

dungeonGen

  • Calabozos de varios pisos

dungeon Gen3d

  • Sistemas de cavernas

CavernGen

Trabajando con prefabs

En la introducción del post, mencione que una gran componente de la generación procedural es separar la lógica en capas y el uso de la recursividad. Para aplicar esto a unity podemos usar las Prefabs. La idea general de esta generación no es tener un game object que genera todas las partes, sino que cada game object sepa generar sus anexos. Esta propuesta desplaza el protagonismo del nivel hacia las secciones, nuestra generación va a ser un producto de la combinación de cada sección definiendo la próxima, con la ayuda del nivel para actuar como limitante de dicha generación.

Si todo esto suena confuso, es tan fácil como especificar las reglas de nuestra generación:

  • La entidad de nivel (calabozo, caverna, laberinto, etc) ubica la primera sección
  • Cada sección tiene una entrada y puede o no tener salidas
  • Cada sección crea las secciones anexas en sus salidas
  • La entidad de nivel conoce todas las secciones creadas

Para el ejemplo de este post en particular trabajaremos con dos tipos de secciones, cámaras y corredores, y agregaremos una regla más:

  • Cada cámara crea tantos corredores como tenga salidas
  • Cada corredor crea tantas cámaras como tenga salidas
chamberBuild
Ejemplo de una sección de tipo cámara con una salida (diamante rojo)

exits

Ejemplo de una cámara con 4 salidas

 

Aplicando las reglas en código

Teniendo en cuenta las reglas, vamos a necesitar definir por lo menos 3 tipos de scripts, estos van a ser Corridor, Chamber y Level. Comencemos con Level, por ahora el nivel se va a encargar de tener el repositorio de prefabs, crear la primer Chamber, exponer una función para el registro de cada sección y de alguna manera limitar la generación infinita.

Por mas que nuestro nivel no se encargue de crear cada sección, puede ayudar a limitar el tamaño del mismo exponiendo una variable para limitar.

Screenshot 2018-10-17_13-56-54
El script de level, contiene las listas de prefabs de chambers y corridors, una lista interna de las secciones construidas y el número máximo de secciones a construir.

2018-10-16 21_24_41-Window

2018-10-16 21_25_37-Window
Las clases de Chamber y Corridor serán nuestras secciones, al crearse, automáticamente se asignan como hijos de Level, se registran como secciones del nivel y generan sus anexos.

Si seguimos el flujo del código, notamos que el nivel crea la primera sección y luego cada sección genera las próximas de manera expansiva, con la limitante del tamaño del nivel.

Screenshot 2018-10-17_13-59-32
Nuestro nivel, un GameObject vacío con el comportamiento de Level y las prefabs cargadas.
Screenshot 2018-10-17_13-59-01
Nuestra prefab de cámara básica con la salida especificada.

¿Por qué las salidas son Transform y no Vector3?

Las salidas no solo denotan la posición de la próxima sección sino también su rotación, cuando nosotros instanciamos una prefab en unity, uno de los overloads del método Instantiate recibe la prefab y una transform. Este overload especifico de Instantiate hace que el objeto creado sea hijo de dicha transform, obligándole a que herede posición, escala y rotación.

Ampliando las reglas del generador

Como podemos notar, hay un problema con nuestra generación, las secciones se pisan unas a las otras porque no estamos limitándolo.

Screenshot 2018-10-17_13-57-59
Ejemplo del calabozo generado y el problema que produce.

Para tratar este problema vamos a agregar una nueva regla:

  • Una sección no puede sobreponerse a otra que ya existía, en caso de que eso suceda, eliminar la sección recién creada.

Unity nos proporciona varias herramientas para manejar colisiones o mas bien, detección de posicionamiento entre objetos, algunos que ya se han cubierto en este sitio como:

  • Mensajes de OnCollisionEnter, OnTriggerEnter, OnCollisionStay, etc… son muy conocidos, pero tienen un par de problemas, no ocurren on demand, sino que están constantemente detectando, y segundo son dependientes de Rigidbody.
  • Raycast, también muy útiles, pueden ser usados on demand o constantemente, son eficientes y muy útiles cuando queremos saber si existe algo hacia alguna dirección, pero si los queremos usar para detectar si un cuerpo está adentro de otro, o intersectando, es mas complicado.

En 3er lugar, encontramos nuestra aplicación para este caso, y esa es collider.bounds.Intersects(Bounds bounds). Esta función nos va a devolver si dos colliders están en intersección. La gran ventaja de esto es que nos permite chequear on demand si una nueva sección esta encima de otra ya existente. Por supuesto, para implementar esto necesitamos tener conocimiento de todas las secciones, y de eso se encarga la clase Level. Así que agregaremos a Level, una función booleana para saber si nuestra nueva sección cumple la nueva regla.

 

2018-10-18 19_11_02-Window
Nuestra nueva función para reforzar la regla de no-intersección, la función recibe el collider de la nueva sección y el collider de la sección que lo creo, ya que este último debería ser ignorado de la validación. También vemos la nueva función de registrar sección, recibimos el collider de los límites de la sección en vez del objeto en sí.

La razón por la cual dejamos de recibir un GameObject como parámetro de RegisterNewSection es porque no sabemos qué tipo de sección puede ser, por lo pronto usaremos el Collider, pero más adelante veremos que con uso de interfaces mejoraremos esto. De esta manera nuestra colección de secciones registradas la vamos a definir como private List<Collider> registeredColliders = new List<Collider>();

2018-10-18 19_15_57-Window
Por ultimo a nivel de nuestras secciones, vamos a aplicar esta regla llamando al nivel y consultando la validez de esta nueva sección.

Con esta última regla aplicada, nuestro calabozo se va a construir sin intersecciones.

Mejorando nuestro Código

Bien, ahora que tenemos la generación funcionando como queremos, trabajemos un poco en mejorar nuestro código. Primero que nada, intentemos sacar el uso de GetComponentInParent<>(). No es que no sea bueno usarlo, pero puede generar problemas de referencia nula. En cambio, usemos un concepto de desarrollo de software llamado Inyección de Dependencia, se trata de definir constructores de una clase de manera que reciban por parámetro todo lo necesario para existir, imponiendo que no se pueda crear una instancia de la misma sin lo que necesita para operar. Como en unity no usamos new de los MonoBehaviors, tenemos que aplicarlo de una manera alternativa. Un uso bastante popular es el de incluir un método Initialize() que reciba todo lo necesario, y sabemos que en seguida después del Instantiate de unity vamos a llamar al método Initialize del componente que queramos inicializar.

2018-10-18 19_32_03-Window
En este caso Initialize reemplazaría al método estándar de Unity, Start.

Aplicando esto, ya no buscamos referencias en los padres de nuestras secciones, sino que la referencia del nivel es pasada de una sección a otra.

El pase de diapositivas requiere JavaScript.

prefab

Finalmente, podemos hablar sobre interfaces y como mejorar mas nuestra arquitectura para eliminar la redundancia de código entre corredor y cámara. Podemos atacar la arquitectura de dos maneras:

  • Interfaz

Podemos crear una interfaz de sección con todo lo referente a lo que tienen en común cámara y corredor, y finalmente en Level mantener un registro de secciones como una lista de dicha interfaz

  • Clase

Podemos unir ambas clases en una única clase de sección, y especificar a nivel de editor de que tipo es dicha sección y que tipo de secciones puede generar, esto a la misma vez logra que en nuestra clase de Level tengamos solo una lista de prefabs.

 

2 comentarios sobre “Generación Procedural I: Calabozos y Cavernas

  1. Muy interesante el post! Voy a tratar de aplicarlo.

    Sobre la mejora del código, puede estár bueno abstraer chamber y corridor en una clase base como comentás, con el agregado de un template method para GenerateNeighbor (en vez de GenerateCorridor y GenerateChamber). Asi a nivel de editor sólo habría que especificar de que tipo concreto es la sección.

    Me gusta

    1. Perfecto si, la tercer opcion es lanzar en comportamiento compartido a una clase base y virtualizar el metodo de generar a los anexos. Usualmente es mejor practica trabajar con interfaces que con herencia porque asi se le da versatilidad total a la implementacion estricta.
      La eleccion entre clase o interfaz esta mas bien dada por el contexto en el que hagamos nuestro codigo, si es para construir un asset de la store tiene que ser lo mas versatil posible, para esto, la mejor opcion es interfaz. Si va a ser para una implementacion interna, clase padre esta mas que bien.

      Saludos y gracias por leer!

      Me gusta

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google photo

Estás comentando usando tu cuenta de Google. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s