Tutorial de Ray casting 2: Rayos y retruécanos

Escrito por el 8 noviembre, 2017

Pues aquí estamos otra fría tarde de noviembre par continuar programando nuestro propio wolfenstein. Hasta el momento, teníamos una primera versión donde únicamente podíamos movernos por el mapa y chocar alegremente con las paredes, y todo aliñado con una vista cenital del mapa al estilo del tutorial de tiles que hice cuando aún era mas joven, feliz, e incluso tenía mas pelo. Lo que pretendo conseguir hoy es llegar a esta versión:

Como viene siendo habitual, aquí teneis el enlace para probar esta versión, y aquí su correspondiente código en github.

Ray casting para dummies

Si has llegado hasta aquí, seguro que aún te estás preguntando ¿cómo diablos dibujo un mundo 3d sin usar un motor 3d? Pues la idea que hay detrás de ello es tan simple y sencilla de entender, que el que la ideó tuvo que ser un genio. El jugador es una coordenada en el plano. Que mira en una dirección, que es un vector normalizado (módulo o longitud de uno). Ese plano es un mapa de tiles, es decir, un array bidimensional con unos, que representan paredes, y ceros, que representan espacio vacío por el que puedo caminar. Ojo, la técnica de ray casting se puede aplicar a otros tipos de escenarios, pero usar mapa de tiles es la forma mas sencilla de entender. Bueno, volviendo al tema. En un mapa cenital, la persona que juega al juego, lo ve todo. Pero en un FPS, la visión del jugador es mas limitada. En concreto, el campo de visión del jugador se le conoce como FOV (field of view, traducción literal). Básicamente el fov es el ángulo de visión que tiene el jugador, compuesto por un ángulo vertical y otro horizontal. Una persona real tiene un FOV vertical de 150 grados, y un FOV horizontal de 200 (cada ojo tiene su propio FOV, así que el total es la unión de ambos conos). Los juegos 3D modernos usan ambos ángulos, consiguiendo distintos efectos cambiando los valores de esos ángulos. A continuación, vemos una imagen que dejará mas claro los conceptos a los que me refiero.

Pues bien, la primera idea es descartar el ángulo vertical, y quedarnos sólo con el ángulo horizontal para calcular el FOV del jugador. Así que nos queda un FOV mas sencillito que tiene esta pinta:

De acuerdo, pero seguramente aún no tengas ni idea de en qué medida te ayuda todo esto para dibujar en 3D. Pues bien, llegó el momento: La idea es tirar un montón de rayos que cubran todo el FOV del jugador posible, y calcular con qué chocan y a qué distancia lo hace. El FOV es un ángulo horizontal, y la dirección del jugador es exactamente la mitad de dicho FOV. Así que es evidente que la mitad del ángulo del FOV queda a la izquierda de mi vector dirección, y la otra mitad del FOV está a la derecha. Así que reparto el número de rayos que tiro para cubrir proporcionalmente mi FOV. De ahí que los valores más importantes sean:

  • Ángulo del FOV
  • Número de rayos que casteo

Así que lo primero que hay que hacer es determinar los ángulos con los que tirar cada rayo, que coincidan con el FOV del jugador, y calcular a qué distancia chocan con alguna pared. El primer punto debería ser sencillo para todos los que estén leyendo esto y usen la cabeza para algo más que llevar gorra, pero el segundo punto es algo más complicado. Pero antes de entrar en materia, vamos a seguir con la explicación. Una vez que tienes calculados todos los rayos, y la distancia a la que chocan, ¿qué? Pues… ¡dibujo rectángulos cuyo ancho son el ancho del canvas dividido por el número de rayos que he tirado, y cuya altura es proporcional a la distancia a la que están! Cuanto más cerca choque el rayo, mas alto pinto el rectángulo. Y cuanto más rayos tire, mejor definición tendré del mapa, a costa de realizar mas cálculos, evidentemente. Si no lo ves, esta imagen que he robado de un blog de un guiri ayudará:

Y ya está, un mundo pseudo 3D en el que no importa lo grande que sea tu mapa de tiles, el tiempo de dibujado es constante y depende totalmente del número de rayos que casteas.

De vuelta al código

¿Cómo programamos ésto? Pues espero que te lo hayas imaginado: Una clase que se dedique sólo a calcular los rayos, a partir del mapa y de la posicion dirección del jugador. Despues de mucho pensar, he decidido llamarla con el superoriginal nombre RayCasting.

Como ya dije antes, defino el ángulo FOV en radianes, el número de rayos que quiero castear, y le paso el mapa. Bueno, en lugar del mapa, lo que le pasó es una función que comprobará si una coordenada concreta, colisiona con alguna pared del mapa. La veremos con mas detenimiento cuando llegue el momento.

Y al actualizar lo que hará la clase es calcular todos los impactos de los rayos con el escenario y a la distancia que lo hacen. Cada rayo es un objeto anónimo de javascript que contiene una propiedad ini vector con la coordenada de inicio del rayo (el del jugador, siempre), otra propiedad end con la coordenada donde el vector acaba chocando con una pared, y la distancia o longitud que tiene el rayo, que es lo mismo que decir a qué distancia está la pared con respecto al jugador.

En este primer intento, nos limitaremos a dibujar los rayos en nuestro ya conocido MiniMapRender.

El funcionamiento es el siguiente:

  1. El juego llamará a este update, durante la fase update del bucle principal. Sus argumentos son la posición y dirección del jugador.
  2. Este update calculará el ángulo de salida de cada rayo, y llamará a una función privada que calculará la distancia y posición con la que el rayo, definido por una posición inicial (la misma que el jugador) y un ángulo de salida, chocará con una pared
  3. Esta clase ray casting se la pasaremos al render, y el render lo que hará es llamar al getRays, para dibujar los rayos, que son las líneas rojas de la demo.

Calcular el ángulo de cada rayo es trivial, como podemos ver en el código de arriba. Calcular cuando chocan no lo es.

Calculando rayos

Estuve meditando bastante tiempo cómo hacerlo. Mis conocimientos de trigonometría rayan el analfabetismo, asi que me dije ¿Y si voy haciendo crecer el vector de cada rayo gradualmente, y veo si está dentro de un tile? Mi clase vector tiene métodos de sobra para ir haciendo que crezca, que básicamente es ir multiplicándolo por el número escalar 1.001, 1.002, 1.003, etc. Pero enseguida descarté la idea. La cantidad de cálculos sería bestial, y no me garantiza obtener la coordenada exacta donde el rayo choca con la pared, que en palabras más concretas, significa que el rayo cambia de tile. Esta imagen lo deja mas claro:

Lo que interesa calcular es la coordenada exacta de cuando el vector cambia de tile, y comprobar si el tile donde entra, es una pared o no. Si es una pared, ya he terminado: calculo la distancia y la devuelvo junto a las coordenadas del rayo. Si no lo es, sigo avanzando.

¿Y cómo calcular cuando un vector cambia de tile? Pues de nuevo hice lo lógico. Puse “ray casting tile javascript” en google, y me llevó a esta librería javascript que implementa el código que se detalla en este pdf, que a su vez está basado en el algoritmo de muestreo gráfico DDA, y lo plagié sin sentimientos. Este es el resultado:

La idea general es determinar el momento transversal t en el que el vector cambia de coordenada en el eje X o en el eje Y. Para ello necesito obtener la parte entera de la coordenada X e Y, que iremos almacenando en int_x e int_y, el crecimiento a sumar en cada muestreo para X e Y en step_x y step_y, el factor de crecimiento en delta_tx y delta_ty, la distancia que queda para alcanzar el siguiente momento t, en dist_x y dist_y, y la distancia avanzada hasta el momento, en max_tx y max_ty.

Todo el mapa está delimitado por paredes, así me aseguro que el rayo siempre chocará con una pared. Como estoy seguro de ello, me permito el lujo de usar un bucle infinito para ir calculando el muestreo. Detecto si estoy colisionando con alguna pared, con la función anónima que se le pasa al constructor desde la clase principal del juego. Si hay colisión, obtengo la coordenada del choque y la distancia con pitágoras, usando los valores previamente calculados. Y si no lo estoy, entonces actualizo esos valores dependiendo de la coordenada que vaya más retrasada.

Lo mejor es que ayudados con el depurador de código de chrome, añadáis algunos breakpoints en el código, y vayáis viendo paso a paso cómo se va calculando, para que todo quede mas claro.

¿Cómo he instanciado esta clase? Pues veamos cómo ha quedado la clase principal del juego.

Lo único nuevo es la instanciación de la nueva clase RayCasting, y cómo se la paso al render, para que la dibuje. Lo mas destacable es cómo le paso la función que detecta colisiones al ray casting. Como dije antes, no es mas que una función con los argumentos X e Y, que devuelve un booleano que indica si esa coordenada es una pared. Al no pasarle el laberinto, permite que la clase RayCasting esté desacoplada de cualquier escenario, y me la pueda llevar a otro juego.

Actualizarla no tiene nada especial.

Y el render que la dibuja, pues también es poca cosa. Los cambios que quedan son el HTML extra que he metido para que desde la demo se pueda cambiar los valores del FOV y del número de rayos al vuelo, pero a estas alturas de la vida, no creo que necesite explicar el código necesario para hacerlo. Si no es así, deberías bajar un poco el listón y empezar por tutoriales menos ambiciosos.

Inicialmente, el HTML arranca el juego mandando un FOV inicial de 60 grados y 320 rayos. Con los controles de la demo podéis ir variando los valores y viendo los resultados.

Y por fin, ha llegado el momento de renderizar en 3D. Pero esto lo dejaremos para el siguiente tutorial, que probablemente sea el mas corto de la larga trayectoria con tan poca actividad de la historia de este blog.

Etiquetas: , ,

¿Tienes algo que decir?

Gestionado con Wordpress y Stripes Theme Entradas (RSS) | Comentarios (RSS)