Implementación de un raycaster en Bash

 (github.com/izabera)
2 puntos por GN⁺ 2024-12-22 | 1 comentarios | Compartir por WhatsApp
  • Un raycaster implementado en Bash: un demo pseudo-3D basado en terminal donde se puede rotar y mover con las flechas, y salir con q
  • La implementación es, en gran parte, un port del tutorial de raycasting de Lode Vandevenne, y todas las matemáticas se procesan con enteros escalados por 64K, sin punto flotante
  • La mayor limitación es el rendimiento de Bash: si se ejecuta un comando por píxel o se mantiene el estado de la pantalla en arreglos o cadenas, resulta difícil imprimir dentro del tiempo de cada frame
  • Para mostrarlo en terminal usa el Unicode half block y color de primer plano/fondo de 24 bits para duplicar de forma efectiva la resolución vertical, aunque eso implica tener que conocer también el color de los píxeles adyacentes
  • En la hoja de ruta ya están terminados fluid movement, decent framerate, parallel rendering, kitty keyboard protocol y un prototipo inicial de sound; siguen pendientes textures, sprites, enemies, particles, multiplayer y más

Raycaster de terminal hecho en Bash

  • Este proyecto es un raycaster que corre en Bash y renderiza una pantalla pseudo-3D dentro de la terminal
  • Los controles permiten rotar y moverse con las flechas, y salir con q
  • Hay más capturas y videos en el álbum de Imgur
  • La implementación es, en gran parte, un port del tutorial de raycasting de Lode Vandevenne

Restricciones que hicieron difícil la implementación

  • El mayor problema es que Bash es lento
    • Señala que incluso si hubiera que ejecutar un solo comando por píxel, sería difícil lograr un acceptable frame rate
    • Aunque se mantenga el estado de la pantalla como un arreglo de colores, el acceso a un elemento arbitrario del arreglo es lineal en tiempo, lo cual también causa problemas
    • Incluso si el estado de la pantalla se guarda en una sola cadena larga, acceder al carácter número n también es lineal en tiempo aun con LANG=C, así que solo leerla para volcarla a pantalla puede tardar más que un frame completo
  • Bash no tiene soporte para punto flotante ni acceso a bibliotecas de funciones matemáticas
    • Todas las matemáticas se hacen con enteros
    • Los valores enteros se escalan por 64K para poder calcular
  • Si se usa un carácter como si fuera un píxel en la terminal, el resultado no se ve bien, así que se usa Unicode half block
    • Se especifican distintos colores de primer plano y de fondo para duplicar de forma efectiva la resolución vertical
    • No hay manera de actualizar solo uno de los dos colores en una celda
    • Tampoco hay manera de consultar el color actual de la celda, y en Bash incluso hacer esa consulta sería demasiado lento
    • Por eso, cada vez que se escribe un píxel, hace falta conocer el color del píxel adyacente

Problemas de terminal y de entrada/salida

  • En un lenguaje lento como Bash, actualizar toda la terminal de una sola vez no es algo sencillo
  • La mayoría de las terminales no están diseñadas para videojuegos, así que no se puede comprobar el estado actual de las teclas presionadas
    • Normalmente solo se puede obtener la entrada de una sola tecla mantenida
    • La repetición de entrada se debouncea lentamente y el límite de entrada continua es bajo, así que puede darse el caso de obtener solo unas 5 o 6 teclas por segundo
    • También es difícil obtener varias teclas simultáneas que no sean modificadoras
    • Indica que kitty keyboard protocol resuelve este problema
  • Llenar la terminal con color requiere mucho volumen de datos
    • Con el tamaño de fuente habitual del autor, se generan alrededor de 10 MB/s de I/O
  • Bash no usa una sola syscall al imprimir una cadena con varios saltos de línea
    • Este proyecto no imprime \n, sino que mueve el cursor de otra manera

FAQ y requisitos de ejecución

  • Si al cambiar el tamaño de la ventana se rompe, parpadea demasiado o no se ve bien en cierta terminal, pide abrir un issue
  • Si el CPU se calienta demasiado o una computadora vieja se pone lenta, recomienda bajar la resolución o ajustar la variable de entorno FPS a menos de 30
    • Se sabe que Microsoft Defender reduce bastante el rendimiento, por lo que sugiere desactivarlo
  • Responde que no funciona en versiones anteriores a Bash 5.2
  • No es código hecho solo con Bash puro
    • Al iniciar llama una vez a stty para desactivar el echo
    • Al salir llama una vez a stty para volver a activar el echo
    • Después de terminar, algunas estadísticas se recopilan con otras herramientas

Estado de la hoja de ruta

  • Elementos completados

    • semi-accurate pseudo 3d

      • fluid movement
      • decent framerate
      • parallel rendering
      • 24 bit colours
      • kitty keyboard protocol
      • framerate-independent speed
      • sound, aunque todavía es un prototipo muy inicial
      • dynamic wall colours
      • dynamic map; por ahora no cambia por eventos, pero técnicamente es dinámico
      • basic animations effects for walls
      • basic on-screen minimap
      • Elementos pendientes

    • mouse support

      • textures
      • sprites
      • objects/enemies
      • particles
      • better perf
      • multiplayer

Lecturas relacionadas

1 comentarios

 
GN⁺ 2024-12-22
Comentarios de Hacker News
  • Esto es realmente genial. Me preguntaba cómo dibujaba sin hacer un echo por cada píxel, y el método es muy ingenioso.
    Como el juego no es 3D “de verdad”, solo necesita ejecutar el trazado de rayos una vez por columna y dibujar apenas unas líneas correspondientes al cielo, el pasto y los objetos reales.
    Lo hace imprimiendo en la terminal, con repetición de cadenas, una cadena del tipo “dibuja este píxel y muévete una celda hacia abajo” tantas veces como sea necesario.
    No es para Bash, pero estaba pensando en crear un motor de renderizado de vóxeles en otro entorno con recursos de cómputo limitados, y seguro que aquí puedo encontrar algo útil.
  • Si te preguntabas si existe un proyector de rayos escrito en MS Batch, también está este: https://github.com/nTh0rn/batch-raycaster
  • Es una lástima que stty requiera hacer fork. Quizás el próximo proyecto sea usar Bash y rowhammer para llamar al ioctl necesario sin hacer fork.
  • No sabía que algo así fuera posible en Bash. Alguna vez pensé que manejaba Bash a un nivel bastante avanzado, pero esto es realmente sorprendente.
    No tengo las matemáticas suficientes para entender la implementación, pero solo verlo ya es divertido.
  • Mis scripts de Bash gastan 300 líneas solo en parsear opciones de línea de comandos de todo tipo, cuando en realidad podrían haber mostrado un juego como este en su lugar :-P
  • Sigo sin entender que todavía estemos atados a shells tan absurdamente lentos. Parece pura locura.
    Entiendo que algunas apps necesiten todo tipo de comportamientos extraños de vt100, pero probablemente el 90% de las apps solo escriben en la salida estándar y el error estándar.
    Siento que debería ser posible volcar texto en pantalla más rápido y dejar al otro 10% en un modo de compatibilidad.
    • Los shells son lentos, y Bash en particular, pero no tengo muy claro cómo se conecta eso con lo demás. El shell no participa en absoluto en interpretar secuencias de escape de terminal, y las terminales modernas son bastante rápidas.
      Incluso en una terminal de 350 columnas se puede renderizar la animación, y dadas las limitaciones, sale muy fluida.
      Además, la premisa misma de este artículo es que Bash es un lenguaje inadecuado para la proyección de rayos. Es parecido a implementar bubble sort en CSS.
      Nada impide “poner al otro 10% en modo de compatibilidad”. Se podría verificar que la cadena contenga solo caracteres normales y usar una ruta rápida.
      El problema es que, en el renderizado de texto por software, en realidad no hay una ruta rápida. Igual hay que procesar cosas como ligaduras.
  • “bash es lento”.
    Esa es una de las razones por las que no uso Bash para scripting. Tampoco lo uso de forma interactiva.
    Algunas distribuciones populares de Linux también evitan Bash como shell de scripting.
  • Estaría bueno combinar esto con la implementación de ps sin fork del autor para crear casi una implementación de psDoom sin forks.
    Bromas aparte, es realmente impresionante.
  • Por supuesto, también hay que hacer una mención honorífica al proyector de rayos en awk de hace 9 años: https://github.com/TheMozg/awk-raycaster/tree/master