Bad Apple composto por 6.500 expressões regulares pesquisadas no Vim

• Para reproduzir o vídeo Bad Apple dentro do Vim, cada frame é convertido em uma consulta de busca, e a imagem é desenhada apenas com o destaque de busca sobre uma grade de espaços em branco de 120x90
• O vídeo é dividido com ffmpeg em cerca de 6.500 frames PNG; depois, em Python, cada imagem é convertida em uma matriz 2D de 0 e 1 para marcar os pixels pretos
• Combinando \%l, \%c, \zs, \ze e o padrão OR \| do Vim, é possível destacar um retângulo de intervalo de linhas e colunas específico com uma única busca
• O processo de reduzir frames a padrões de busca retangulares não usa uma solução ótima; em vez disso, escolhe a string de busca mais curta entre mesclagem de cima→baixo, mesclagem da esquerda→direita e RLE por linha
• Uma macro coloca o padrão de busca de cada linha no registrador / e avança para a próxima linha para trocar de frame, reduzindo a cintilação e a queda de frames que ocorrem ao colar consultas longas diretamente na janela de busca

---

Reproduzindo Bad Apple com destaque de busca do Vim

• O objetivo é assistir ao vídeo Bad Apple sem sair do Vim
• O que realmente muda na tela não é o conteúdo do arquivo, mas a consulta de busca atual do Vim
• O vídeo resultante é limitado à resolução de 120x90
  • Foi difícil aumentar mais por causa do tamanho da tela

Extração de frames e binarização

• Usando o vídeo e a sugestão de comando ffmpeg do repositório badapple-frames de Felixoofed, foram obtidos cerca de 6.500 frames PNG
• Um código em Python redimensiona cada PNG para 120x90, converte para preto e branco e trata pixels com valor menor que 10 como 1
  • 1 significa pixel preto
  • 0 significa pixel claro
• O vídeo original era 480x360, mas foi reduzido para 120x90 após medir o tamanho do terminal
• A função text_preview foi usada para verificar o resultado da conversão, imprimindo 0 como . e 1 como #

Fazendo caracteres do terminal parecerem pixels

• Ao criar uma grade de texto em um arquivo do Vim e buscar caracteres específicos, o destaque dos resultados de busca pode parecer uma imagem
• Como o destaque de busca padrão é azul e pouco nítido, foi usada a configuração hi Search cterm=NONE ctermfg=grey ctermbg=grey
  • A cor de primeiro plano e a cor de fundo dos caracteres encontrados são ajustadas para o mesmo cinza, para parecerem blocos
• Em fontes comuns, os caracteres são mais altos na vertical, fazendo os pixels parecerem retângulos
• A fonte Square foi usada para deixar os caracteres do terminal mais próximos de quadrados e fazer a grade parecer mais natural

Desenhando retângulos como padrões de busca

• A busca do Vim pode fazer correspondências com base em um número de linha e um número de coluna específicos
• O padrão de exemplo \%>5c\%<15c\%>4l\%<9l corresponde a um retângulo entre as colunas 5~15 e as linhas 4~9
• Vários retângulos podem ser conectados por OR com \|, permitindo correspondências simultâneas em uma única string de busca
• Graças a esse recurso, o problema passa a ser decompor os pixels pretos de cada frame em vários conjuntos de retângulos

Algoritmo para reduzir frames a retângulos

• Uma grade de 90x120 tem cerca de 10.000 pixels; se o padrão for criado pixel a pixel, a string de busca pode chegar a dezenas de milhares de caracteres
• Em testes básicos, a busca do Vim em si é rápida, mas strings de busca longas demais reduzem a taxa de frames
• A primeira abordagem escrita encontra sequências contínuas de 1 por linha e, se elas se sobrepõem aos trechos da linha seguinte, as mescla em retângulos
  • Encontra sequências contínuas de 1 na primeira linha
  • Encontra a sobreposição entre os trechos da linha seguinte e os trechos da linha anterior
  • Mescla quando a área do retângulo mesclado é maior que a área isolada de cada linha
  • Quando possível, continua mesclando novos trechos a retângulos existentes
• Essa abordagem não é ótima porque não olha além de uma linha à frente
  • Ela perde casos em que algo que agora parece uma mesclagem ruim se tornaria uma boa mesclagem ao considerar linhas posteriores

Três formas de gerar padrões para evitar gargalos

• Muitas strings de busca ficavam na faixa de 500~2.000 caracteres, mas em alguns frames eram geradas strings com mais de 10.000 caracteres
• Strings de busca longas reduziam a taxa de frames de cerca de 40 FPS para um dígito
• O comprimento da string de busca não é uma métrica perfeita de desempenho, mas, neste caso, muitos padrões de tamanho parecido eram ligados por OR, então a quantidade de padrões e o tempo de busca podiam crescer juntos
• Em vez de procurar um algoritmo geral ótimo, os três algoritmos simples são executados, e o padrão de busca mais curto é escolhido
  • Mesclagem de cima→baixo
  • Mesclagem da esquerda→direita
  • RLE por linha
• O número de vezes em que cada um foi selecionado foi o seguinte
  • Mesclagem original de cima→baixo: 1.110 vezes
  • Mesclagem da esquerda→direita: 2.239 vezes
  • RLE de linha única: 3.300 vezes
• Embora o RLE tenha sido escolhido com mais frequência, em casos ruins ele pode ser muito ruim, então seu uso isolado foi evitado

Avançando frames dentro do Vim

• Na janela central superior do Vim, há um arquivo em branco de 90 linhas x 120 colunas
  • Como a busca usa linhas e colunas como referência, os caracteres reais não são necessários
• Nas laterais, há buffers vazios para centralizar a imagem
• Na janela inferior, há cerca de 6.500 padrões de busca, um por linha
• A macro lê o padrão de busca da linha atual, coloca-o no registrador de busca e avança para a próxima linha

• Macro usada

  • A macro tem a forma "ay$:let @/=@a^M+
  • O funcionamento é o seguinte
  • "a: usa o registrador a como destino
  • y$: copia até o fim da linha atual
  • :let @/=@a: define o registrador de busca / como o conteúdo do registrador a
  • ^M: executa o comando
  • +: move para o início da próxima linha
  • Se essa macro tiver sido gravada no registrador q, é possível avançar 1.500 frames o mais rápido possível com 1500@q
  • Ao colar uma consulta longa diretamente na janela de busca, como em /^Ra^M, a janela de busca cresce para acomodar uma consulta de milhares de caracteres, causando cintilação e queda de frames
  • Definir diretamente o registrador de busca com let @/=@a evita esse problema

Limitações e código publicado

• Como foram usados os recursos de busca por linha e coluna do Vim, é possível argumentar que isso não é composto apenas por expressões regulares tradicionais
• Não há tratamento para manter a taxa de frames estável
  • Ao longo de todo o vídeo, a taxa de frames oscila em alguns pontos
• Ainda assim, foi produzido um resultado próximo de uma solução genérica para reproduzir vídeo dentro do Vim usando apenas consultas de busca
• O código não está organizado, mas pode ser conferido no repositório vim-badapple

[GN⁺]

Comentários no Hacker News

• Eu sabia que, se fosse o nolen, ele daria um jeito de aumentar isso em 1000 vezes :))) Já usei técnicas parecidas antes, mas separadamente, e definitivamente não em um único dia. Se tiver interesse:
  Bad Matrix (imprime blocos no terminal com tput): https://www.evalapply.org/posts/bad-matrix/
  Animating Text Art in Javascript (anima como um flipbook imprimindo texto em uma grade fixa): https://www.evalapply.org/posts/animate-text-art-javascript/...
  oxo (formata e imprime um tabuleiro de jogo da velha no terminal e faz o match de vitória/derrota/empate com regex): https://github.com/adityaathalye/oxo/blob/7681e75edaeec5aa1f...
  Ainda assim, esse Bad Apple é o melhor

• A demonstração técnica que me fez entrar de vez em Bad Apple foi a versão rodando no NES
  https://somethingnerdy.com/downloads/
  O vídeo rodando no meu Everdrive está aqui
  https://inversethought.com/jordi/video/badapple.mp4
  O áudio sai completo também. Os dados têm cerca de 1 GB, em um sistema em que jogos comuns não passavam de algumas centenas de KB e a CPU tinha apenas três registradores de 8 bits para cálculo

  • Impressionante. Como alguém que já brincou um pouco com desenvolvimento para NES, imagino que não deve ter sido fácil atingir esse desempenho gráfico. Normalmente, se houver só alguns sprites em uma linha, o NES já começa a “derreter” os sprites; não sei qual é o termo exato
    Fiquei curioso se usaram o tile map de fundo em vez de sprites. Mesmo assim, em termos de largura de banda gráfica, é bem impressionante
    Diz “taxa total de reprodução de áudio (44,2 kHz)”, e também surpreende o som ser tão nítido. Fico imaginando se é algum recurso expandido pelo cartucho. Pelo que lembro, o canal PCM do NES não chegava nem perto dessa taxa de bits, e acho que o tamanho das amostras também era de 8 bits
  • Dependendo do que você achou interessante, talvez também goste de um Bad Apple parecido implementado no NES. Com a dificuldade extra de rodar via ACE de Super Mario Bros. e transmitir todos os dados pelo controle
    https://www.youtube.com/watch?v=lfG8DbxFibY
    Também há um vídeo explicativo feito junto
    https://www.youtube.com/watch?v=Wa0u1CjGtEQ
  • Muito legal mesmo; se houver algum post sobre esse trabalho, eu adoraria ler

• A parte no final que move para a próxima linha para tornar a macro do Vim “reexecutável” também poderia ser feita executando a macro uma vez por linha com o comando abaixo
  :%norm @q

  • Uau, aprendi algo hoje. É bem surpreendente que eu não conhecesse esse truque
    Quando eu fazia Vim golf antigamente, normalmente criava macros recursivas. Gravava a macro e terminava com +@q. Ou seja, ela ia para a próxima linha e executava a macro de novo. Assim, ao executar a macro uma vez, ela percorria todas as linhas
    Em termos de quantidade de teclas, é muito eficiente, mas na prática é difícil de raciocinar e não fica natural nas mãos, então eu não usava tanto. Ainda assim, é uma técnica divertida para golf

• No mês passado, essas Govee Curtain Lights estavam em promoção
  https://us.govee.com/products/govee-curtain-lights
  Pelo que sei, dá para enviar GIFs animados para elas. Então adicionei a tarefa de fazer um GIF de “Bad Apple” ao meu quadro Kanban, mas ainda não sei quanta memória o dispositivo tem nem quão bem vai rodar
  Às vezes, a cena em que Remmy Scarlet abre as asas ainda me dá calafrios

  • Tentei fazer isso com luzes Twinkly, mas infelizmente a memória das luzes era insuficiente e não consegui rodar por mais do que alguns segundos
  • Tenho um GIF de Bad Apple em resolução 64x32, com pouco menos de 1 MB
    https://ezgif.com/ ajudou muito

• Bad Apple não cansa. É uma das melhores coisas da internet. E, quase toda vez que vejo, fico com um pouco de inveja por não ter pensado nessa ideia antes
  Também gostei muito da implementação das notas de rodapé desse blog. Acho que vou acabar usando

  • Essas notas de rodapé foram tiradas do site do meu talentoso amigo Jake (https://jakelazaroff.com/). Talvez você já tenha visto o trabalho dele por aqui antes
    Em telas grandes, aparecem como sidenotes; em telas pequenas, viram notas de rodapé inline que se expandem ao clicar. Pode copiar à vontade

• No problema de minimizar retângulos, o problema aqui parece diferente do discutido no StackOverflow. A thread do SO trata de uma partição em retângulos que não se sobrepõem, mas este projeto em Vim permite sobreposição
  Então é possível que encontrar a solução ótima seja muito mais fácil

  • Do ponto de vista algorítmico, na verdade é o contrário. O problema de cobertura mínima permitindo sobreposição é NP-difícil, enquanto o problema de partição mínima sem sobreposição tem algoritmos em tempo polinomial. Veja o artigo de Franzblau e Kleitman de 1984, “An Algorithm for Covering Polygons with Rectangles”: https://core.ac.uk/download/pdf/82333912.pdf
    Claro, isso é só um aparte acadêmico e não necessariamente significa que, na prática, um lado seja mais fácil quando a situação é fazer algo funcionar como projeto de uma tarde
  • Bom ponto. Sim, eu tinha deixado passar completamente o fato de que os retângulos podem se sobrepor. Acho que provavelmente vou encerrar este projeto por aqui e estou bem satisfeito com a solução atual, mas parece verdade que isso simplifica bastante o problema

• Um gerador paralelo de soluções candidatas é uma ideia muito boa, mas sempre demoro a perceber que não preciso criar o algoritmo mais poderoso de todos. Isso porque fico pensando que, com só mais alguns ajustes, daria para fazer uma solução que funcione em todos os casos

  • Talvez seja o meu truque favorito para deixar protótipos rápidos o suficiente. É sempre divertido quando funciona
    Mas concordo que é realmente difícil perceber que dá para dar um passo atrás e usar esse método em vez de fazer algo “perfeito”

• Bem legal. Boa criatividade. Os jogos que serviram de base também são bem bons, e o bullet hell é hipnótico

• As pessoas que fazem Doom ou Bad Apple rodar de jeitos inesperados são incríveis
  Há casos interessantes, como rodar Doom em um teste de gravidez

  • Não concordo muito com isso. Na prática, foi mais como colocar um microcontrolador arbitrário dentro da carcaça de um teste de gravidez e rodar Doom nele

• Isso me lembrou de quando assisti à Copa do Mundo de 2006 no trabalho. Eu fazia login via ssh no servidor de casa e conseguia ver as partidas no terminal
  Não havia largura de banda suficiente para assistir de outro jeito