Implementação de Raycaster em Bash

 (github.com/izabera)
2 pontos por GN⁺ 2024-12-22 | 1 comentários | Compartilhar no WhatsApp
  • Um raycaster implementado em Bash, uma demonstração pseudo-3D baseada em terminal em que você gira e se move com as setas e sai com q
  • A implementação é, em grande parte, um port do tutorial de raycasting de Lode Vandevenne, e toda a matemática é feita com operações inteiras em escala de 64K, sem ponto flutuante
  • A maior limitação é o desempenho do Bash: se executar um comando por pixel ou mantiver o estado da tela em arrays/strings, fica difícil imprimir dentro do tempo de um frame
  • Para a exibição no terminal, usa Unicode half block e cores de primeiro plano/fundo de 24 bits, efetivamente dobrando a resolução vertical, mas com a restrição de precisar conhecer também a cor do pixel adjacente
  • No roadmap atual, fluid movement, decent framerate, parallel rendering, kitty keyboard protocol e um protótipo inicial de sound já foram concluídos; textures, sprites, enemies, particles, multiplayer e outros ainda não foram concluídos

Raycaster de terminal feito em Bash

  • Este projeto é um raycaster que roda em Bash e renderiza uma tela pseudo-3D dentro do terminal
  • Os controles usam as setas para girar e se mover, e q para sair
  • Mais capturas de tela e vídeos estão no álbum do Imgur
  • A implementação é, em grande parte, um port do tutorial de raycasting de Lode Vandevenne

Restrições que dificultaram a implementação

  • O maior problema é que Bash é lento
    • O autor afirma que, mesmo se for preciso executar apenas um comando por pixel, é difícil obter uma taxa de quadros aceitável
    • Mesmo mantendo o estado da tela em um array de cores, o acesso a elementos arbitrários do array é em tempo linear, o que vira um problema
    • Mesmo mantendo o estado da tela como uma única string longa, acessar o n-ésimo caractere é em tempo linear mesmo com LANG=C; só ler para despejar na tela pode levar mais tempo que um frame
  • Bash não tem suporte a ponto flutuante nem acesso a uma biblioteca de funções matemáticas
    • Toda a matemática é feita com inteiros
    • Os valores inteiros são ampliados por uma escala de 64K para os cálculos
  • Usar um caractere como se fosse um pixel no terminal não fica bom, então o projeto usa Unicode half block
    • Ao definir cores diferentes de primeiro plano e de fundo, a resolução vertical é efetivamente dobrada
    • Não há como atualizar apenas uma das duas cores em uma célula
    • Também não há como consultar a cor da célula atual e, em Bash, até essa consulta seria lenta demais
    • Por isso, sempre que escreve um pixel, é preciso saber a cor do pixel adjacente

Problemas de terminal e entrada/saída

  • Atualizar o terminal inteiro de uma vez usando Bash, uma linguagem lenta, não é algo simples
  • A maioria dos terminais não foi projetada para videogames, então não permite testar o estado das teclas atualmente pressionadas
    • Normalmente, só dá para obter a entrada de uma única tecla sendo mantida pressionada
    • A repetição de entrada passa por debounce lento, e o limite de entrada contínua também é baixo, levando a situações de cerca de 5 a 6 caracteres por segundo
    • Também é difícil obter a pressão simultânea de várias teclas que não sejam modificadoras
    • O autor afirma que o kitty keyboard protocol resolve esse problema
  • Preencher o terminal com cores exige muitos dados
    • No tamanho de fonte usual do autor, isso gera cerca de 10 MB/s de I/O
  • Bash não usa uma única syscall ao imprimir strings com várias quebras de linha
    • Este projeto não imprime \n e move o cursor de outra forma

FAQ e requisitos de execução

  • Se a janela quebrar ao ser redimensionada, se houver muita cintilação ou se a aparência ficar ruim em um terminal específico, o autor pede para abrir uma issue
  • Se a CPU esquentar muito ou se um computador antigo ficar lento, a orientação é reduzir a resolução ou definir a variável de ambiente FPS para menos de 30
    • Como o Microsoft Defender é conhecido por degradar bastante o desempenho, é sugerido desativá-lo
  • O autor responde que o projeto não funciona em Bash anterior à versão 5.2
  • O código não é feito apenas de Bash puro
    • Na inicialização, chama stty uma vez para desligar o echo
    • Ao sair, chama stty uma vez para religar o echo
    • Após o encerramento, algumas estatísticas são coletadas com outras ferramentas

Estado do roadmap

  • Itens concluídos

    • pseudo-3D semi-preciso

      • fluid movement
      • decent framerate
      • parallel rendering
      • 24 bit colours
      • kitty keyboard protocol
      • framerate-independent speed
      • sound, mas ainda como um protótipo muito inicial
      • dynamic wall colours
      • dynamic map, atualmente não é alterado por eventos, mas é tecnicamente dinâmico
      • basic animations effects for walls
      • basic on-screen minimap
      • Itens não concluídos

    • mouse support

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

Leituras relacionadas

1 comentários

 
GN⁺ 2024-12-22
Comentários do Hacker News
  • Isso é muito bom. Eu estava curioso para saber como ele desenhava sem fazer um echo para cada pixel, e o método é bem inteligente.
    Como o jogo não é 3D “de verdade”, ele só precisa executar o rastreamento de raios uma vez por coluna e desenhar apenas algumas linhas correspondentes ao céu, à grama e aos objetos reais.
    A ideia é imprimir no terminal uma string do tipo “desenhe este pixel e mova uma posição para baixo”, usando repetição de strings pelo número de vezes necessário.
    Não é para Bash, mas eu estava pensando em criar um motor de renderização de voxels em outro ambiente com recursos computacionais limitados, e acho que certamente vou encontrar algo útil aqui.
  • Se você estava se perguntando se existe um projetor de raios escrito em MS Batch, também tem este: https://github.com/nTh0rn/batch-raycaster
  • É uma pena que stty precise de fork. Talvez o próximo projeto seja chamar o ioctl necessário com Bash e rowhammer, sem fork.
  • Eu não fazia ideia de que algo assim era possível em Bash. Já cheguei a achar que eu sabia lidar com Bash em um nível bastante avançado, mas isso é realmente impressionante.
    Não tenho matemática suficiente para entender a implementação, mas só de ver já é divertido.
  • Meus scripts Bash gastam 300 linhas só fazendo parsing de opções de linha de comando, quando na verdade poderiam estar mostrando um jogo desses no lugar :-P
  • Ainda não consigo entender como continuamos presos a shells tão absurdamente lentos. Parece pura insanidade.
    Entendo que alguns apps precisem de todos os comportamentos peculiares do vt100, mas provavelmente 90% dos apps só escrevem na saída padrão e no erro padrão.
    Deveria ser possível despejar texto na tela um pouco mais rápido e colocar os outros 10% em modo de compatibilidade, não?
    • Shells são lentos, especialmente o Bash, mas não vejo muito bem como o restante do argumento se conecta. O shell não participa em nada da interpretação de sequências de escape de terminal, e terminais modernos são bem rápidos.
      Dá para renderizar animação até em um terminal de 350 colunas, e, considerando as restrições, ela sai bem fluida.
      Além disso, a própria premissa deste texto é que Bash é uma linguagem inadequada para projeção de raios. É parecido com implementar bubble sort em CSS.
      Nada impede “colocar os outros 10% em modo de compatibilidade”. Bastaria verificar se a string contém apenas caracteres normais e usar um caminho rápido.
      O problema é que, na renderização de texto por software, na prática não existe um caminho rápido. Ainda é preciso lidar com coisas como ligaduras.
  • “Bash é lento.”
    É por isso que esse é um dos motivos pelos quais não uso Bash para scripting. Nem uso interativamente.
    Algumas distribuições Linux populares também evitam Bash como shell de scripting.
  • Seria legal juntar isso com a implementação de ps sem fork do autor para criar quase uma implementação de psDoom sem fork.
    Brincadeiras à parte, é realmente muito legal.
  • Claro que o projetor de raios em awk de 9 anos atrás também merece uma menção honrosa: https://github.com/TheMozg/awk-raycaster/tree/master