Motor 3D para GameBoy Advance: Consiguiendo lo imposible

Versión 2:
Descarga ROM y código fuente aquí.
Esta versión ya se mueve fluida a 60fps y permite girar la cámara.
Cambios:
Aparte de las optimizaciones de la versión 1, he añadido mas optimizaciones, y he implementado la rotación de la camara.
-Todo el código es copiado a la RAM y se ejecuta desde ahí. Se usa código ARM en vez de Thumb.
-Para ganar mas velocidad utilizo el modo5, que baja un poco la resolución y permite tener dos framebuffer en la memoria de video evitando tener que usar la RAM para luego copiarla a la VRAM en cada frame. También uso las técnicas de escalado y desplazamiento de la GBA para crear un par de frames intermedios mientras se renderiza el siguiente frame final.

Para la rotación utilizo aproximaciones rápidas de lo que serían los auténticos cálculos de la rotación. Ademas, cada vez que se gira, desplazo la posición de referencia para evitar aun mas cálculos al transformar las coordenadas durante el dibujado.

Para evitar aun mas perdidas de velocidad, he replicado la función crítica Render para cada angulo posible, de forma que las transformaciones de coordenadas están hard-coodeadas dentro de las funciónes Render-n, evitando llamadas a funciones y comprobaciones de angulo cada vez que se procesa un pixel.

Versión 1:
Descarga ROM y código fuente aquí.
La GameBoy Advance fue una de las primeras videoconsolas portatiles que intentó en algunos de sus juegos simular el efecto 3D. Juegos como Driv3r, Asterix y Obelix XXL, o Craxy Taxi. No obstante en la mayoría de dichos juegos el efecto 3D era muy, muy básico. Es por eso que yo, como friki ingeniero informático que soy me puse a investigar de que manera se podría conseguir un motor 3D decente. Tras un día investigando y picando código...¡Este fue el resultado!

Como habréis comprobado, la calidad del efecto 3D casi no se puede comparar con la de ningún otro juego de GBA. El motor es de tipo voxel space y el video fue acelerado algo así como x200 ya que la demo en su versión original (la del vídeo) tardaba 11 segundos en generar cada frame. Esto es debido a la gran cantidad de multiplicaciones y divisiones que debía hacer el motor en cada frame. Para los que no sepáis muy bien como funciona un motor voxel space os lo explico de manera muy sencilla:

Tenemos una imagen de color y otra imagen de profundidad. Dibujamos el entorno desde el frente hacia atras aplicando perspectiva (podeis ver el triangulito con el campo de visión en el GIF), para ello trazamos en la pantalla lineas verticales del color proporcional al pixel horizontal de la pantalla y el pixel horizontal de la linea de campo de visión actual. Esta linea vertical empezará desde la ultima altura dibujada hasta un nuevo valor calculado a partir de la altura en el mapa de profundidad y la distancia con el punto de vista (Si el valor obtenido es menor, no se dibuja la linea).

Optimizando el código:

Pues seguramente la baja potencia del procesador de la GameBoy fue lo que hizo que no apareciera ningún juego usando este tipo de motor, las multiplicaciones y divisiones son muy lentas en su procesador. Estas operaciones son vitales tanto para calcular las posiciones horizontales del campo de vision y pantalla como las de las alturas. ¿Que solucion tenemos? ¡Crear una estructura de datos con estos valores precalculados! En el archivo comprimido podeis encontrar generarmatriz.c que puede ser compilado para PC y usando los datos de matrizalturas.h (compartido con el proyecto devkit) generar una estructura de datos con las alturas precalculadas matrizalturas.raw y posiciones horizontales matrizx.raw las cuales se añaden al ROM. También, para realizar otras divisiones y multiplicaciones con multiplos de 2, utilizo a ser posible las operaciones de desplazamiento << y >> las cuales son mas rápidas.

Ademas, calcularemos el campo de visión menos frecuentemente en posiciones alejadas y limitamos la distancia de dibujado a 512 pixeles.

Estos cambios, junto con otras cuantas optimizaciones de código, permiten tras un gran esfuerzo y sudor conseguir unos gloriosos...

¡5fps!

Lo cual supone aproximadamente un speedup del 3000% y seguiría siendo insuficiente para cualquier juego en condiciones, pero al menos se mueve decentemente.

Se podría decir que la optimización es del 95% ya que los limites técnicos de la consola están ahí. Estas son algunas otras optimizaciones menores posibles que ni me he molestado en hacer:

• Alinear matrizx.raw a 256 bytes cada linea para asi a la hora de leer sus datos podamos cambiar SCREEN_WIDTH*(step-minstep) por (step-minstep)<<8 aunque esto nos hará desperdiciar 16 bytes de memoria en la estructura de datos en la ROM por cada linea.
• Dibujar las lineas verticales una por una, de forma que si una alcanza el valor maximo se haga un break y se pase a la siguiente sin seguir avanzando en profundidad. Solo habría aceleración en los casos que el mapa alcanzase la parte de arriba de la pantalla y la aceleración sería irregular. Habría que almacenar los valores de step en una estructura de datos.
• Si se os ocurriese alguna mas, ¡comentad!

Curiosidad:

Uso de memoria en la demo:

Elemento	Espacio (KB)	Porcentaje	Notas
Código	9.79	0.18%	El corasón de la demo. La parte que controla todo el funcionamiento.
Imagen Background	39.1	0.72%	La imagen del cielo tan bonica para la mitad superior de la pantalla (240x80) a 16 bit bgr555
Mapa colores	2048	38.07%	1024x1024 a 16 bit bgr555
Mapa profundidad	1024	19.03%	1024x1024 a 8 bit (valores 0-255)
Matriz x	238	4.42%	Valores para cada pixel horizontal (1-240) en cada profundidad (8-512) de la posición horizontal del campo de visión (valores de 16 bit)
Matriz Alturas	2021	37.57%	Valores de altura en la pantalla de 8 bit para cada altura del mapa (0-255) en cada profundidad (8-512) para distintas alturas de camara posibles (16)
Total	5379.89	100%