Introducción

La idea principal en raycasting es lanzar rayos a intervalos regulares y determinar la distancia en la que cada rayo se topa con una pared. En Raycasting 2 vimos cómo lanzar rayos a intervalos regulares, en esta entrega veremos cómo seguir el rayo del origen hasta encontrarse con una pared, y finalmente determinar la distancia.

Siguiendo rayos

En mi opinión esta es la parte "complicada" del motor gráfico.

Supongamos que tenemos el siguiente mapa (0 es espacio vacío):

(def grid [[1 1 1 1 1 1 1 1 1 1 1 1]
           [1 0 0 0 0 0 0 0 0 0 0 1]
           [1 0 0 0 0 0 0 0 0 0 0 1]
           [1 0 0 0 0 0 0 0 0 0 0 1]
           [1 0 0 0 0 0 0 0 0 0 0 1]
           [1 0 0 0 0 0 0 0 0 0 0 1]
           [1 0 0 0 0 0 0 0 0 0 0 1]
           [1 0 0 0 0 0 0 0 0 0 0 1]
           [1 0 0 0 0 0 0 0 0 0 0 1]
           [1 0 0 0 0 0 0 0 0 0 0 1]
           [1 0 0 0 0 0 0 0 0 0 0 1]
           [1 1 1 1 1 1 1 1 1 1 1 1]])

Es una cuadrícula de 12x12. Como nuestra unidad es de tamaño 64, las coordenadas que podemos ocupar en este mapa son 768x768 (12x64).

Dicho de otra manera, si queremos que nuestro jugador se encuentre en la posición (1,1), entonces las coordenadas pueden ir desde (64,64) para la esquina superior izquierda, hasta (127,127) para la esquina inferior derecha.

diagrama-posicion

Aquí es importante hacer una pausa para analizar estas coordenadas. Hablando del eje x, 63 aún pertenece a la columna anterior (columna 0), y 64 pertenece a la siguiente columna (columna 1).

columnas

Lo mismo para el eje y, 63 pertenece a la fila 0, y 64 pertenece a la fila 1, etc.

Es importante ser consistente con esta definición, ya que más adelante al estar verificando en qué posición se encuentra un rayo, asignarlo a una celda equivocada nos puede causar elementos extraños en nuestra escena (como secciones de paredes encimadas).

Lo se porque a mi me pasó.

Entonces supongamos que nuestro jugador se encuentra en las coordenadas [300, 400]. En estas coordenadas el jugador entonces se encuentra en la celda:

x = 300 / 64 = 4
y = 384 / 64 = 6

El jugador se encuentra en la celda [6, 6]

[[1 1 1 1 1 1 1 1 1 1 1 1]
 [1 0 0 0 0 0 0 0 0 0 0 1]
 [1 0 0 0 0 0 0 0 0 0 0 1]
 [1 0 0 0 0 0 0 0 0 0 0 1]
 [1 0 0 0 0 0 0 0 0 0 0 1]
 [1 0 0 0 0 0 0 0 0 0 0 1]
 [1 0 0 0 ^ 0 0 0 0 0 0 1]
 [1 0 0 0 0 0 0 0 0 0 0 1]
 [1 0 0 0 0 0 0 0 0 0 0 1]
 [1 0 0 0 0 0 0 0 0 0 0 1]
 [1 0 0 0 0 0 0 0 0 0 0 1]
 [1 1 1 1 1 1 1 1 1 1 1 1]]

Y supongamos también que se encuentra viendo (tiene una rotación de) hacia π/2 (90°), con su FOV de π/3 (60°).

La pregunta del millón es: ¿cómo saber si el rayo choca contra una pared? La respuesta a esta pregunta es lo que hace a un raycaster un raycaster.

Checando colisiones

Tenemos las coordenadas del jugador [300, 400], y con el FOV podemos determinar el ángulo del rayo. De Raycasting 2 sabemos que:

$$\ \text{rayo n} = (rotacion + \frac{FOV}{2} - (incremento \times n) $$

Entonces:

Rayo 0 = (π/2) + ((π/3) / 2) - 0
Rayo 0 = 2.094395102393195

La manera ingenua

Con el ángulo del rayo y la posición del jugador podemos ir incrementando el rayo en un intervalo pequeño, digamos de 1 unidad o menos (entre más pequeño mejor precisión) y checando el valor de la celda actual, si es > 0 entonces es una pared, guardamos la longitud del rayo y listo.

small-interval

En la imagen, cada punto sobre el rayo es el punto donde checamos colisiones.

Recordemos que:

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

h siempre va a ser 1 (porque incrementamos la línea en 1), entonces:

$$(x_2,y_2)=(x_1+\cos( \alpha ),y_1+\sin( \alpha )) $$

Para la posición de [300, 400] (redondeamos hacia abajo siempre, y recordamos que en el eje y restamos si el rayo va hacia arriba):

x2 = 300 + cos(2.094395102393195) = 299
y2 = 400 - sin(2.094395102393195) = 399

La nueva posición es [299, 399] y eso corresponde a la celda [4, 6] en el mapa porque 299 / 64 = 4. [4, 6] no contiene una pared, así que probamos de nuevo:

x2 = 299 + cos(2.094395102393195) = 298
y2 = 399 - sin(2.094395102393195) = 398

La nueva posición es [298, 398] y eso corresponde de nuevo a la celda [4, 6] en el mapa porque 298 / 64 = 4. [4, 6] no contiene una pared, así que el proceso se repite...

Por cada unidad.

Por cada columna.

60 veces por segundo.

Obviamente no es muy rápido que digamos.

La manera "astuta"

Si el problema es que estamos checando a intervalos muy pequeños (una unidad) entonces simplemente podemos incrementar este intervalo y reducir el número de chequeos que se hacen. Por ejemplo cada 100 en vez de cada 1:

x2 = 300 + (100 * cos(2.094395102393195)) = 250
y2 = 400 - (100 * sin(2.094395102393195)) = 313
y2 = [3, 4]

Efectivamente: se reduce el número de chequeos necesarios, pero eso va a causar que en el espacio entre cada chequeo nos saltemos paredes:

big-interval

Como podemos ver en la imagen anterior, el rayo colisiona con una celda que contiene una pared, pero debido al ángulo de colisión y el intervalo de chequeo, nunca detectamos esta colisión y el rayo sigue su camino.

La manera inteligente

Afortunádamente para nosotros este es un problema resuelto. Personas más inteligentes que yo se dieron a la tarea de resolverlo, porque resulta que es útil no solo para raycasting. Veamos la siguiente imagen:

exact

El momento eureka viene cuando nos damos cuenta que una colisión sólo puede ocurrir en los límites de cada celda. Entonces no es necesario revisar todos los puntos, basta con revisar en cada punto donde el rayo cruza una de las líneas que demarcan cada celda.

una colisión sólo puede ocurrir en los límites de cada celda

Si el rayo cruza una línea vertical, entonces es una posible colisión horizontal (es decir, con la celda que se encuentra a la izquierda o derecha de la posición actual del rayo).

Si el rayo cruza una línea horizontal, entonces es una posible colisión vertical (es decir, con la celda que se encuentra arriba o abajo de la posición actual del rayo)

Lo que tenemos que hacer entonces es encontrar todos los cruces tanto horizontales como verticales y checar colisiones en cada uno de ellos.

El algoritmo platicadito es el siguiente:

  • Partimos de la celda en donde se encuentra el jugador.
  • Para cruces verticales:
    • Encontramos la distancia desde el jugador al siguiente cruce vertical.
    • Verificamos si es pared.
      • Si es pared, terminamos y regresamos las coordenadas.
      • Si no es pared, extendemos el rayo hasta el siguiente cruce vertical y repetimos.
  • Para cruces horizontales:
    • Encontramos la distancia desde el jugador al siguiente cruce horizontal.
    • Verificamos si es pared.
      • Si es pared, terminamos y regresamos las coordenadas.
      • Si no es pared, extendemos el rayo hasta el siguiente cruce horizontal y repetimos.
  • Comparamos la distancia entre el cruce horizontal y el vertical, y regresamos el menor de los dos.

El último punto es necesario porque como nuestros mapas van a ser áreas cerradas, se garantiza que todos los rayos van a terminar en una colisión. En la imagen anterior el cruce final es horizontal, pero podemos imaginar que si estamos verificando sólo cruces verticales, el tercer y último cruce vertical sería una colisión, aunque la distancia al jugador es mayor que el último cruce horizontal.

Ahora el problema que tenemos que resolver es

  1. ¿Cómo encontramos los cruces?
  2. ¿Cómo extendemos el rayo?

Esa es la cuestión.

Encontrando intersecciones

Lo primero que tenemos que hacer para ver cómo encontramos las intersecciones, es identificar los datos que conocemos:

  • El ángulo del rayo.
  • La posición del jugador.
  • El tamaño de cada celda (64x64).
  • La celda actual en la que se encuentra el jugador.

Y lo que queremos encontrar es el punto exacto en donde el rayo cruza una de las líneas que forman la celda (el punto Ax,Ay en la imagen).

La posición del jugador es [300, 400] que corresponde a la celda [4, 6].

intersection

En la imagen anterior podemos ver que Ay se encuentra exactamente sobre el eje horizontal superior, y sabemos que la distancia entre el eje superior e inferior es exactamente 64. Lo que tenemos que hacer es encontrar la coordenada y de dicho eje:

if angle is positive
  Ay = floor(Py / unit) * unit
else
  Ay = (floor(Py / unit) * unit) + unit

Recordemos que estamos manejando ángulos normalizados (Raycasting 1) entonces si el ángulo es positivo, sabemos que el rayo va hacia arriba.

Lo que hace el pseudo-código anterior es simplemente determinar la celda en la que se encuentra el jugador y multiplicarlo por 64 para encontrar su coordenada. Como en la imagen el rayo es positivo:

Ay = floor(400 / 64) * 64
Ay = 6 * 64 = 384

Ya conocemos Ay y por lo tanto conocer Ax se vuelve un simple problema de trigonometría:

$$\tan( \alpha ) = \frac{opuesto}{adyacente} $$

Lo que queremos encontrar es adyacente entonces:

$$adyacente = \frac{Py - Ay}{\tan( \alpha )} $$

Finalmente le sumamos el valor actual de Py para obtener las coordenadas finales del punto de intersección A:

Ax = Px + ((Py - Ay) / tan(angulo))
Ax = 300 + ((400 - 384) / tan(2.094395102393195))
Ax = 290

El punto final entonces es [290, 384], lo cual corresponde a la celda localizada en [4, 6]...

85afd1ebc17194788d7581af4cf1a29f7dfc7b08b922f50dbc67bd64f08fa370

La celda original en la que esta el jugador es [4, 6] y estamos detectando un cruce horizontal en la celda [4, 6] lo cual no tiene sentido.

Lo que está pasando es que Ay = 384 queda justo en el borde de la celda, y la estamos considerando como parte de la celda que esta debajo del cruce, lo cual es incorrecto si seguimos nuestra definición:

Aquí es importante hacer una pausa para analizar estas coordenadas. Hablando del eje x, 63 aún pertenece a la columna anterior (columna 0), y 64 pertenece a la siguiente columna (columna 1).

En realidad nuestra intención es que el eje del cruce pertenezca a la celda que esta por encima. Para solucionarlo simplemente restamos 1 al valor de Ay. Esto porque el rayo va hacia arriba. Si el rayo fuera hacia abajo, entonces no sería necesario.

El punto de cruce sería [290, 383] lo que corresponde a la celda [4, 5]. Ahora si tiene sentido.

Los cruces verticales son muy similares, solo que en vez de verificar si el rayo va hacia arriba o abajo, se verifica si está a la izquierda o a la derecha.

Ejecución manual

Hagamos el ejercicio de ejecutar el algoritmo manualmente, paso a paso. Después de eso ya estaremos listos para ponerlo en código. Veremos que como siempre, el diablo está en los detalles.

Primero el pseudo-código del algoritmo completo para cruces horizontales:

map = [[1 1 1 1 1 1 1 1 1 1 1 1]
       [1 0 0 0 0 0 0 0 0 0 0 1]
       [1 0 0 0 0 0 0 0 0 0 0 1]
       [1 0 0 0 0 0 0 0 0 0 0 1]
       [1 0 0 0 0 0 0 0 0 0 0 1]
       [1 0 0 0 0 0 0 0 0 0 0 1]
       [1 0 0 0 0 0 0 0 0 0 0 1]
       [1 1 1 1 1 1 1 1 1 1 1 1]]
pos = [300, 400]
angle = 2.094395102393195
unit = 64

// Xa y Ya son los incrementos aplicados al rayo
// cuando queremos extenderlo porque no se ha topado
// con una pared
Xa = Ya = 0 

if rayo arriba {
  Ya = -unit
  Ay = floor(Py / unit) * unit
} else {
  Ya = unit
  Ay = (floor(Py / unit) * unit) + unit
}

Xa = Ya / tan(-a)
Ax = Px + ((Px - Ay) / tan(angle))

Ay = if rayo arriba { --Ay } else { Ay }

while (!wall(Ax, Ay)) {
  Ax = Ax + Xa
  Ay = Ay + Ya
}

return Ax,Ay

Y para cruces verticales:

if rayo izquierda {
  Xa = unit
  Bx = (floor(Px / unit) * unit) + unit
} else {
  Xa = -unit
  Bx = floor(Px / unit) * unit
}

Ya = Xa * tan(-angle)
By = Py + ((Px - Bx) * tan(angle))

Bx = if rayo izquierda { Bx } else { --Bx }

while (!wall(Bx, By)) {
  Bx = Bx + Xa
  By = By + Ya
}

return Bx,By

Lo bonito de este algoritmo es que extender el rayo es extremadamente rápido. Son solo sumas. Esto es posible porque una vez calculando Xa o Ya según sea el caso, esta distancia siempre va a ser la misma para cada punto de intersección de ese rayo.

Anteriormente comentaba que una de las razones por las que raycasting es posible en hardware modesto era en parte por la manera en la que se pinta por columnas y no por píxel. La otra gran razón es precisamente que extender los rayos no es computacionalmente muy demandante.

extender los rayos no es computacionalmente muy demandante

Intersecciones horizontales

  1. Ya = -64
  2. Ay = floor(400 / 64) * 64 = 384
  3. Xa = -64 / tan(-2.094395102393195) = -36.95
  4. Ax = 300 + ((300 - 384) / tan(2.094395102393195)) = 214.26
  5. Ay = 384 - 1 = 383
  6. ¿Hay pared en [214/64, 383/64] - [3, 5]? No
  7. Ax = 214.26 + -36.95, Ay = 383 + -64
  8. ¿Hay pared en [2, 4]? No
  9. Ax = 177.31 + -36.95, Ay = 319 + -64
  10. ¿Hay pared en [2, 3]? No
  11. Ax = 137.36 + -36.95, Ay = 255 + -64
  12. ¿Hay pared en [1, 2]? No
  13. Ax = 100.41 + -36.95, Ay = 191 + -64
  14. ¿Hay pared en [0, 1]? Si
  15. Resultado es [63.46, 127]

Intersecciones verticales

  1. Xa = -64
  2. Bx = floor(300 / 64) * 64 = 256
  3. Ya = -64 * tan(-2.094395102393195) = -110.85
  4. By = 400 + ((300 - 256) * tan(2.094395102393195)) = 323.78
  5. Bx = 256 - 1 = 255
  6. ¿Hay pared en [3, 5]? No
  7. Bx = 191, By = 212.93
  8. ¿Hay pared en [2, 3]? No
  9. Bx = 127, By = 102.08
  10. ¿Hay pared en [1, 1]? No
  11. Bx = 63, By = -8.77
  12. ¿Hay pared en [0, -1]? Si (porque se sale de las coordenadas del mapa)
  13. El resultado es [63, -8.77]

Distancia

Ya tenemos la colisión horizontal y la colisión vertical. Lo que sigue es mucho más sencillo: ¿cual es la más cercana?

Pitágoras my dude al rescate:

$$a^2 + b^2 = c^2 $$

$$distancia = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2} $$

Entonces la distancia a la colisión horizontal es:

$$dh = \sqrt{(300 - 63.46)^2 + (400 - 127)^2} $$

Y a la colisión vertical:

$$dv = \sqrt{(300 - 63)^2 + (400 + 8.77)^2} $$

dh = 361.22
dv = 472.50
d = 361.22

La distancia mas corta es la distancia a la colisión horizontal.

Código de ejemplo

El algoritmo anterior lo podemos implementar en 4 funciones:

(defn- h-intersect
  [pos angle unit]
  (let [[x y] pos
        tan-a (Math/tan angle)
        Ya (if (pos? angle) (- unit) unit)
        Xa (if (zero? tan-a) Ya (/ Ya (Math/tan (- angle))))
        Ay (if (pos? angle)
             (* (Math/floor (/ y unit)) unit)
             (+ (* (Math/floor (/ y unit)) unit) unit))
        Ax (+ x (/ (- y Ay) tan-a))
        Ay (if (pos? angle) (dec Ay) Ay)]
    (loop [Ax Ax Ay Ay]
      (if (wall? [Ax Ay] unit)
        [Ax Ay]
        (recur (+ Ax Xa) (+ Ay Ya))))))
        
(defn- v-intersect
  [pos angle unit]
  (let [[x y] pos
        half-pi (/ Math/PI 2.0)
        Xa (if (< (- half-pi) angle half-pi) unit (- unit))
        Ya (* Xa (Math/tan (- angle)))
        Bx (if (< (- half-pi) angle half-pi)
             (+ (* (Math/floor (/ x unit)) unit) unit)
             (* (Math/floor (/ x unit)) unit))
        By (+ y (* (- x Bx) (Math/tan angle)))
        Bx (if (< (- half-pi) angle half-pi) Bx (dec Bx))]
    (loop [Bx Bx By By]
      (if (wall? [Bx By] unit)
        [Bx By]
        (recur (+ Bx Xa) (+ By Ya))))))
        
(defn distance
  [[x y] [x-i y-i]]
  (Math/sqrt (+ (Math/pow (- x x-i) 2) (Math/pow (- y y-i) 2))))
        
(defn find-intersect
  [pos angle unit]
  (let [[x-h y-h :as h-int] (h-intersect pos angle unit)
        [x-v y-v :as v-int] (v-intersect pos angle unit)
        h-dist (distance pos h-int)
        v-dist (distance pos v-int)]
    (if (< h-dist v-dist) h-dist v-dist)))

Demo

El demo se manipula utilizando las siguientes teclas:

  • Flechas izquierda / derecha: modifican la rotación.
  • w a s d: modifican la posición (arriba, abajo, strafe).

No creo que haga mucha falta explicarlo. Se lanzan los rayos igual al demo 2, solo que en vez de una distancia fija de 200, estamos calculando la distancia de cada rayo de acuerdo a las colisiones.

En esta ocasión no voy a poner el código completo; pienso subirlo en un futuro no muy lejano a algún repositorio para que lo puedan consultar. Sin embargo con las funciones de la sección anterior, en conjunto con el código de las entregas anteriores debería ser relativamente sencillo de replicar.

Finalmente, si presionan la barra de espacio pueden habilitar / deshabilitar el bug que sucede cuando se olvidan de restar 1 cuando se calcula la celda de la colisión (intenten proyectar los rayos entre los dos cuadros que se tocan por las esquinas)

Conclusión

Aunque seguimos en 2D, ya tenemos todos los elementos necesarios para crear una vista en 3D. El demo que se presentó en este artículo lo hice (en una versión más sencilla) para ayudarme a arreglar un problema con mi primer intento del raycaster.

Necesitaba una manera de ayudarme a encontrar el problema, pero que fuera más sencilla y eficiente que estar viendo largos listados de números y coordenadas. Una vez que pude visualizar el mapa en 2D y cómo interactúan los rayos con la geometría del mismo, fue obvio cual era el problema. Espero que les ayude a hacer una imagen mental de cómo se ve el mundo en 2D, y cual sería su proyección en 3D.

La parte complicada de un raycaster es determinar los cruces y detectar las colisiones, aunque como vimos basta con matemáticas simples. Nada de cálculos en 3D, solo operaciones básicas y funciones trigonométricas.

En la siguiente entrega vamos a romper la barrera de la segunda dimensión. Es como si extendiéramos nuestra mano y jaláramos hacia arriba el mapa que tenemos actualmente.

Lo más interesante de todo es que verán que lo que sigue es mucho más sencillo.