“Bad Apple!!” no Minecraft
(purplesyringa.moe)- Esta é uma implementação que faz Bad Apple!! tocar em tempo real sobre o motor lento do Minecraft, com a mesma resolução 512×384 do original, 20 fps e em escala de cinza
- A ideia central é fazer um structure block no modo
LOADsubstituir a si mesmo pela estrutura do quadro seguinte, e usar clocks com diferença de fase para ultrapassar o limite de 10 Hz da redstone - Como usar um bloco para cada pixel exigiria atualizar 768 chunks a 20 Hz, o projeto reduziu isso fazendo um bloco representar mais informação visual com texturas, modelos e blockstates personalizados do resource pack
- O gargalo não estava na redstone nem na iluminação, mas em
setBlocke no processamento de eventos, então a quantidade de atualizações foi reduzida com codificação delta e substituição de sprites 4×4 que mudam com frequência - A qualidade final foi refinada com 6 tons de cinza, dithering com blue noise e correção de ruído de compressão com perdas, mas o problema de reduzir o original de 30 fps para 20 fps não foi totalmente resolvido
Condições para uma reprodução próxima do original
- O objetivo era reproduzir Bad Apple!! dentro do Minecraft o mais próximo possível do original
- O vídeo roda a 20 fps
- A resolução é 512×384, igual à animação original
- Não é preto e branco puro, mas escala de cinza
- Em CPUs e GPUs modernas, dá para assistir em 20 fps reais sem gravar e acelerar depois
- Não usa command blocks
- Atalhos fáceis foram excluídos das condições de implementação
- Mods não são usados como método de implementação; só são permitidos mods de otimização para testes em máquinas fracas
- Não são usados command blocks,
/setblocknem datapacks - Também não são usadas texturas animadas
- Em dispositivos mais fracos, pode ser necessário usar VulkanMod ou Sodium
- É melhor evitar C2ME, porque o salvamento automático prejudica o desempenho
Limites encontrados por implementações anteriores
- As versões anteriores de Bad Apple!! em Minecraft em geral ficaram restritas a telas pequenas ou renderização lenta
- A tentativa de catlord5 alcançou 512×384 e 30 fps, mas renderizava cerca de 40 vezes mais devagar
- Algumas implementações em tempo real baseadas em redstone ficavam em 5 fps ou em resoluções baixas
- O Minecraft é lento não só no motor de simulação, mas também no de renderização, e o custo cresce conforme aumenta o número de chunks
- Um chunk 16×16×16 tem custo alto de rerenderização independentemente do conteúdo
- Reduzir a quantidade de chunks cobertos pela tela é essencial
- A redstone é difícil de usar diretamente para 20 fps porque geradores de clock práticos normalmente produzem sinal de 10 Hz
- Redstone dust é um dos principais componentes sem atraso, mas pesa bastante no desempenho
Experimentos com formas de armazenar os dados
- O método de hopper line é uma forma típica de armazenamento em que itens guardados em baús são retirados por hoppers e lidos com comparator
- O hopper transfere itens a cada 0,4 segundo, então a taxa máxima é de 2,5 fps
- Para chegar a 20 fps seriam necessários vários hoppers em paralelo, o que traz problemas de custo de simulação e de organização em tiles
- Também foi testado um método que lê valores de 1 a 15 com jukebox e music discs, armazenando quase 4 bits
- Ao espalhar os bits no eixo do tempo, seria possível mirar em 20 fps com 2 hoppers
- Mas a lógica de redstone e o dust necessários para fazer bit shift eram lentos demais, e até o protótipo ficou sem desempenho suficiente
- A repeater delay line é um método simples em que cada pixel tem sua própria linha de repeater, liberando o valor no momento certo
- O tiling de 1×1 pixel é possível
- Mas, como implementações já existentes muito menores ainda precisavam de aceleração de 20 vezes, isso não seria suficiente
Passando os quadros com structure block
- O structure block pode salvar uma área com
SAVEe carregá-la em outro lugar comLOAD- Não pode ser obtido no survival, mas não substitui tudo com um único comando como um command block
- Pode ser ativado por sinal de redstone
- A chave da ideia é que um structure block em modo
LOADpode carregar uma área que se sobrepõe a ele mesmo- Se o structure block atual for trocado pelo próximo, cada ativação passa a carregar o quadro seguinte
- Se a troca for feita de forma simples, o novo structure block detecta imediatamente o sinal de redstone ao redor e ativa de forma recursiva
- Essa recursão continua até atingir o limite rígido do Minecraft
- Como o processamento de desligamento do redstone dust nem chega a terminar, estados anormais de energia acabam permanecendo
- Para bloquear a ativação recursiva, foi adicionado um atraso de 1 redstone tick com repeater
- As estruturas precisam ser criadas com
/tick freeze, para que o repeater seja salvo no estado desligado - Depois de carregar, a próxima estrutura só é chamada um redstone tick depois
- As estruturas precisam ser criadas com
Tratamento dos ticks para chegar a 20 fps
- No Minecraft existem game ticks e redstone ticks
- O motor do jogo recalcula a física a 20 Hz
- Componentes de redstone normalmente agendam atualização em unidades de 0,1 segundo, ou seja, 10 Hz
- Na prática, os eventos são processados em intervalos de 0,05 segundo, e, dependendo do momento da entrada do usuário, a reação da redstone pode ser deslocada para aquela fase
- Para obter 20 fps, foram usadas quatro estruturas
- As estruturas vermelha e amarela formam um clock de 10 Hz
- As estruturas azul e verde formam outro clock de 10 Hz
- Ao iniciar os dois clocks com fases diferentes, as quatro cores aparecem alternadamente no mesmo lugar a 20 Hz
- Para iniciar os dois clocks com diferença de fase de forma estável, foi aproveitado um bug antigo em que um pistão leva 3 game ticks quando empurra um redstone block por entrada direta do usuário
Técnicas de resource pack para reduzir o número de chunks
- Se cada bloco fosse um pixel, uma tela 512×384 teria 24 chunks na vertical e 32 na horizontal
- No total, 768 chunks precisariam ser atualizados continuamente a 20 Hz
- Isso também esbarra na distância máxima de renderização vanilla de 32 chunks, então não seria realista
- Com texturas personalizadas no resource pack, várias texturas de blocos foram alteradas para colocar vários subpixels dentro de um único bloco
- 16 variações de bloco equivalem a 4 bits
- Com 256 blocos e cores adicionais, dá para representar escala de cinza em vez de apenas preto e branco
- Com isso, a resolução em blocos foi reduzida em 4 vezes, para 256×192 blocos
- O número de chunks atualizados caiu para 192
- Mesmo assim, ainda era um peso grande demais para atualização a 20 Hz
Fila de renderização e codificação delta
- O motor de renderização do Minecraft prioriza atualizações de chunks próximos ao jogador
- Várias threads constroem chunks ao mesmo tempo, e a fila de atualização entrega primeiro os mais próximos do jogador
- Se os N chunks mais próximos forem atualizados sem parar a 20 Hz, só eles podem acabar sendo processados e o resto pode deixar de ser renderizado
- Com Spark, foi possível verificar que o gargalo estava nas atualizações gerais, não na redstone nem na iluminação
- Em especial,
setBlocke os event handlers eram o problema
- Em especial,
- A solução foi reduzir o número de atualizações, aplicando codificação delta para atualizar apenas os blocos que mudavam entre um quadro e outro
- Como a maioria dos quadros não muda tanto, havia margem teórica para melhorar o desempenho
- Como o structure block só pode carregar até 48×48×48 blocos por vez, a tela foi dividida em 6×4 subtelas de 48×48
- O protótipo inicial levava cerca de 7 minutos para uma execução, e exigia
/tick freeze, 24 botões e/tick unfreeze, mas funcionava- Só a codificação delta ainda não era rápida o bastante
Otimização com modelos e blockstate
- Os modelos do Minecraft definem a forma dos blocos com cuboides, e as coordenadas podem passar do intervalo
(0,0,0)a(16,16,16)e ir de -16 até 32- Com a configuração certa, um bloco pode ser renderizado como se fosse até 3 vezes maior, substituindo uma área de 9 blocos
- Como não há blocos suficientes para cobrir todas as combinações, isso só é viável em casos comuns, como uma área 6×6 totalmente preta
- Dos cerca de 600 blocos utilizáveis, 256 foram usados para a representação básica de subpixels, e parte do restante foi reservada para otimizações
- A abordagem final divide a tela em células de 2×2 blocos e trata o sprite 4×4 pixels de cada célula como candidato a substituição por um único bloco
- A diferença entre dois quadros consecutivos é calculada
- A versão anterior e a posterior de cada célula alterada recebem pontos
- Em cenas que mudam rápido, células com mais pixels alterados ganham pontuação maior
- Os sprites com maior pontuação recebem os blocos disponíveis primeiro
- Para ultrapassar o limite básico de quantidade de blocos, foi feita uma exploração dos
blockstates- Blocos como
oak_logpodem escolher modelos diferentes conforme suas propriedades - Blocos como
grindstonepermitem usar combinações de várias propriedades como chave
- Blocos como
- Ao extrair variantes de blockstate dos assets padrão e filtrar propriedades que não podiam ser controladas, o número de modelos acessíveis subiu de cerca de 600 para 1700
- A quantidade de cores passou a 6
- A quantidade de blocos otimizados passou a 400
Áudio e mecanismo de inicialização
- A música foi tratada trocando o som de um music disc por meio de resource pack
- O tempo de reprodução do disco continua fixo mesmo se o áudio for alterado
- Foi usado o disco Relic, por ter duração mais próxima de “Bad Apple!!”
assets/minecraft/lang/en_us.jsonfoi alterado para que a legenda no jogo apareça como “Now Playing: Bad Apple!!”
- Um conjunto com botão, dropper, hopper e jukebox foi montado para que um único clique colocasse o disco na jukebox e iniciasse a música
- Quando a reprodução termina, o hopper devolve o disco ao dropper para preparar a próxima execução
- Por causa da quasiconnectivity, o sinal de redstone emitido pela jukebox durante a reprodução bagunçava o estado do hopper e do dropper
- A entrada do botão foi ajustada para fazer o dust atualizar o dropper
- Um repeater então liga o dropper novamente um redstone tick depois, inserindo o disco
- Para levar o sinal do ponto de visualização até os dispositivos atrás da tela, foi criado um fio instantâneo baseado em structure block
- O structure block carrega um redstone torch energizado no segmento seguinte e, no tick seguinte, ele se apaga por causa de um redstone block
- Esse pulso ativa o próximo structure block, transmitindo o sinal
- Como o structure block pode cobrir até 48 blocos, ele consegue enviar o sinal de início para a grade de subtelas 48×48
- A distância de cerca de 150 blocos entre o espectador e os dispositivos atrás da tela foi ligada com uma estrutura separada e resetável
- A transmissão do sinal ocorre gerando e apagando em cadeia combinações de structure block e redstone block
- Como essa estrutura é difícil de salvar diretamente no creative, os arquivos de structure foram gerados com biblioteca Python
- O mecanismo final foi reunido em uma caixa 4×2×3 acionada por um botão externo
Pré-processamento dos quadros e qualidade do vídeo
- As tarefas restantes de pré-processamento eram reduzir o vídeo colorido completo para 6 cores e converter o vídeo de 30 fps para 20 fps
- Bad Apple!! não usa apenas preto e branco puro; várias cenas utilizam escala de cinza
- Motion blur
- Objetos com brilhos diferentes
- Gradientes em transições de cena
- Efeitos como fogo, sol, sombra e ondulações
- Arredondar simplesmente para a cor mais próxima cria banding
- O dithering ameniza isso convertendo tons intermediários impossíveis de representar em padrões de cores vizinhas representáveis
- Um dithering global de alta qualidade pode gerar resultados muito diferentes entre quadros consecutivos
- O olho humano percebe facilmente essa inconsistência
- E isso também cria atualizações demais para o Minecraft aguentar
- Ditherings locais como Bayer dithering eram estáveis, mas a qualidade era baixa, então o ordered dithering com blue noise virou o meio-termo
- O
ffmpegnão oferece suporte a dithering com blue noise - As texturas de blue noise de Christoph Peters foram recortadas para 512×384 e aplicadas com um script em Rust
- O
- O vídeo original veio de um upload no Niconico com compressão com perdas, então havia ruído
- O ruído em áreas pretas e brancas ficou mais visível depois do dithering
- Para corrigir isso, tons quase pretos foram arredondados para preto, tons quase brancos para branco, e os tons intermediários foram espalhados de forma a manter a continuidade
- O problema de reduzir de 30 fps para 20 fps não foi totalmente resolvido
- Se cada terceiro quadro for descartado, o intervalo de movimento alterna entre quadros ímpares e pares e fica visualmente incômodo
- A quantidade de atualizações também passa a variar em padrão serrilhado
- Vídeos online de Bad Apple!! em 60 fps tinham muitos artefatos em transições rápidas de cena, porque tinham sido ampliados por IA ou ferramentas automáticas
Resultado e trabalhos seguintes
- A implementação começou em 48×36 com 2 cores, passou por 128×96 e 10 cores, depois por 256×192, e no fim chegou a 512×384 com 6 cores
- Também houve tentativa de tocar a música com note block, mas isso exigiria qualidade boa o bastante para virar praticamente outro projeto, então a ideia foi abandonada
- Foi criada a técnica structstone, que usa structure blocks como se fossem redstone, e também foi iniciado um protótipo de computador com essa ideia
- Durante o desenvolvimento, foram usados
ffmpeg,mpv, a image crate de Rust, código decompilado do Minecraft e técnicas para minimizar o tamanho do diretório do mundo - O trabalho todo levou mais de um mês e, em colaboração com amigos, virou uma experiência de resolver problemas de um jeito diferente de projetos comuns
1 comentários
Opiniões no Hacker News
Aprendi muito mais sobre computação gráfica do que esperava, e elogios ao autor
Uma pequena correção: a imagem que o autor chamou de “The sun” na verdade é a cena em que Eirin [0] olha para a Lua. Nessa cena [1], Eirin estende a mão para a Lua, de onde foi exilada, mas hesita e a recolhe; na cena seguinte, Kaguya [2] também estende a mão para a Lua, mas não hesita. Segundo a wiki de Touhou, o plano de roubar a Lua teria sido de Eirin, então não tenho muita certeza do que exatamente esse simbolismo significa
[0] https://en.touhouwiki.net/wiki/Eirin_Yagokoro
[1] https://youtu.be/FtutLA63Cp8?t=99
[2] https://en.touhouwiki.net/wiki/Kaguya_Houraisan
Eirin escolheu cortar de propósito a conexão com a Lua para proteger Kaguya
Não entendo muito bem por que Bad Apple está virando praticamente o Hello World de renderização gráfica, mas é divertido ver em tempo real
Também vi esta demo que mostra hipermídia em alta taxa de quadros com Bad Apple: https://data-star.dev/examples/bad_apple
Em muitos aspectos, Touhou, diferentemente de fandoms anteriores, foi quase um protótipo dos fandoms modernos da internet, e vídeos de Bad Apple não são derrubados mesmo usando o mesmo áudio
Segundo, o formato de teatro de sombras é fácil de reconhecer por mais baixa que seja a resolução. Já vi até um caso em uma grade 3x3. Além disso, como é em preto e branco, ou seja, só duas cores, 1/0, é muito fácil transformar os quadros em praticamente qualquer formato imaginável só sabendo o nível de “Hello World”
Roda em uma CPU totalmente programável feita com Redstone. As especificações do IRIS Computer são: CPU de 16 bits customizada, 8 kB de RAM, 64 kB de ROM, 1 kB de ROM de texturas, tela de 96x64 pixels com 16 cores, unidade de ponto flutuante (add/sub/mult/div/sqrt), clock de 173 ticks de Redstone, sem aceleração de hardware para gráficos 3D, execução de programas escritos em URCL; graças ao servidor MCHPRS, roda a 1 milhão de ticks por segundo, com velocidade de clock de 5,8 kHz
Em vez de música com batidas e compassos regulares, faz muito mais sentido imaginar que você está ouvindo os bits pares de um barramento de 16 bits ligados a instrumentos enquanto o MS-DOS inicializa. Como o desenvolvedor dos jogos Touhou compôs essas faixas enquanto criava sozinho jogos hardcore de tiro para PC-88/PC-98, sem formação formal em teoria musical, isso parece um resultado natural, e por isso elas podem soar mais familiares para engenheiros de hardware embarcado do que música comum
Outro fator foi a comunidade nicovideo.jp / nico-tech, que se desenvolveu a partir da cultura do 2ch/futaba. Usuários com competência muito maior do que sua ambição por remuneração ou dinheiro — na época, muitos também eram estudantes de STEM — despejavam técnica em remixes por diversão. Magos de FPGA desconhecidos, especialistas em drivers de motor e editores de vídeo apareciam do nada, soltavam vídeos alucinantes e iam embora; era realmente absurdo. Em certo momento, a Maker Faire Tokyo, para agradar desenvolvedores web de camiseta preocupados com aparência, chegou a colocar pessoas suspeitas de usar camisas sociais de nico-tech em uma área isolada de outro pavilhão. O episódio foi irônico, levou ao nascimento dos encontros nico-tech e não se repetiu. Essa densidade absurda de qualidade e quantidade de conteúdo criou a inércia do PV de Bad Apple!!
O último elemento essencial foi o fato de o PV ser monocromático — estritamente falando, em escala de cinza. Provavelmente foi por isso que este vídeo, e não outro da era de ouro do nicovideo.jp, acabou sendo o escolhido
1: https://www.youtube.com/watch?v=Yw5HTeT_dis
Ele já é bonito e impressionante por si só como obra de arte, então acho que tem muitas características que agradariam especialmente ao pessoal da demoscene
Também há outros clipes de vídeo com cores: https://youtu.be/mgfwwqwxdxY
“Bad Apple em cima de tudo!” é uma das minhas modas nerds favoritas
Quando vi pela primeira vez no Genesis/Mega Drive, fiquei chocado que fosse possível em um hardware tão fraco. Gosto de ver novos ports feitos para coisas sem desempenho suficiente. Não acho que eu seja inteligente o bastante para fazer isso, já que não sou bom em programação de baixo nível, mas respeito muito quem consegue
A parte que diz “essa recursão termina quando o Minecraft atinge um limite rígido e, por sorte, gera um bloco amarelo em vez de um bloco vermelho” me lembrou o antigo glitch de supressão de atualização (https://mcdf.wiki.gg/wiki/Java_Edition:Update_Suppression)
A supressão de população, mais complicada (https://mcdf.wiki.gg/wiki/Java_Edition:Population_Suppressio...), também pode deixar o motor do jogo em um estado de glitch semelhante, fazendo os blocos caírem imediatamente
Meu algoritmo de dithering favorito para vídeos é o Yliluoma dithering: https://bisqwit.iki.fi/story/howto/dither/jy/
Ele é especialmente útil para conteúdo em escala de cinza, porque encontrar a matriz de dithering ideal dentro da paleta disponível é uma operação exata simples, e o resultado pode ser colocado em uma tabela de consulta para uso em renderização em tempo real. Pessoalmente, acho que fica muito melhor que Bayer ou dithering aleatório, especialmente em gradientes
Dizer algo como “Redstone dust é praticamente o único componente que não cria atraso de ticks, mas é muito lento. Parece que não há ninguém na Mojang que conheça algoritmos de grafos” é exagerado
Ele ficou muito menos lento desde o texto que o post original linkou como fonte de informação, e houve muitas melhorias nos últimos 3 anos, incluindo uma recente. A Mojang recebe muito ódio de todos os lados. O motivo de ter demorado tanto para tornar Redstone menos lento é que qualquer mexida mínima em Redstone faz a comunidade gritar, e fazer trabalho que não seja adicionar recursos novos também faz a comunidade gritar, então isso passou a valer menos a pena. Ficar bravo na internet dizendo que eles não conhecem algoritmos de grafos não ajuda. A Mojang já contratou várias vezes talentos muito bons da comunidade de Minecraft, como Panda4994, Kingbdogz e Gnembon, e tem a competência técnica para fazer o que quiser. O que ela não tem é tempo e orçamento infinitos. Manter e sincronizar ao mesmo tempo uma base de código Java de 15 anos e um app C++ multiplataforma gigantesco é realmente difícil, então eu gostaria que as pessoas fossem um pouco mais generosas. Estou cansado do ódio que chega de todos os lados o dia inteiro, e queria que fosse possível simplesmente dizer que Minecraft é incrível
Antes eu achava mais irritante, mas depois percebi que isso parece menos arrogância e mais a ingenuidade de pessoas na faixa dos 16 a 21 anos, com pouca experiência “profissional”
Também não parece que se importem com compatibilidade entre versões
Depois do ensino médio, não fiquei tão obcecado por Minecraft a ponto de criar dispositivos sérios de Redstone
Hoje jogo algumas vezes por mês com amigos quando, de repente, volta a vontade de construir e explorar alguma coisa. Olhando para o ecossistema de Redstone agora, ele mudou tanto que está irreconhecível, e fico me perguntando se vou ter uma sensação parecida conforme vou me tornando aos poucos um engenheiro de software sênior. Imagino que, com o passar dos anos, ao olhar para stacks em que não mexi profissionalmente por alguns anos, vou me maravilhar com a rapidez com que a tecnologia muda e com as coisas novas que as pessoas constroem em cima dela
Não concordo com a reação “E... é isso? Olhando em retrospecto, o resultado parece quase trivialmente alcançável, e a gente se pergunta por que ninguém fez antes”
Este é um ótimo registro de desenvolvimento e uma pequena aula sobre como dividir uma tarefa que parece esmagadora em pedaços quase impossíveis, mas possíveis. Gostei muito. Para referência, esta implementação renderiza Bad Apple a 20fps no Minecraft vanilla usando apenas uma textura customizada e algumas definições de objetos customizadas alteradas para permitir mais texturas. O resto é bem exótico, mas é vanilla
Acho meio engraçado terem colocado tanto esforço no vídeo em si
Quando termino uma implementação de Bad Apple, normalmente estou exausto demais para pensar em dithering ou taxa de quadros; simplesmente passo pelo ffmpeg e digo que está pronto
Bad Apple feito em um mundo de Minecraft também vale a pena ver: https://www.youtube.com/watch?v=RN3QW9SVnds