Introducción

No recuerdo como llegué a él, pero uno de mis sitios favoritos es el de Fabien Sanglard. Tiene una serie de artículos de excelente calidad principalmente sobre gráficos por computadora. Pero los especialmente famosos son los que reseñan motores gráficos (engines) de antaño. Dos de ellos los extendió y publicó como libros:

  1. Game Engine Black Book: Wolfenstein 3D
  2. Game Engine Black Book: Doom.

Si disfrutan de los artículos, les recomiendo ampliamente los libros en formato físico. La calidad de impresión es muy buena y el detalle de las imágenes simplemente no es el mismo que en formato eBook.

Recientemente compré el libro de Wolfenstein 3D y tengo que decir que es fascinante leer sobre los retos técnicos que el equipo de id Software en general, y John Carmack en particular, enfrentaron para hacer que la PC pudiera desplegar gráficos en pseudo-3D. Y no sólo eso, sino que lo hiciera lo suficientemente rápido, con gráficos impresionantes (para la fecha), con efectos de sonido e incluso una simulación de propagación de sonido que alertaba a los enemigos de tu presencia, y encima de todo divertido.

Así que hice lo que cualquier persona haría, y decidí programar mi propio raycaster. Está de más decir que lo único que tiene en común con el milagro técnico que fue en su momento Wolfenstein 3D es que ambos utilizan la técnica de raycasting para proyectar un mapa en 3D, pero hasta ahí. En realidad lo que hace especial a Wolf no es su uso de raycasting, sino los hacks necesarios para lograr que una computadora sin el hardware necesario para operaciones de punto flotante, sin doble buffer de video y con menos de 64kb disponibles de memoria total, fuera capaz de semejante proeza.

El objetivo de esta serie de artículos es explicar la técnica de raycasting y que puedan crear su propia implementación. Raycasting es especialmente atractivo ya que, como vamos a ver, no requiere de conceptos matemáticos complejos para generar mundos en 3D. Solamente son necesarios conceptos básicos como manejo de ángulos, vectores y trigonometría. La implementación la vamos a hacer en ClojureScript para poder incluir ejemplos ejecutables en el mismo artículo.

La implementación completa estará dividida en varios artículos. Al final de cada uno voy a incluir una implementación de ejemplo con lo que se ha visto hasta ese momento, para servir a manera de ejemplo e inspiración para seguir adelante. A riesgo de extenderme demasiado, voy a tender a explicar en extremo detalle cada uno de los conceptos, por lo que si algo les resulta demasiado básico pueden saltarlo con confianza.

Pero principalmente, espero que lo encuentren divertido.

Ángulos y Triángulos

Lo único que necesitan para poder crear su propio motor gráfico utilizando la técnica de raycasting es:

  1. Conocer algún lenguaje de programación.
  2. Operaciones con ángulos.
  3. Trigonometría.

Por esto y a manera de recordatorio, el artículo actual va a tratar sobre estos tres puntos. Al final vamos a crear pequeño programa que nos permitirá visualizar un ángulo y modificar la magnitud del mismo utilizando el teclado. No parece muy interesante, pero servirá para validar los conceptos vistos.

¿Grados o Radianes?

Cuando pensamos en ángulos, estamos acostumbrados a pensar en grados. Incluso son parte de nuestro lenguaje coloquial: decimos por ejemplo dio un giro de 180 grados para referirnos a que algo cambió completamente de sentido. También sabemos casi por naturaleza que solo hay 360 grados. Así como una hora tiene 60 minutos, un ángulo no puede medir más de 360 grados, y punto.

Sin embargo y como muchas otras cosas en nuestra vida cotidiana, el número 360 es completamente arbitrario y bien pudo haber sido 100. Básicamente lo que sucedió fue que en la necesidad de poder medir ángulos, alguien (o un grupo tal vez) tomó un círculo y dijo "vamos a dividir este círculo en 360 partes" y listo. Por eso no hay ángulos de más de 360 grados.

Pero los radianes son diferentes.

En radianes la medida del ángulo se relaciona directamente con el círculo, lo cual tiene sentido ya que un ángulo es un pedazo de un círculo. Para saber lo que mide un radian tomamos un círculo de radio 1 (círculo unitario):

unit-circle

Formamos un ángulo, recordando que un ángulo no es otra cosa que un pedazo de ese círculo, y notamos como la circunferencia forma un arco opuesto al ángulo:

1-radian

Cuando ese arco mide igual que el radio (1 en este caso), eso es 1 radian. En medio círculo hay π radianes, y en un círculo completo hay 2π radianes.

Entonces nosotros vamos a trabajar en radianes. Además prácticamente todas las funciones trigonométricas que vamos a utilizar esperan grados en radianes, y con esto nos evitamos el estar haciendo operaciones de conversión. Sea cual sea la manera que utilicen para medir y especificar ángulos, solo hay que asegurarse de ser congruentes.

Midiendo ángulos

Para nuestros propósitos, necesitamos una manera de cuantificar ángulos que nos diga dos cosas:

  1. La magnitud del ángulo. Es decir que tan grande es.
  2. La dirección del ángulo. Es decir si es un ángulo positivo (sentido contrario a las manecillas del reloj) o negativo (sentido de las manecillas del reloj).

La dirección es fundamental porque nos va a decir si un rayo va hacia arriba o hacia abajo, y como veremos más adelante, en la manera en que calculamos la posición actual del rayo, y si esta posición es libre o representa una pared.

pos-neg-angles

Vamos a estar trabajando con ángulos, y una de las operaciones más comunes va a ser sumar dos ángulos. Por ejemplo, supongamos que nuestro jugador se encuentra viendo directamente al este, y tiene un campo de visión de 60 grados (o π/3 radianes para irnos acostumbrando), entonces este jugador puede ver a su izquierda lo que se encuentre dentro de un ángulo de π/6, y a su derecha lo que se encuentre dentro de un ángulo de -π/6 (porque es un ángulo negativo).

Suponiendo que vamos a trazar 320 rayos, entonces el ángulo de cada rayo subsecuente debe ser angulo nuevo = angulo anterior -(π/960). Empezamos en 0 + π/3:

  1. Rayo 0 = π/3 - π/960
  2. Rayo 1 = Rayo 0 - π/960
  3. Rayo 2 = Rayo 1 - π/960
  4. ...
  5. Rayo n = Rayo n-1 - π/960

Pero va a llegar un momento (en la mitad exactamente en nuestro ejemplo) en el que el ángulo va a dejar de ser positivo y se va a convertir en un ángulo negativo:

  1. Rayo 157 = 0.0032724923474893863
  2. Rayo 158 = 0.0016362461737446932
  3. Rayo 159 = 0.0
  4. Rayo 160 = -0.0016362461737449152
  5. Rayo 161 = -0.0032724923474898304

Si nos fijamos, los valores negativos de los ángulos son exactamente los mismos que los valores positivos, solo que cambia el signo (la dirección del rayo). El ángulo del rayo 160 es igual al ángulo 158, solo que el primero es medido como un ángulo negativo y el segundo como un ángulo positivo.

A eso le llamamos normalizar el ángulo.

Suponiendo que no normalizáramos los ángulos, y tuviéramos un ángulo a1 = 1/4 π y otro ángulo a2 = 3/2 π y los sumamos r = a1 + a2, el resultado sería r = 7/4 π lo cual es correcto pero está midiendo el ángulo positivo. Nosotros necesitamos medir el ángulo negativo (-1/4 π).

Normalizando ángulos

El parámetro de entrada va a ser un ángulo en radianes. Lo primero que tenemos que hacer es asegurarnos que el ángulo cumpla con 0 < α < 2π

(mod α (* 2 Math/PI))

La explicación de por qué se usa mod aquí queda fuera del alcance de este artículo, pero si les interesa saber cómo llegamos a esto pueden consultar el código fuente de Apache commons-math. Algo importante que recalcar es que la función mod de Clojure(Script) no corresponde al operador módulo % que es común en otros lenguajes de programación.

Después simplemente comparamos: si el ángulo es mayor a π (es decir, 180 grados), le restamos 2π (es decir 360 grados). Si no es mayor a π entonces lo regresamos igual.

Lo anterior es equivalente a decir: si el ángulo está en los cuadrantes I o II, regresa el valor del ángulo positivo. Si está en los cuadrantes III o IV, regresa el valor del ángulo negativo.

La función completa queda así:

(defn normalize-angle
  [α]
  (let [π-sqr (* 2 q/PI)
        α (mod α π-sqr)]
    (if (> α q/PI) (- α π-sqr) α))

Demo

Finalmente tenemos una pequeña demostración de la normalización de ángulos en acción. Para usarlo es necesario dar click en el elemento canvas para asegurarnos que tenga el foco, y usar las flechas de dirección del teclado para alterar el ángulo.

Observar cómo la magnitud del ángulo jamás excede π (cuando se aproxima a 180 grados por el cuadrante II) y jamás es menor de -π (cuando se aproxima a 180 grados por el cuadrante III). Lo mismo sucede al aproximarse a los 0/360 grados por los cuadrantes I y IV.

El código es muy sencillo. Para la animación utilizamos Quil, una librería para animaciones en Clojure y ClojureScript. Gracias a Quil podemos definir nuestra animación (sketch en el lingo de Quil) sin mucha ceremonia y utilizando un estilo funcional que va muy ad hoc con Clojure.

Primero definimos nuestro sketch:

(q/defsketch angles-demo
  :host "angles-demo"
  :draw draw
  :setup setup
  :key-pressed key-pressed
  :middleware [m/fun-mode]
  :size [512 320])
  • :host es el id del elemento canvas en la página que contendrá el sketch.
  • :middleware es configuración específica de Quil para utilizar programación funcional.
  • :size es el tamaño del sketch.

Ahora nos vamos a concentrar en las funciones setup, key-pressed y draw, en ese orden.

Setup

La función setup la ejecuta Quil una vez al iniciar, y define el estado inicial de nuestro sketch. En este caso define el ángulo inicial (π/2) y la resolución del incremento del ángulo (π/64). Este estado inicial es utilizado por las funciones subsecuentes.

(defn setup []
  (do (q/smooth)
      (q/frame-rate 60)
      {:angle (normalize-angle (q/radians 90)) :res (/ q/PI 64)}))

Key-pressed

Como su nombre lo indica, key-pressed se ejecuta cada vez que se recibe un evento del teclado. De acuerdo a la tecla presionada se incrementa o decrementa el valor del ángulo en el estado del programa.

(defn key-pressed
  [{:keys [angle res] :as state} {:keys [key key-code]}]
  (case key
    (:up :right) (update-in state [:angle] #(normalize-angle (+ % res)))
    (:down :left) (update-in state [:angle] #(normalize-angle (- % res)))
    state))

Draw

draw es la función que se ejecuta para dibujar el sketch. Recibe como parámetro el estado actual, y se encarga de dibujar un cuadro (frame). Nuestro sketch lo tenemos configurado a 60 cuadros por segundo.

Primero pinta el fondo, el eje x, el círculo en el centro y un pequeño punto rojo indicando el centro, de donde vamos a pintar una linea (rayo) en ángulo con el eje x. En la esquina superior izquierda se despliega la dirección del rayo (arriba/abajo), el valor normalizado del ángulo actual, y el cuadrante en el que se encuentra el rayo.

Lo realmente interesante viene en cómo pintar el rayo. Sabemos que parte del centro del sketch, pero necesitamos saber en que coordenadas termina. Conocemos el origen, la longitud (el radio del círculo) y el ángulo.

(q/line [x1 y1]
        [(+ x1 (* length (q/cos angle)))
         (- y1 (* length (q/sin angle)))])

La fórmula para conocer las coordenadas finales del rayo es (en el código se resta y1 en vez de sumarse ya que en el sistema de coordenadas usados por Quil, el eje y crece hacia abajo):

$$(x_2,y_2)=(x_1+l\cdot\cos(a),y_1+l\cdot\sin(a)) ;$$

Pero aquí estamos para entender el por qué y no para usar fórmulas a ciegas, así que vamos a ver de donde sale y servirá de introducción a las operaciones trigonométricas que vienen más adelante.

El rayo y el eje x forman un triángulo rectángulo. El eje x es el cateto adyacente (a), y lo largo del rayo (el radio del círculo) es la hipotenusa (h). El cateto opuesto (b) no lo tenemos, pero es perpendicular al eje x.

finding-x2

En la imagen anterior se puede observar claramente que para llegar al punto (x2,y2), partiendo del origen (x1,y1) sumamos a x1 el cateto adyacente, y sumamos (restamos en nuestro caso) a y1 el cateto opuesto.

Por definición:

$$h=b \div a ;$$

$$a=h\cdot\cos(α) ;$$

$$b=h\cdot\sin(α) ;$$

Entonces:

$$x_2=x_1+h\cdot\cos(α) ;$$

$$y_2=y_1+h\cdot\sin(α) ;$$

Y finalmente:

$$(x_2,y_2)=(x_1+h\cdot\cos(α),y_1+h\cdot\sin(α)) ;$$

Código completo

(ns sheepish-3d.angles-demo
  (:require [quil.core :as q :include-macros true]
            [quil.middleware :as m]))

(defn normalize-angle
  "Given an angle (in radians), return a corresponding angle that is normalized between 2π - π
  The sign represents the angle direction."
  [α]
  (let [π-sqr (* 2 q/PI)
        α (mod α π-sqr) ;; make angle between 0 -- 2π
        ]
    (if (> α q/PI)
      (- α π-sqr)  ;; make angle between -π -- π
      α)))

(defn setup []
  (do (q/smooth)
      (q/frame-rate 60)
      {:angle (normalize-angle (* 0.25 q/PI)) :res (/ q/PI 64)}))

(defn draw
  [{:keys [angle] :as state}]
  (let [x1 (/ 512 2)
        y1 (/ 320 2)
        length y1
        x2 (+ x1 (* length (q/cos angle)))
        y2 (- y1 (* length (q/sin angle)))]

    ;; background
    (q/background 98 114 164)

    ;; x axis
    (q/stroke 248 248 242)
    (q/line [0 length] [512 length])

    ;; radar
    (q/stroke 248 248 242)
    (q/fill 98 114 164)
    (q/ellipse x1 y1 320 320)

    ;; center dot (origin)
    (q/stroke 255 85 85)
    (q/fill 255 85 85)
    (q/ellipse x1 y1 2 2)

    ;; hypotenuse
    (q/stroke 255 85 85)
    (q/line [x1 y1] [x2 y2])

    (q/stroke 255 184 108)
    ;; opposite
    (q/line [x2 y2] [x2 y1])

    ;; adjacent
    (q/line [x1 y1] [x2 y1])

    ;; draw angle indicator
    (q/fill 255 184 108)
    (q/text "Ray direction: " 10 15)
    (q/text "Angle value: " 10 30)
    (q/text "Quadrant: " 10 45)
    (if (pos? angle) (q/fill 80 250 123) (q/fill 255 121 198))
    (q/text (if (pos? angle) "Up" "Down") 90 15)
    (q/fill 80 250 123)
    (q/text angle 90 30)
    (q/text (cond
              (and (>= angle 0) (< angle (/ q/PI 2))) "I"
              (and (>= angle (/ q/PI 2)) (< angle q/PI)) "II"
              (and (>= (+ angle (* 2 q/PI)) q/PI) (< (+ angle (* 2 q/PI)) (* 1.5 q/PI))) "III"
              (>= (+ angle (* 2 q/PI)) (* 1.5 q/PI)) "IV")
            90 45)))

(defn key-pressed
  [{:keys [angle res] :as state} {:keys [key key-code]}]
  (case key
    (:up :right) (update-in state [:angle] #(normalize-angle (+ % res)))
    (:down :left) (update-in state [:angle] #(normalize-angle (- % res)))
    state))

(q/defsketch angles-demo
  :host "angles-demo"
  :draw draw
  :setup setup
  :key-pressed key-pressed
  :middleware [m/fun-mode]
  :size [512 320])

Conclusión

Cuando empecé a programar lo hice, como muchos de mis colegas contemporáneos, con el objetivo de programar videojuegos. Uno de mis primeros intentos fue crear un juego similar al legendario DOOM. Está de más decir que mi intento no llegó muy lejos.

Gran parte de mi frustración se debía no tanto a la complejidad de los temas, sino a la falta de documentación clara al respecto. Existían algunos recursos, pero la gran mayoría hacían obvios conceptos que, por lo menos a mi yo de hace 20 años, eran todo menos obvios. Está también mi falta de comprensión de temas fundamentales de matemáticas que son absolutamente necesarios, y por supuesto mi falta de experiencia programando.

Con esta serie pretendo crear los recursos que a mi yo de hace 20 años le hubieran gustado que existieran. Seguramente tampoco hubiera logrado crear su DOOM clone, pero tal vez hubiera llegado un poco más lejos.