Visión, luces y sombras – Shadowcasting mejorado

¡Ohp!, bienvenidos a esta primera entrada de una nueva sección experimental: desarrollo.

Soy Uexkull, el diseñador/administrador de este ñordo de web (puedo decirlo, total, no me pagan). He querido plasmar, liberar, compartir por aquí algunas de mis aportaciones personales a ese mundillo llamado “diseño y desarrollo de videojuegos”.

Quiero que esta sección sea un tanto amena y, si bien está orientada especialmente a desarrolladores de videojuegos, no veréis ningún código de ningún lenguaje de programación en ninguno de mis algoritmos, puede que ni pseucódigo. El objetivo es que “cualquiera” pueda leerlo, entenderlo y aplicarlo de la forma que quiera en el lenguaje que quiera.

Un poco de contexto

En el desarrollo de videojuegos, especialmente en mis favoritos (los roguelike), la línea de visión o el campo de visión (Line of Sight, Field of View, LOS, FOV), es una de las mecánicas que más recursos puede llegar a utilizar.

El “qué puede ver un personaje” o “qué puede iluminar cierta luz” son prácticamente sinónimos en muchos juegos, pues en la implementación pueden utilizarse los mismos algoritmos para ambas tareas. Nos centraremos en el contexto 2D de un emisor de luz, que creo que es el que más podría complicarse de haber alguna diferencia.

La primera predisposición casi natural es visualizar las líneas de visión o de luz como líneas propiamente dichas, de ahí surgen las famosas y simples (pero costosas) técnicas de Raycasting o emisión de rayos, veamos o repasemos en qué consisten.

Raycasting, ventajas y desventajas

Los algoritmos estándar de raycasting se fundamentan en la emisión de rayos en todas las direcciones desde el emisor de luz. Cada rayo avanzará definiendo como iluminada cada sección que atraviese (celdas, píxeles, etc, depende del juego) hasta chocar contra un obstáculo (una pared o cualquier cosa que no permita el paso de luz). Básicamente simula una luz real, pero tiene enormes desventajas.

Área iluminada por raycasting

Figura 1. Iluminación mediante raycasting. La celda amarilla del centro representa un emisor de luz. Las celdas azules son las iluminadas al tener contacto con un rayo. Las celdas grises son celdas no iluminadas. Se generan 36 rayos, uno cada 10 grados sexagesimales.

Un rayo no es más que un bucle que irá recorriendo cada casilla por la que en teoría debe pasar. En base al ángulo del rayo no es difícil obtener un vector dirección normalizado que nos indique los incrementos de X e Y en cada iteración. Sabremos que estamos en una nueva casilla al ver que varía la parte entera de la coordenada. Para un efecto radial es importante que todos los rayos tengan la misma longitud (el radio).

Observemos cómo actúa esta técnica básica con un obstáculo en medio.

Iluminación con técnica de raycasting con obstáculo en medio

Figura 2. Mismo ejemplo ahora con dos bloques lilas que hacen de obstáculo a la luz. Vemos cómo evitan que se iluminen ciertas casillas, simulando una sombra.

Uno de los problemas que ya podemos observar es la cantidad de rayos que hay que emitir, y veremos por qué el número de rayos suele ser muy superior al ejemplo dado. Supongamos que queremos ampliar el alcance de la luz, ampliar el número de celdas que los rayos alcanzan pero manteniendo la misma cantidad de rayos. Aquí el resultado:

Iluminación con técnica de raycasting. Se requieren más rayos entre más aumenta la distancia.

Figura 3. Raycasting con 36 rayos de largo alcance. Se aprecian celdas entre los rayos que no son cubiertas.

El problema es evidente, y la solución es un sumidero de tiempo de ejecución. Al ampliarse el radio, la distancia entre dos rayos en la lejanía termina siendo muy superior al tamaño de una celda y por tanto, se producen áreas no cubiertas por los mismos aunque se encuentren en el radio de iluminación. La solución más intuitiva es aumentar la cantidad de rayos y lo ideal sería hacerlo en base al radio deseado. Para un radio como este quizás sea mejor duplicar el número de rayos (uno cada 5 grados sexagesimales, haciendo un total de 72). Por lo general se suele trabajar con cifras múltiplos de 360, como 720 o 1440, lo que parece una animalada. En un entorno 3D esta cifra es mucho mayor.

Sin embargo, veremos que más rayos no solo evitan este problema, también mejora el realismo de las luces. Al haber rayos más cerca de las esquinas de los obstáculos, se iluminan celdas que muchas veces quedan ensombrecidas por los mismos erróneamente.

El principal problema de este algoritmo es la redundancia. Una celda puede ser visitada múltiples veces por rayos distintos ya habiendo sido iluminada. El coste computacional está más relacionado con el número de rayos y la distancia de los mismos que con el número de celdas en sí.

En un escenario con múltiples emisores de luz y una cantidad de rayos por emisor “normal” (entre 360 y 1440), la cantidad de operaciones que deben realizarse para calcular la iluminación es simplemente brutal. En juegos en tiempo real donde se calcula la iluminación en cada fotograma esto es una auténtica locura. Aún así, con los ordenadores de hoy en día, incluso móviles o tablets no precisamente de última generación, esta bestialidad de técnica tira perfectamente siempre que no se abuse.

Una alternativa más elegante: el shadowcasting

El raycasting tiene muchísimas variantes e implementaciones mejoradas que disminuyen los tiempos de ejecución a números insignificantes en relación al algoritmo anteriormente expuesto. Sin embargo, su fundamentación es la misma y sus problemas suelen ser similares.

El shadowcasting o proyección de sombras comprueba la iluminación de una forma completamente distinta al raycasting. Para definir si una celda está iluminada se comprueba que no exista obstáculo entre la misma y el emisor de luz. La principal diferencia es que aquí no hay rayos, sino que se comprueba manualmente específicamente las celdas en el radio de iluminación.

Los algoritmos de shadowcasting evitan que se escapen celdas y no pasan demasiadas veces por la misma celda. Muchos de los algoritmos suelen centrarse en encontrar objetos que proyecten sombras y en evitar pasar por las celdas que abarca dicha sombra (de ahí su nombre). El coste computacional ahora sí irá en relación al número de celdas a comprobar, disminuyendo drásticamente los tiempos de ejecución en comparación a un raycasting estándar.

Nuestro algoritmo: shadowcasting recursivo

Aunque este algoritmo lo desarrollé hace unos años, pero Björn Bergström ya lo había hecho antes, en 2001. Y aunque sus implementaciones se alejan un poquito de la mía y contienen algunos errores, publicó una explicación en Roguebasin en la que posteriormente colaboramos yo y otros compañeros con correcciones e implementaciones. Es hora de quitarle el polvo a dicho material, traducirlo y exponerlo por aquí.

Mecánica del shadowcasting general

El shadowcasting, como ya se ha descrito anteriormente, visita las celdas del área a iluminar una por una, incluso muchos algoritmos de shadowcasting se ahorran pasar por muchas celdas cuando se conoce un obstáculo que las oculta (como es el caso de nuestro algoritmo). Por lo general se escanea fila a fila o columna a columna, o con una combinación de ambas.

En nuestro algoritmo (y en muchos otros), se divide el área en 8 cuadrantes. Dichos cuadrantes comparten siempre una línea de celdas con sus adyacentes. A partir de ahora usaremos simple ASCII para describir escenarios, además de más cómodo y rápido, nos envuelve en un ambiente roguelike siempre tan querido.


            Línea compartida
               por 
Línea          1 y 2      Línea compartida
compartida\      |      / por
por 1 y 8  \     |     / 2 y 3
            \1111|2222/
            8\111|222/3
            88\11|22/33
            888\1|2/333
Línea       8888\|/3333  Línea compartida
compartida ------@------- por 3 y 4
por 7 y 8   7777/|\4444  
            777/6|5\444
            77/66|55\44
            7/666|555\4
            /6666|5555\
   Línea   /     |     \  Línea compartida
compartida/      |      \ por 4 y 5
por 6 y 7      Línea     
             compartida por 
             5 y 6

Figura 4. Los 8 cuadrantes en los que se divide el área a iluminar.

Los cuadrantes 1 y 6 se analizarán fila a fila de izquierda a derecha.
Los cuadrantes 2 y 5 se analizarán fila a fila de derecha a izquierda.
Los cuadrantes 3 y 8 se analizarán columna a columna de arriba a abajo.
Los cuadrantes 4 y 7 se analizarán columna a columna de abajo a arriba.

El algoritmo en sí

Utilizaremos los elaborados ejemplos y explicaciones puestos en roguebasin para este fantástico algoritmo sobre un cuadrante (el 1).


 ................. 16  @ = Emisor
  ......###....... 15  # = Celda bloqueante.
   .....###....... 14  . = Celda no bloqueada.
    ....###..#..## 13 
     ...##........ 12
      ............ 11
       ........... 10
        .......... 9
         ......... 8
          ........ 7
           ....... 6
            ...... 5
             ..... 4
              .... 3
               ... 2
                .. 1
                 @

Figura 5. El primero de los 8 cuadrantes, que se escaneará de izquierda a derecha empezando por la primera fila (la 1).

Nuestro algoritmo comenzará escaneando la primera línea (la 1) de izquierda a derecha. Cuando alcance la última celda (la celda más a la derecha), y si esta no era una celda bloqueante, comenzará a escanear la siguiente fila. La “chicha” del asunto llegará al encontrar una celda bloqueante por la línea 12. A medida que pasa por las celdas las irá marcando como iluminada.

Antes de continuar, tendremos que conocer el concepto de pendiente normalizada de la recta entre dos puntos y cómo calcularla. Es algo muy simple.

La pendiente inversa normalizada es la pendiente entre dos puntos que va entre 0 (vertical total) y 1 (diagonal perfecta). Realmente es la inversa de la pendiente. En algún momento tendremos que obtener la pendiente de la línea que va desde la celda en la que estamos hasta el origen. Para este caso es muy simple de calcular:

(x1 – x2) / (y1 – y2)

Sin embargo, es una complicación innecesaria como explicaré más adelante. De momento, nos basta saber que la celda de más a la izquierda de cualquier fila está justamente formando una diagonal perfecta con el emisor, es decir, su pendientes es exactamente 1. Por ejemplo, en la fila 12, si suponemos que la coordenada del emisor es 25,30, tendremos que la celda más a la izquierda del cuadrante a analizar está en 13,18. Aplicando la innecesaria fórmula tenemos:

25-13 / 30-18 = 12 / 12 = 1.

Explicación de la “complicación” del señor Bergström: en realidad, no es algo que este señor aplicara en su implementación y sólo lo introdujo para visualizar mejor el concepto de la pendiente. Pero la cosa es aún más simple. La celda de más a la izquierda siempre dará 1 porque coincide que su posición en la fila está tan alejada de la componente X como de la Y. Es decir, en el caso anterior, la celda de más a la izquierda de la fila 12 está precisamente 12 celdas a la izquierda. Conociendo el número de fila y la celda podemos obtener directamente la pendiente normalizada que no es más que un factor de lejanía con el eje vertical.

Siguiendo el ejemplo anterior, para la fila 12, la celda que forma una diagonal es la que está 12 celdas más allá (12/12 = 1). La celda que está en mitad de la fila, debería dar por tanto 0.5 de pendiente inversa, y efectivamente, ya que está a 6 unidades en el eje X del origen (6/12 = 0.5). Finalmente, la celda más a la derecha debería dar 0 de pendiente (0/12 = 0), ya que es vertical total con el origen.

En pocas palabras, la fórmula se reduce a una simple división:

posición de la celda en la fila / número de fila

Explicado esto, podríamos decir de otra forma que en realidad el escaneo de una fila termina cuando se alcanza la pendiente tope, en este caso 0. Hay una razón para verlo de esa manera que pronto descubriremos.

Veamos cómo tratar las celdas bloqueantes:


 ................. 16  X = Primera celda bloqueante escaneada.
  ......###....... 15  # = Celda bloqueante.
   .....###....... 14  . = Celda no bloqueada.
    ....###..#..## 13 
     ...X#........ 12

Una vez en la línea 12, escaneando de izquierda a derecha el algoritmo se topa con la primera celda bloqueante (señalada con una X en el diagrama ASCII). En este momento analizaremos la pendiente del borde izquierdo de la celda con el origen. Es decir, imaginamos que se crea una línea entre la esquina inferior izquierda del obstáculo y el origen, y obtenemos la pendiente inversa de dicha línea. En este caso es de aproximadamente 0.82.

Para hacernos una idea del punto desde el que se obtendría la pendiente, hagamos una especie de zoom a las celdas comprometidas en este proceso.


 +---+xxxxx#####  x = Primera celda bloqueante.
 |   |xxxxx#####  & = punto desde el que calcular
 |   |xxxxx#####      la pendiente normalizada.
 +---&xxxxx#####
 +---++---++---+
 |   ||   ||   |
 |   ||   ||   |
 +---++---++---+

Es el momento de iniciar un nuevo escaneo recursivo una fila por encima. Este nuevo escaneo, sin embargo, no recorrerá toda la fila, sino que recorrerá hasta llegar a la pendiente tope (0.82). Con esto conseguimos que la nueva pendiente tope nos defina el comienzo de “la sombra” del obstáculo en los sucesivos escaneos. En el siguiente diagrama veremos el recorrido que harán por ahora los dos escaneos activos.

 
 2222............. 16  # = Celda bloqueante
  2222..###....... 15  . = Celda no bloqueante
   222..###....... 14  
    222.###..#..## 13  1 = Escáner original
     111##11111111 12  2 = Nuevo escáner con tope 0.82

Vemos que el escáner 2 se detiene siempre antes de llegar a la celda cuya pendiente normalizada con el origen es igual o inferior a 0.82. Al terminar cada fila escanea la superior, siempre con el tope de 0.82. Si encontrase algún nuevo obstáculo en su recorrido (no es el caso), generaría también un nuevo escáner con un tope aún más estricto. Mientras tanto, el escáner original debe seguir escaneando el resto de la fila.

 
 ................. 16  # = Celda bloqueante
  ......###....... 15  . = Celda no bloqueante
   .....###....... 14  
    ....###..#..## 13  o = Primera celda no bloqueante
     ...##o....... 12      después de una sección de bloqueantes.

El escáner original comprobaría la siguiente celda y vería que también es una celda bloqueante, en este caso continua sin hacer nada hasta encontrar una celda no bloqueante. Casualmente la siguiente celda es no bloqueante. En este caso se vuelve a realizar un cálculo de la pendiente con el lado derecho de la celda bloqueante previa, pero esta vez el punto es más cercano a la esquina superior como veremos al realizar zoom.

 
 ##########&oooo  o = Primera celda no bloqueante
 ##########o   o  & = Punto desde el que calcular
 ##########o   o      la pendiente normalizada.
 ##########ooooo
 +---++---++---+
 |   ||   ||   |
 |   ||   ||   |
 +---++---++---+

Esta nueva pendiente con un valor aproximado de 0.6 definirá el límite de la sombra de los bloqueantes vistos. Tras analizar el resto de la fila, el siguiente escáner que comience en la fila superior lo haría a partir de la casilla que supere dicha pendiente de inicio.

De hecho, tras finalizar el escaneo de esta línea, el escáner original comienza a escanear la siguiente a partir de la casilla con la nueva pendiente de inicio. “Casualmente” (en realidad este ejemplo pretende abarcar todos los posibles casos extraños) es una casilla bloqueante como vemos en el siguiente diagrama.


 2222............. 16  # = Celda bloqueante
  2222..###....... 15  . = Celda no bloqueante
   222..###....... 14  1 = Escaneado por el esc. original
    222.#x#..#..## 13  2 = Escaneado por el esc. generado anteriormente.
     111##11111111 12  x = celda bloqueante del escáner original
                           tras empezar en la siguiente fila.

Cuando esto ocurre se debe continuar hasta encontrar una celda no bloqueante como ya hicimos en la fila 12 para definir una nueva pendiente de inicio. Sería dos celdas más allá, así que definimos una nueva pendiente de inicio a partir de ella y seguimos recorriendo la fila normalmente. Nos topamos con la siguiente celda bloqueante.


 2222............. 16  # = Celda bloqueante
  2222..###....... 15  . = Celda no bloqueante
   222..###....... 14  1 = Escaneado por el esc. original
    222.###11x..## 13  2 = Escaneado por el esc. generado anteriormente.
     111##11111111 12  x = celda bloqueante del escáner original

Es necesario ahora obtener una nueva pendiente tope e iniciar otro escáner recursivo, tal y como se hizo con la primera celda bloqueante de la fila 12. La diferencia del nuevo escáner con el escáner 2 es que este empezará desde la nueva pendiente de inicio que calculamos en la etapa anterior.


 ..........33..... 16  # = Celda bloqueante
  ......##333..... 15  . = Celda no bloqueante
   .....##333..... 14  3 = nuevo escáner.
    ....###..x..## 13  
     ...##........ 12  x = celda bloqueante del escáner original

Nótese que el nuevo escáner (el 3) ha comenzado también en celdas bloqueantes.

Continuando con el escáner original, buscamos ahora la primera celda no bloqueante tras la bloqueante encontrada. Al encontrarla, obtenemos una nueva pendiente de inicio y seguimos escaneando la fila hasta terminar e iniciar otro escaneo en la fila superior o hasta encontrar una nueva celda bloqueante.


 ................. 16  # = Celda bloqueante
  ......###....... 15  . = Celda no bloqueante
   .....###....... 14  o = primera celda no bloqueante tras bloqueante.
    ....###..#o.x# 13      
     ...##........ 12  x = celda bloqueante del escáner original

Encontramos una nueva celda bloqueante, con lo que repetimos el proceso de inciar un nuevo escáner con las pendientes de inicio y final calculadas. El nuevo escáner procesaría lo siguiente:


 ............444.. 16  # = Celda bloqueante
  ......###...44.. 15  . = Celda no bloqueante
   .....###...44.. 14  o = primera celda no bloqueante tras bloqueante.
    ....###..#o.x# 13  4 = nuevo escáner.   
     ...##........ 12  x = celda bloqueante del escáner original

El escáner original debe ahora buscar una celda no bloqueada, pero terminará de recorrer la fila sin encontrarla. Este es el caso en el que el escáner original no continua un nuevo escaneo en la fila superior. En su lugar, habrá generado sucesivos escáneres recursivos que seguirán escaneando las casillas pertinentes.


 2222......33444.. 16  # = Celda bloqueante
  2222..###33.44.. 15  . = Celda no bloqueante
   222..###33.44.. 14  1, 2, 3, 4 = escáneres activos.
    222.###11#11## 13  
     111##11111111 12 

Finalmente, el resultado sería:


 ....ssssss.....ss 16  @ = Emisor de luz
  ....ssss#..s..ss 15  # = Celda bloqueante
   ...ssss#..s..ss 14  . = Celda no bloqueante
    ...ss##..#..## 13  s = Celda sombreada (no iluminada)
     ...##........ 12
      ............ 11
       ........... 10
        .......... 9
         ......... 8
          ........ 7
           ....... 6
            ...... 5
             ..... 4
              .... 3
               ... 2
                .. 1
                 @

No es difícil asignar intensidad de luz en base a la distancia de la celda al emisor. Dejo una especie de gif de una cutrada hecha en Java a lo rápido donde se aprecia mínimamente una versión de este algoritmo aplicada a los 8 cuadrantes. Las celdas marrones son celdas bloqueantes de luz.Screenshots de un cutre roguelike

Hay más alternativas

No solo existe raycasting y shadowcasting, existen otros esquemas de iluminación. En cualquier caso, para cada esquema hay algoritmos que difieren muchísimo en su implementación. Los algoritmos de shadowcasting son actualmente los más utilizados en muchísimos engines 3D y juegos modernos, aunque no necesariamente los mejores.

Hay muchos juegos que pueden aprovechar mejor otro tipo de esquemas, o incluso no utilizar el más apropiado pero sí el más sencillo de implementar (como es el raycasting), decisión típica en diseñadores novatos, pero que por lo general no suele afectar demasiado al rendimiento.

En un futuro capítulo de Visión, luces y sombras veremos otra implementación con shadowcasting muy distinta.

Copyright © Björn Ritzl (anteriormente Björn Bergström) y Alexander Vega Jiménez (Uexkull)

Deja un comentario