Introducción

En el artículo anterior nos quedamos hablando sobre ángulos y trigonometría, pero en realidad no vimos nada sobre lo que es raycasting en específico.

El objetivo de esta entrega es explicar de qué se trata raycasting y empezar a ver cómo implementarlo. Con 80% más triángulos, funciones trigonométricas y Pitagoras.

Y a todo esto, ¿qué es raycasting?

Se le conoce como raycasting a una técnica para generar imágenes por computadora. La idea básica es muy simple y se puede ejecutar en tiempo real, por lo que ha sido utilizada en videojuegos. Sin embargo produce imágenes poco realistas.

La idea es la siguiente:

  1. Tienes a un observador (el jugador en un juego de primera persona) viendo en una dirección determinada.
  2. Partiendo del observador y en dirección hacia donde está viendo, se lanzan rayos imaginarios. El número de rayos es igual al ancho de la resolución total de la imagen. Es decir si la imagen es de 800x600 entonces se van a lanzar 800 rayos. Estos rayos forman un cono, a este cono se le conoce como campo de visión (field of view).
  3. Cuando un rayo se topa con una pared, se calcula la distancia a la que se encuentra la pared.
  4. De acuerdo a esta distancia, se pinta ese segmento de la imagen (una columna). Entre mayor sea la distancia, menor va a ser la columna pintada. Entre menor sea la distancia, mayor va a ser la columna. Justo como en la vida real: objetos más cercanos se ven más grandes que objetos más lejanos.

corner-1

En este momento tal vez se estén preguntando: ¿por qué el número de rayos tiene que ser igual al ancho de la resolución?

column-render

Supongamos que nuestro viewport (es decir el espacio donde se va a proyectar la imagen) es de 512 píxeles de ancho. Por cada píxel de ancho se lanza un rayo, se calcula la distancia en la que topa con pared y se pinta una columna (una línea vertical) de 1 píxel de ancho y de n píxeles de alto, donde n es la altura proporcional a la distancia.

Podemos utilizar menos rayos para ahorrar recursos. Supongamos que queremos usar la mitad de rayos, entonces para 512 píxeles usaremos 256 rayos. En este caso la columna en vez de ser de 1 píxel de ancho, será de 2, efectivamente estamos reduciendo la resolución a la mitad.

Este manejo por columna es una de las razones por las que la técnica de raycasting es lo suficientemente rápida como para generar imágenes en tiempo real con requerimientos de hardware modesto. Otra es que con raycasting sólo se calculan las superficies que son visibles por el jugador (dentro de su campo de visión) y se ignora el resto.

De hecho Wolfenstein 3D podía ejecutarse en PCs con procesadores 286.

En el inicio...

Antes de empezar a programar nuestro motor gráfico, necesitamos definir el mundo que vamos a representar y las limitantes que vamos a usar para simplificar dicha representación.

En nuestro mundo:

  1. El piso es plano. No hay elevaciones, escaleras, valles, etc.
  2. Todas las paredes forman un ángulo de 90° con respecto al piso.
  3. El mundo es cerrado. No hay áreas abiertas.
  4. Las paredes se componen de cubos de cierto tamaño.

El último punto puede causar cierta confusión. Supongamos que tenemos un mapa de 12x12, algo como esto:

[[5 5 1 5 1 5 1 5 1 5 1 5]
 [1 0 0 0 0 0 0 0 0 0 0 3]
 [1 0 0 0 0 0 0 0 0 0 0 3]
 [1 0 0 0 0 0 0 0 0 0 0 3]
 [2 0 0 0 0 0 0 0 0 0 0 3]
 [2 0 0 0 0 0 0 0 0 0 0 3]
 [2 0 0 0 0 0 0 0 0 0 0 3]
 [2 0 0 0 0 0 0 0 0 0 0 3]
 [2 0 0 0 0 0 0 0 0 0 0 3]
 [2 0 0 0 0 0 0 0 0 0 0 3]
 [2 0 0 0 0 0 0 0 0 0 0 3]
 [4 5 4 5 4 5 4 5 4 5 4 5]]

En donde un 0 representa espacio vacío, y > 0 representa una pared.

Si las paredes se componen de cubos de cierto tamaño, digamos 8x8x8 unidades (pero en realidad puede ser cualquier tamaño) entonces las paredes miden l = 8 * 12 unidades. Este tamaño al que le vamos a llamar "unidad", determina el tamaño mínimo que puede tener una pared (también afecta a las texturas, pero falta mucho para que lleguemos a eso).

Aquí lo importante es tener en mente que el tamaño del mapa no es necesariamente el tamaño de la pantalla (el viewport). El jugador puede estar tan cerca de la pared que incluso una sola sección (un cubo de 8x8x8) no pueda ser vista por completo en el ancho de la pantalla.

Nosotros vamos a definir nuestra unidad como unit = 64.

Campo de visión

El campo de visión es lo que el jugador alcanza a ver en un momento determinado. Podemos imaginarlo como un cono que se va abriendo a medida que se aleja del jugador. Este cono tiene un ángulo determinado, y a ese ángulo le llamamos campo de visón (field of view o simplemente FOV).

fov

El ojo humano tiene aproximadamente un campo de visión horizontal de alrededor de 210°, pero de esos 210° solo 114° los podemos usar para percibir la profundidad. La razón es muy simple: usamos ambos ojos para ayudarnos a percibir profundidad, y el campo de visión de ambos se sobrepone en estos 114° únicamente.

Típicamente los juegos en primera persona utilizan un campo de visión de entre 60° y 90°, aunque hay algunos que te dejan ajustarlo. En Quake 1 por ejemplo, el FOV por defecto es de 90°.

Nosotros vamos a definir el campo de visión como fov = π/3.

Ángulo entre rayos

Anteriormente se dijo que se va a lanzar un rayo por columna. Estos rayos van a formar una especie de abanico o cono, que representan el FOV del jugador.

Supongamos que:

  • El jugador se encuentra viendo en dirección de π/2 (a esto le llamamos rotación).
  • El campo de visión es de π/3.
  • La proyección mide 512 píxeles de ancho.

La rotación representa el centro del FOV, por lo que la mitad del FOV (π/6) queda a la derecha de la rotación actual, y la otra mitad a la izquierda:

  • Rayo 0: rot + (FOV / 2)
  • Rayo 511: rot - (FOV / 2)

Falta determinar el valor del ángulo entre los rayos 1, 2, 3...n. Esto es muy sencillo, simplemente incremento = (FOV / ancho de proyección).

Como nuestra proyección es de 512 píxeles, entonces incremento = (π/3) / 512.

Finalmente, para calcular el ángulo de un rayo n:

rayo n = (rotacion + (FOV / 2)) - (incremento * n)

Demo

Ya tenemos las propiedades del mundo que vamos a representar. Lo que sigue es ponerlo en práctica.

Según mis cálculos, lo que vamos a implementar a continuación es 1/4 de lo que se necesita para un motor gráfico con raycasting simple. Por simple me refiero a sin texturas, sin puertas, sin enemigos, solo el jugador y algunas paredes de colores. Lo que resta sería el algoritmo para encontrar las paredes, calcular la distancia y finalmente pintar las columnas.

El objetivo del demo es visualizar las propiedades que definimos para nuestro mundo virtual, y jugar con los parámetros para ver como afectan a la proyección.

Vamos a visualizar los siguientes parámetros (todos los ángulos en radianes):

  • FOV
  • Ángulo entre cada rayo
  • Total de rayos
  • Rotación (dirección hacia donde se encuentra orientado el jugador)
  • Posición del jugador (coordenadas x,y en el mapa 2D donde se encuentra el jugador)

El demo se manipula utilizando las siguientes teclas:

  • Flechas arriba / abajo: incrementa / decrementa el FOV.
  • Flechas izquierda / derecha: modifican la rotación.
  • w a s d: modifican la posición (arriba, abajo, strafe).
  • j k: duplica / reduce a la mitad el número de rayos.
  • barra de espacio: revierte a valores iniciales.

Funcionamiento

En realidad el demo no es muy distinto al anterior. Lo más complicado es el manejo del teclado y la manipulación del estado del sistema. El funcionamiento es el mismo: tenemos las funciones setup, key-pressed y draw.

Lanzando rayos

La parte más relevante es la lógica para lanzar los rayos. En este momento lo único que hacemos es pintar una línea que representa al rayo ficticio, pero en la versión final esto no va a ser así.

Empezamos calculando el ángulo inicial:

(let [[width height] world-size
      [x1 y1 :as p1] pos
      ray-angle (+ rotation half-fov)])

El ángulo inicial es el ángulo de rotación actual + la mitad del FOV.

(doseq [n-ray (range 1 (inc num-rays))]
        (let [ray-angle (normalize-angle (- ray-angle (* n-ray ray-inc)))
              [x2 y2 :as p2] [(+ x1 (* 200 (q/cos ray-angle)))
                              (- y1 (* 200 (q/sin ray-angle)))]]
          (q/line p1 p2)))

Después creamos una lista que va del 1...número de rayos + 1 (este es el rayo que estamos trazando actualmente) y por cada rayo calculamos el ángulo del mismo. Con este ángulo calculamos la dirección de la línea usando la fórmula que vimos en el artículo pasado. El 200 en este caso es una longitud arbitraria para efectos de visualización. En la versión final, la longitud se va a calcular cuando el rayo choque con una pared.

El resto es simplemente pintar los valores actuales.

Manipulando el mundo

La lógica detrás de la manipulación de las variables de la simulación es sencilla. En teoría solo hay que:

  1. Detectar la tecla presionada.
  2. Calcular los nuevos valores a partir de los valores actuales.
  3. Actualizar el estado del sistema con los nuevos valores.

En la práctica la función para manejar los eventos del teclado se puede volver engorrosa rápidamente, ya que hay que manejar los distintos eventos, combinaciones de teclas (por ejemplo uso de shift, control, etc.) y asegurarnos de manipular todas las variables asociadas (por ejemplo si se manipula la rotación, hay que actualizar el vector de dirección, más adelante se explica al respecto).

De hecho en el siguiente artículo vamos a reescribir key-pressed para mejorar muchas de las limitantes actuales, va a quedar irreconocible. Pero por ahora nos tendremos que conformar con esto.

No hay sorpresas en su funcionamiento: es un case en donde dependiendo de la tecla presionada, se realiza una acción.

Número de rayos

(let [num-rays (if (= key-code 75) (/ num-rays 2) (* num-rays 2))
                  ray-inc (/ fov num-rays)]
              (-> state
                  (update-in [:num-rays] (constantly num-rays))
                  (update-in [:ray-inc] (constantly ray-inc))))

Multiplicamos o dividimos el número de rayos por 2, ya que de otra manera el cambio sería demasiado lento. Si modificamos el número de rayos, también tenemos que recalcular el incremento entre cada rayo.

Posición del jugador arriba / abajo

(let [[width height] world-size
                  accel 5
                  [x1 y1] pos
                  [x2 y2] [((if (= key-code 87) + -) x1 (* accel (q/cos rotation)))
                           ((if (= key-code 87) - +) y1 (* accel (q/sin rotation)))]]
              (update-in state [:pos]
                         (constantly [(if (or (< x2 0)
                                              (>= x2 width)) x1 x2)
                                      (if (or (< y2 0)
                                              (>= y2 height)) y1 y2)])))

Esto ya se parece más a un juego. Necesitamos mover al jugador del punto de origen a un punto final, dependiendo de la rotación actual. En otras palabras, usamos la misma ecuación de la línea vista anteriormente, solo que en vez de longitud de línea tenemos un factor de aceleración, que nos va a decir cuantas unidades se mueve el jugador por cuadro (efectivamente que tan rápido se mueve).

Además aprovechamos para agregar algo de detección de colisiones. Si realizar el movimiento pondría al jugador fuera de las coordenadas del mapa 2D, entonces no se modifica el valor del eje correspondiente.

Posición del jugador izquierda / derecha (strafe)

(let [[width height] world-size
                  accel 5
                  strafe-dir (normalize-angle (+ rotation (* 0.5 q/PI)))
                  [x1 y1] pos
                  [x2 y2] [((if (= key-code 65) + -) x1 (* accel (q/cos strafe-dir)))
                           ((if (= key-code 65) - +) y1 (* accel (q/sin strafe-dir)))]]
              (update-in state [:pos]
                         (constantly [(if (or (< x2 0)
                                              (>= x2 width)) x1 x2)
                                      (if (or (< y2 0)
                                              (>= y2 height)) y1 y2)])))

Muy similar al caso anterior, con una gran diferencia: la dirección del movimiento no se calcula en base a la rotación actual, sino a un plano que siempre va a estar perpendicular a la rotación actual del jugador, y paralelo al plano de proyección. Suena más complicado de lo que realmente es, y creo que queda mucho más claro jugando con el demo.

En el demo, la rotación se representa por la línea roja, y el vector de dirección por la línea amarilla. Imaginen que la línea amarilla está paralela a la pantalla donde se va a proyectar la imagen. Entonces el movimiento se va a ser en la misma dirección que la línea amarilla.

Rotación

(let [new-rotation (normalize-angle ((if (= key-code 37) + -) rotation res))
                  new-dir (normalize-angle (+ new-rotation (* 0.5 q/PI)))]
              (-> state
                  (update-in [:rotation] (constantly new-rotation))
                  (update-in [:dir] (constantly new-dir))))

La rotación es uno de los movimientos más sencillos, simplemente se le suma una cantidad al ángulo de rotación actual. Como modificamos la rotación, hay que modificar el vector de dirección para que siga siendo perpendicular a la rotación.

FOV

(let [fov ((if (= key-code 38) + -) fov (* 0.02 q/PI))]
              (-> state
                  (update-in [:fov] (constantly fov))
                  (update-in [:half-fov] #(* fov 0.5))
                  (update-in [:ray-inc] #(/ fov num-rays))))

Finalmente tenemos la acción de incrementar / decrementar el campo de visión. Si modificamos el campo de visión, se modifica también el número de rayos que vamos a necesitar.

Código completo

A continuación el código completo para que puedan seguirlo más fácilmente. En la siguiente entrega vamos a empezar a organizar el proyecto de manera que las funciones que son propias del engine vayan en su propio namespace.

(ns sheepish-3d.world-building
  (: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 initial-state
  []
  (let [[width height :as world-size] [512 320]
        fov (/ q/PI 3)
        ray-inc (/ fov width)
        rotation (/ q/PI 2)
        dir (+ rotation (* 0.5 q/PI))
        num-rays width]
    {:fov fov :half-fov (* fov 0.5) :world-size world-size :ray-inc ray-inc
     :rotation rotation :dir dir :res (/ q/PI 64) :pos [(/ width 2) (+ (/ height 2) 50)]
     :num-rays num-rays}))

(defn setup
  []
  (q/smooth)
  (q/frame-rate 60)
  (initial-state))

(defn draw
  [{:keys [fov half-fov ray-inc world-size rotation pos dir num-rays] :as state}]

  ;; draw background
  (q/background 98 114 164)

  (let [[width height] world-size
        [x1 y1 :as p1] pos
        ray-angle (+ rotation half-fov)]

    (q/with-stroke [80 120]
      ;; shoot rays
      (doseq [n-ray (range 1 (inc num-rays))]
        (let [ray-angle (normalize-angle (- ray-angle (* n-ray ray-inc)))
              [x2 y2 :as p2] [(+ x1 (* 200 (q/cos ray-angle)))
                              (- y1 (* 200 (q/sin ray-angle)))]]
          (q/line p1 p2))))

    ;; rotation line
    (q/stroke 255 85 85)
    (q/line p1 [(+ x1 (* 100 (q/cos rotation)))
                (- y1 (* 100 (q/sin rotation)))])

    ;; direction line
    (q/stroke 241 250 140)
    (q/line p1 [(+ x1 (* 50 (q/cos dir)))
                (- y1 (* 50 (q/sin dir)))])

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

    ; stats
    (q/fill 255 184 108)
    (q/text "FOV: " 10 15)
    (q/text "Ray inc: " 10 30)
    (q/text "Ray count: " 10 45)
    (q/text "Direction: " 10 60)
    (q/text "Position: " 10 75)

    (q/fill 80 250 123)
    (q/text fov 80 15)
    (q/text ray-inc 80 30)
    (q/text num-rays 80 45)
    (q/text rotation 80 60)
    (q/text (str (int x1) " " (int y1)) 80 75)))

(defn key-pressed
  [{:keys [rotation res fov world-size pos num-rays] :as state} {:keys [key-code]}]
  (case key-code

    ;; num rays
    (75 74) (let [num-rays (if (= key-code 75) (/ num-rays 2) (* num-rays 2))
                  ray-inc (/ fov num-rays)]
              (-> state
                  (update-in [:num-rays] (constantly num-rays))
                  (update-in [:ray-inc] (constantly ray-inc))))

    ;; position up / down
    (87 83) (let [[width height] world-size
                  accel 5
                  [x1 y1] pos
                  [x2 y2] [((if (= key-code 87) + -) x1 (* accel (q/cos rotation)))
                           ((if (= key-code 87) - +) y1 (* accel (q/sin rotation)))]]
              (update-in state [:pos]
                         (constantly [(if (or (< x2 0)
                                              (>= x2 width)) x1 x2)
                                      (if (or (< y2 0)
                                              (>= y2 height)) y1 y2)])))

    ;; strafe left / right
    (65 68) (let [[width height] world-size
                  accel 5
                  strafe-dir (normalize-angle (+ rotation (* 0.5 q/PI)))
                  [x1 y1] pos
                  [x2 y2] [((if (= key-code 65) + -) x1 (* accel (q/cos strafe-dir)))
                           ((if (= key-code 65) - +) y1 (* accel (q/sin strafe-dir)))]]
              (update-in state [:pos]
                         (constantly [(if (or (< x2 0)
                                              (>= x2 width)) x1 x2)
                                      (if (or (< y2 0)
                                              (>= y2 height)) y1 y2)])))

    ;; rotate left / right
    (37 39) (let [new-rotation (normalize-angle ((if (= key-code 37) + -) rotation res))
                  new-dir (normalize-angle (+ new-rotation (* 0.5 q/PI)))]
              (-> state
                  (update-in [:rotation] (constantly new-rotation))
                  (update-in [:dir] (constantly new-dir))))

    ;; increase / decrease fov
    (38 40) (let [fov ((if (= key-code 38) + -) fov (* 0.02 q/PI))]
              (-> state
                  (update-in [:fov] (constantly fov))
                  (update-in [:half-fov] #(* fov 0.5))
                  (update-in [:ray-inc] #(/ fov num-rays))))

    ;; reset
    32 (initial-state)
    state))

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

Conclusión

Si bien el demo sigue siendo un tanto básico, ya contiene varios de los elementos que vamos a utilizar para nuestro raycaster:

  1. Cálculo del campo de visión.
  2. Cálculo del ángulo entre rayos.
  3. Generación de los rayos subsecuentes.
  4. Manipulación de posición y dirección.
  5. Detección de colisiones.

Puedo decir con total confianza y absoluta certidumbre de que es un valor completamente arbitrario, que hemos completado un 38% del total del proyecto.

Una de las características del demo actual es que los rayos tienen una longitud fija de 200 unidades. En la siguiente entrega veremos cómo extender los rayos para detectar colisiones y determinar la longitud (y por lo tanto la distancia) de cada rayo. Se va a poner bueno.