Adaptive Tile Refresh de Commander Keen

 (fabiensanglard.net)
2 pontos por GN⁺ 2023-07-29 | 1 comentários | Compartilhar no WhatsApp
  • Adaptive Tile Refresh (ATR) é a técnica de rolagem criada para Commander Keen 1~3 evitar a lenta atualização de tela cheia do EGA, redesenhando apenas os tiles que mudaram em vez da tela inteira
  • O modo EGA Dh armazena a tela de 320x200 com 16 cores dividida em 4 planos (C0~C3), e escrever os 32 KiB da tela inteira a cada frame pelo barramento ISA limitava o desempenho a cerca de 5 fps, dificultando atualização a 60 Hz
  • O ATR usa os registradores CRTC_START, OFFSET e PEL para lidar com o deslocamento vertical e horizontal dentro de uma tela virtual e, ao tocar a borda, faz um jolt para recentralizar a referência da tela, sobrescrevendo na VRAM apenas os tiles necessários
  • O custo do jolt depende da quantidade de tiles a redesenhar; no exemplo de Commander Keen 1, apenas 40 tiles de 250 mudaram, então só 16% da tela inteira foi redesenhada, e o desempenho dependia de mapas com muitos tiles repetidos
  • Commander Keen 4~6 trocou o ATR por um método que usa o wraparound da abertura de 64 KiB de VRAM para continuar fazendo panning e desenhar apenas as faixas de borda recém-reveladas; em algumas placas Super VGA, isso causou problemas de compatibilidade ao entrar em memória não inicializada

Limites de largura de banda encontrados no EGA

  • Commander Keen funcionava melhor em PCs com EGA (Enhanced Graphics Adapter), e a programação gráfica era feita por meio de registradores de configuração e de uma janela de memória de 64 KiB mapeada para a VRAM
  • O EGA armazena os dados internos em 4 planos: C0, C1, C2, C3
    • C0 guarda o bit menos significativo (LSB) de cada valor de pixel de 4 bits
    • C3 guarda o bit mais significativo (MSB)
    • Cada plano tem 200 linhas, com 40 bytes por linha
  • A estrutura de 4 bancos foi projetada para fornecer largura de banda suficiente para acompanhar a tela CRT, e o CRTC lê 4 bytes em paralelo
  • O modo EGA Dh usado por Commander Keen fornece resolução de 320x200 e 16 cores
    • Ele não usa o esquema do modo 10h, que recompõe tintas a partir de 64 valores de cor
    • Mesmo no modo Dh, ainda é possível alterar as cores da paleta dentro do conjunto básico de 16 cores, algo usado nos fades simples de entrada e saída de Commander Keen

O redesenho de tela cheia que o Adaptive Tile Refresh evitou

  • O principal gargalo que o ATR resolveu era a largura de banda
  • Escrever a cada frame os valores de 4 bits dos 320x200 pixels, cerca de 32 KiB, era pesado demais para o barramento ISA
  • Um loop simples atualizando a tela inteira em toda iteração ficava em torno de 5 quadros por segundo
  • O EGA também oferece maneiras de escrever nos 4 bancos ao mesmo tempo, mas embora isso ajude em tarefas como limpar a tela ou duplicar colunas em Wolfenstein 3D, não se encaixava no problema de rolagem de Commander Keen

Rolagem suave feita com registradores

  • O ATR primeiro cria na VRAM uma tela virtual maior do que a área visível e move a região exibida alterando o valor de CRTC_START, que define de onde o CRTC começa a ler
  • A rolagem vertical é relativamente simples
    • Adicionando 16 linhas acima e 16 abaixo da tela visível, cada plano passa a usar 40 x 232 = 9.280 bytes
    • Ao mover a tela uma linha para cima, CRTC_START aumenta 40 bytes
    • Ao mover uma linha para baixo, CRTC_START diminui 40 bytes
  • A rolagem horizontal usa em conjunto os registradores OFFSET e PEL
    • Ajustar OFFSET para 2 adiciona 16 bytes de padding entre linhas, criando margem de 16 pixels em cada lado da tela virtual
    • Aumentar CRTC_START em 1 faz a imagem se mover em passos de 8 pixels por causa da estrutura em planos, o que é grosseiro demais
    • O Horizontal Pel Panning, isto é, o registrador PEL, permite pular até 7 bits após CRTC_START, tornando possível a rolagem horizontal por pixel
  • Na prática, o movimento lateral ajusta CRTC_START com o valor da coordenada dividido por 8 e ajusta PEL com o resto da coordenada (% 8)

Jolt e atualização parcial por tiles

  • Ao alcançar a borda da tela virtual, o ATR executa um jolt para recentralizar a tela virtual
  • Como redesenhar tudo levaria cerca de 200 ms e derrubaria a taxa para 5 fps, o jolt funciona sobrescrevendo apenas os tiles alterados em vez de fazer um redesenho completo
  • As fases de Commander Keen são feitas com tiles de 16x16
    • Quando o artista desenha os tiles, o sistema de build atribui um ID único a cada tile
    • O level designer posiciona esses IDs em um editor 2D para montar o mapa
    • O motor acompanha quais IDs de tile estão presentes na tela virtual
  • No momento do jolt, ele compara os IDs de tile do estado atual da tela virtual com o estado-alvo depois de recentralizar
    • Tiles iguais são ignorados
    • Apenas os tiles diferentes são sobrescritos na VRAM
  • A eficiência do jolt é inversamente proporcional ao número de tiles que precisam ser redesenhados, então os designers precisavam montar tilemaps com muitos tiles repetidos
  • No exemplo de Commander Keen 1, após mover suavemente para a direita e atingir o fim da tela virtual, um jolt de 16 pixels para a esquerda alterava apenas 40 tiles de 250
    • A parte redesenhada correspondia a 16% da tela inteira
  • Sobre o fundo, uma camada de sprites é desenhada
    • O motor mantém uma lista das coordenadas de tiles sujos sobrescritos pelos sprites
    • A cada novo frame, ele percorre a lista suja, restaura os tiles de fundo e então redesenha os sprites

Double buffer e o drifting da segunda trilogia

  • Para evitar artefatos visuais, todo o sistema era duplicado em dois framebuffers
    • Enquanto o CRTC lê um deles, o outro pode ser escrito em outra posição da VRAM
    • Cada buffer usa (320 + 32) * (200 + 32) * 4 / 8 = 40.832 bytes
    • O total do double buffer é 40.832 * 2 = 81.664 bytes, acima dos 64 KiB da placa EGA original da IBM
  • Segundo VileR, somente a placa IBM EGA original vinha com 64 KiB; a maioria dos clones EGA lançados por volta de 1986~1987 trazia 256K, e na época do lançamento de Commander Keen quase não havia placas EGA com menos de 256K
  • Em Commander Keen 1~3, os padrões repetitivos exigidos pelo ATR aparecem com destaque na tela, mas em Commander Keen 4~6 isso já não é tão evidente
  • A segunda trilogia de Keen aproveita o comportamento de wraparound em que CRTC_START, ao chegar ao fim de um bloco de 64 KiB, volta para o começo do bloco
    • A tela continua fazendo panning e desenha apenas a linha de tiles da borda recém-exposta
    • Como o jolt desaparece, diminui a necessidade de criar campos repetitivos com cores parecidas
  • Isso não foi tanto um novo recurso, mas uma melhoria para eliminar o jolt
    • Os dois elementos do double buffer fazem drift pelo espaço da VRAM na mesma velocidade, então não se sobrepõem
    • Na maioria dos casos, isso funcionava bem
  • Algumas placas Super VGA apresentavam problemas
    • Em implementações fora do padrão e com mais memória, em vez de ocorrer o wraparound do fim para o começo, o acesso podia entrar em memória real não inicializada
    • Em vez de lidar separadamente com várias placas não padronizadas, Carmack preferiu uma solução mais simples: ao chegar ao fim da tela, aceitar um hitch e copiar a tela inteira para cima
  • É possível que essa técnica de drifting tenha impedido o uso de cópias rápidas de VRAM para VRAM com tiles e sprites armazenados na própria VRAM, mas como a quantidade desenhada por frame era muito pequena, isso provavelmente não chegou a ser um grande problema

Leituras relacionadas

1 comentários

 
GN⁺ 2023-07-29
Opiniões do Hacker News

  • A suavidade da rolagem de Commander Keen 4–6 ficou por muitos anos sem concorrentes no PC, mesmo depois que os jogos passaram a usar gráficos de 256 cores.
    Graças ao trabalho técnico impressionante de John Carmack e à arte de Adrian Carmack com paleta de 16 cores, a id acabou criando, por um período nos anos 1990, os jogos de plataforma mais bonitos do PC.
    Adrian Carmack não é parente do Carmack mais famoso, mas o considero um mestre oculto da paleta de 16 cores.

    • É meio estranho perceber que todos os jogos clássicos de Commander Keen foram desenvolvidos e lançados entre dezembro de 1990 e dezembro de 1991.
      O ritmo de evolução dos gráficos e da jogabilidade foi realmente enorme.
      A mudança desde o primeiro jogo: https://en.wikipedia.org/wiki/Commander_Keen_in_Invasion_of_...
      A mudança até o último jogo: https://en.wikipedia.org/wiki/Commander_Keen_in_Goodbye,_Gal...
      Joguei na época, quando era criança, e tinha esquecido que as coisas estavam acontecendo tão rápido assim.
    • Se for para escolher o jogo de plataforma de PC mais bonito por um período dos anos 1990, eu escolheria Prince Of Persia.
      Não querendo diminuir Commander Keen, mas sinto que os visuais e a dinâmica de jogo de PoP eram incomparáveis para a época.
      Quando joguei pela primeira vez, por volta dos 7 anos, pareceu mágico, e ele ainda é meu jogo de plataforma favorito, então admito que sou enviesado.
      Claro, PoP não tem rolagem nenhuma, e essa parte é a magia negra de Commander Keen.
    • Talvez seja uma perspectiva de quem olha em retrospecto, mas boa parte desse desenvolvimento inovador parece bem simples em comparação com o desenvolvimento atual.
      “A memória é lenta, então vamos redesenhar só o que mudou” hoje é uma ideia quase óbvia.
      Ainda assim, as otimizações dos episódios 4–6 são interessantes. Também é curioso que nos episódios 1–3 eles fizeram todo aquele trabalho partindo da suposição de que o buffer não fazia wrapping, mas, na prática, ele fazia, tornando esse trabalho inútil.
    • E Jazz Jackrabbit? Aquele jogo também tinha uma rolagem VGA realmente suave.

  • Já fiz um jogo baseado em tiles no Windows 98 com DirectX 5, e no começo implementei algo parecido com o que o texto descreve.
    A situação era um pouco mais simples porque a tela não rolava, embora muitos tiles pudessem precisar ser redesenhados.
    No fim, removi todo esse código, porque ao perfilar o custo de desenhar a tela inteira em uma placa RIVA TnT, o tempo era tão pequeno que nem dava para medir.
    Ainda bem que perdi a era EGA no desenvolvimento para PC. Acho que, se fosse naquela época, eu não teria terminado nada.

    • Eu, pelo contrário, gostava desse tipo de programação de baixo nível.
      Otimizava usando deslocamentos de bits em vez de multiplicações, escrevia o código essencial em assembly e, conforme os processadores evoluíam, passava a escrever 16 ou 32 bits por vez.
      Como eu tinha pouco material, continuava aprendendo com livros da biblioteca local e disquetes cheios de arquivos txt.
      Eu era jovem demais e inexperiente, então não terminei nada, mas consegui fazer uma rolagem vertical suave, quase fiz a rolagem horizontal funcionar e também implementei double buffering de um cubo 3D girando. Incluía depth buffering, matemática e desenho de polígonos linha a linha.
      Aí o DirectX apareceu, o ponto de contato com a máquina sumiu, e o cubo 3D girando ficou fácil demais para ser divertido.
    • Já naquela época a diferença entre as placas de vídeo mais lentas e as mais rápidas estava ficando grande.
      O barramento passou de 8 bits para 16/32 bits, as placas de vídeo passaram a oferecer suporte a posted writes para que a CPU esperasse menos, e, com CPUs também mais rápidas, sistemas velozes conseguiam escrever uma tela 640x480x256 a mais de 300 quadros por segundo.
      Nesse caso, talvez fosse um buffer em memória de sistema em cache com cópia por DMA, ou talvez um blitter cuidasse do desenho. Mas, mesmo na época do Windows 98, havia placas 3D de baixo custo em que o acesso pela CPU era muito lento, só um pouco melhor que placas antigas de barramento ISA.
      Com as resoluções de tela ficando altas demais, hoje isso até se inverteu um pouco. Mesmo que seja possível redesenhar uma tela 4K inteira a 60 quadros por segundo, é difícil chamar isso de eficiente.
      Jogos normalmente ainda redesenham tudo, mas compositores de desktop fazem bastante otimização, como atribuir camadas dinamicamente a planos de hardware para reduzir as áreas redesenhadas.

  • Trabalhei em outra empresa de jogos na mesma época e inventei por conta própria uma técnica de rolagem igual à segunda abordagem.
    Não acho que tenha sido algo tão surpreendente. Se alguém estivesse resolvendo o mesmo problema naquela época, provavelmente chegaria a uma conclusão parecida.
    Também criei nosso próprio driver de áudio PWM para reproduzir sons amostrados pelo alto-falante do PC, e parece que todo mundo fazia isso também.
    O PC não recebeu amor suficiente antes de todos nós migrarmos para os consoles. Demos como 8088 MPH, do Hornet, ainda me deixam empolgado.

    • Se foi um jogo lançado, você poderia dizer o título para podermos comparar? Concordo que a maioria teria pensado em soluções parecidas, mas fico curioso para saber se a sensação ao jogar era a mesma.
    • Se isso não era tão impressionante assim, por que tantos jogos de plataforma com rolagem de ponta da época ainda eram tão travados?
      Não é um requisito essencial para um jogo divertido, mas a suavidade que Keen mostrava, especialmente em hardware modesto, como abaixo de 10 MHz, era algo de arregalar os olhos na época.
    • A fama muitas vezes vem não da invenção em si, mas da capacidade de comercialização e marketing.
      Devem ter existido incontáveis grandes invenções desconhecidas ao longo de milhares de anos.
      Eu mesmo “inventei” algo parecido 10 anos antes do LinkedIn, mas não consegui comercializar com sucesso. Imagino que a maioria das invenções nunca tenha ficado amplamente conhecida.
      É por isso que muitas startups começam com duas pessoas: um especialista e uma pessoa de negócios.
      Então não está errado. Essa invenção pode não ter sido nada de especial por si só, mas se tornou especial pela combinação de novidade, utilidade e comercialização bem-sucedida.

  • O excelente livro Masters of Doom explica que Keen era um jogo no estilo Mario, ou seja, de rolagem horizontal
    A id propôs essa tecnologia à Nintendo como uma opção para portar Mario para o PC, mas a Nintendo recusou, e foi assim que Keen nasceu
    Foi um salto enorme para os jogos de PC e inaugurou uma nova era de jogos para PC
    Mas uma coisa que ainda não entendo bem é: o que havia de tão diferente entre a tecnologia do NES e a do PC para que a Nintendo conseguisse implementar rolagem horizontal anos antes do PC?

    • EGA essencialmente oferecia um grande framebuffer
      Nos modos gráficos EGA, você podia desenhar qualquer coisa arbitrária que quisesse — linhas, círculos, pixels individuais etc. — e ele foi feito para ser usado assim
      Mas rolagem não vinha de graça. Era preciso copiar memória diretamente e, como o artigo linkado mostra, se você simplesmente forçasse a barra de forma bruta, por causa do limite de largura de banda do barramento ISA, conseguiria algo como só 5 quadros por segundo
      O NES e outros consoles de 8/16 bits não foram feitos para desenhar coisas arbitrárias. Foram feitos para renderizar tiles
      Bastava definir uma grade de tiles de fundo e fornecer um offset de rolagem. Sprites funcionavam de modo parecido, mas podiam se mover de forma independente. Tudo isso vinha de graça a 60 quadros por segundo
      A desvantagem é que não dá para renderizar coisas arbitrárias facilmente. Por exemplo, para pintar um único pixel em algum lugar, seria necessário um contorno bem complicado
      Não é tanto uma questão de a Nintendo ter “descoberto” algo antes da IBM; a IBM criou um sistema gráfico de uso geral voltado a computadores de uso geral e gráficos estáticos, oferecendo controle fino sobre cada pixel. Ao olhar para uma placa EGA, ela é um dispositivo bem grande, com bastante silício
      Já a Nintendo criou um sistema gráfico dedicado muito mais simples, voltado a deslocar tiles
    • Na prática, eles fizeram um port de SMB3 e o mostraram à Nintendo
      Quando a Nintendo não aceitou, criaram novos assets, que depois se tornaram Keen
      O vídeo do port está aqui: https://youtu.be/1YWD6Y9FUuw
    • Não tenho certeza, mas entendo que o NES tinha um chip gráfico dedicado para manipulação de sprites, enquanto no PC tudo isso precisava ser feito por software
    • O método do artigo usa um framebuffer de pixels independentes para imitar em software os tiles gerenciados por hardware
      Para o lado do NES, https://www.nesdev.org/wiki/PPU parece ser um bom ponto de partida
      O desafio principal não é “descobrir como fazer rolagem horizontal” em si, mas ajustar o motor de um jogo de rolagem horizontal para que funcione bem dentro das restrições de espaço de memória e largura de banda de um sistema completamente diferente
    • Acho que o NES e o GB eram baseados em tiles
      Como os jogos eram feitos com base em sprites com camadas, a forma de “acelerar” 2D fazia bastante sentido

  • A entrevista de John Carmack por Lex Fridman passa por todas as principais inovações de cada jogo
    É um episódio realmente fascinante, e recomendo muito se você tiver tempo. Tem cerca de 5 horas

  • Ainda me lembro da época em que eu acreditava conhecer quase todos os segredos de Commander Keen Goodbye Galaxy
    Meus colegas de escola costumavam perguntar os segredos das fases que jogavam nos computadores da escola depois da aula

    • Que inveja. Na escola em que estudei, pelo que cheguei a conversar, eu era o único nerd que já tinha ouvido falar de Commander Keen

  • Quando vejo fabiensanglard.net, recomendo na hora

    • Ele é realmente um tesouro. O livro sobre CPS1 também é excelente
      Se alguém conhecer outros blogs de jogos clássicos com profundidade técnica, gostaria que compartilhasse
      https://nicole.express/ e https://sudden-desu.net/ também são sites de que gosto

  • Entendi como a rolagem vertical funciona ajustando o ponto inicial do framebuffer por scanline, mas no começo não estava claro para mim como a rolagem horizontal podia ser possível sem distorcer demais o framebuffer
    Pensando um pouco mais, percebi que é parecido com desenhar uma imagem na lateral de um cilindro. Não importa onde você desenhe a borda esquerda da imagem: sempre há uma forma de girar o cilindro e configurar os registradores CRTC_START e PEL para ver a imagem inteira com nitidez
    Também é interessante a parte em que “ao chegar à borda da tela, como solução simples, aceitavam um engasgo e copiavam a tela inteira para cima”
    Lembro que, ao iniciar Keen, geralmente aparecia uma mensagem como “VGA compatibility mode enabled”, e sempre me perguntei o que aquilo significava

  • Commander Keen era um joguinho realmente adorável
    Preciso procurar um jeito de rodá-lo de novo
    Mas qual seria a melhor forma de executar isso? Faz uns 20 anos que não uso Windows desde que virei “adulto”; como posso jogar no Debian?

    • Dá para jogar direto: https://archive.org/details/msdos_Commander_Keen_1_-_Maroone...
    • Discordo. Esse era um jogo para crianças que, por algum motivo, podiam usar um computador, mas não tinham um Nintendo
      Na época, computadores custavam umas 10 vezes mais que consoles, então normalmente era porque os adultos tinham ideias bem fortes sobre o que a criança deveria fazer
      Comparado aos jogos de NES e Genesis, falta alma. Eu gostava na época, mas rejoguei recentemente no DosBox e senti claramente que não dá para comparar
    • DosBox roda jogos VGA antigos muito bem e funciona em praticamente qualquer plataforma, inclusive dentro do navegador: https://archive.org/details/msdos_Commander_Keen_1_-_Maroone...
    • Deve ser DosBox
    • Commander Keen e Jill of the Jungle foram os jogos que me apresentaram ao PC antigamente. Ótimas lembranças

  • Alguns anos atrás implementei o segundo método, mas era muito lento mesmo desenhando só a borda frontal
    Só que escrevi em C e nunca aprendi programação em assembly direito
    https://github.com/geon/kate/blob/master/src/platform/dos/eg...