Bad Apple composé de 6 500 expressions régulières recherchées dans Vim

 (eieio.games)
1 points par GN⁺ 2025-01-13 | 1 commentaires | Partager sur WhatsApp
  • Pour lire la vidéo Bad Apple dans Vim, chaque image est convertie en requête de recherche, et l’image est dessinée sur une grille d’espaces de 120x90 uniquement avec le surlignage de recherche
  • La vidéo est découpée avec ffmpeg en environ 6 500 images PNG, puis chaque image est convertie en Python en tableau 2D de 0 et de 1 pour marquer les pixels noirs
  • En combinant \%l, \%c, \zs, \ze et le motif OR \| de Vim, des rectangles définis par des plages de lignes et de colonnes sont surlignés en une seule recherche
  • Le processus qui réduit les images en motifs de recherche rectangulaires ne cherche pas la solution optimale : il choisit la chaîne de recherche la plus courte entre la fusion de haut en bas, la fusion de gauche à droite et le RLE par ligne
  • Une macro place le motif de recherche de chaque ligne dans le registre /, puis passe à la ligne suivante pour faire défiler les images, ce qui réduit le scintillement et la baisse de framerate causés par le collage direct de longues requêtes dans la barre de recherche

Lire Bad Apple avec le surlignage de recherche de Vim

  • L’objectif est de regarder la vidéo Bad Apple sans quitter Vim
  • Ce qui change réellement à l’écran n’est pas le contenu du fichier, mais la requête de recherche courante de Vim
  • La vidéo résultante est limitée à une résolution de 120x90
    • Il était difficile de l’agrandir davantage à cause de la taille de l’écran

Extraction des images et binarisation

  • En utilisant la vidéo et la suggestion de commande ffmpeg du dépôt badapple-frames de Felixoofed, environ 6 500 images PNG ont été obtenues
  • Du code Python redimensionne chaque PNG en 120x90, la convertit en noir et blanc, puis traite comme 1 tout pixel dont la valeur est inférieure à 10
    • 1 signifie un pixel noir
    • 0 signifie un pixel clair
  • La vidéo d’origine était en 480x360, mais elle a été réduite à 120x90 après mesure de la taille du terminal
  • La fonction text_preview sert à afficher les 0 sous forme de . et les 1 sous forme de # afin de vérifier le résultat de la conversion

Faire ressembler les caractères du terminal à des pixels

  • En créant une grille de texte dans un fichier Vim et en recherchant certains caractères, le surlignage des résultats de recherche peut ressembler à une image
  • Le surlignage de recherche par défaut est bleu et peu net ; le réglage hi Search cterm=NONE ctermfg=grey ctermbg=grey est donc utilisé
    • La couleur de premier plan et d’arrière-plan des caractères trouvés est réglée sur le même gris pour leur donner l’apparence de blocs
  • Avec une police classique, les caractères sont plus hauts que larges, ce qui fait ressembler les pixels à des rectangles
  • La police Square est utilisée pour rendre les caractères du terminal proches d’un carré, afin que la grille paraisse plus naturelle

Dessiner des rectangles avec des motifs de recherche

  • La recherche de Vim peut faire correspondre du texte à partir de numéros de ligne et de numéros de colonne précis
  • Le motif d’exemple \%>5c\%<15c\%>4l\%<9l correspond à un rectangle situé entre les colonnes 5 à 15 et les lignes 4 à 9
  • Plusieurs rectangles peuvent être reliés par \| en OR afin d’être trouvés simultanément dans une seule chaîne de recherche
  • Grâce à cette fonctionnalité, le problème devient la décomposition des pixels noirs de chaque image en un ensemble de rectangles

Algorithme de réduction des images en rectangles

  • Une grille de 90x120 représente environ 10 000 pixels ; si l’on crée des motifs pixel par pixel, la chaîne de recherche peut atteindre plusieurs dizaines de milliers de caractères
  • Lors des tests de base, la recherche Vim elle-même est rapide, mais des chaînes de recherche trop longues font chuter la fréquence d’images
  • La première approche écrite consistait à trouver, ligne par ligne, les séquences continues de 1, puis à les fusionner en rectangles lorsqu’elles chevauchaient les séquences de la ligne suivante
    • Trouver les séquences continues de 1 sur la première ligne
    • Trouver le chevauchement entre les séquences de la ligne suivante et celles de la ligne précédente
    • Fusionner si l’aire du rectangle fusionné est supérieure à l’aire de chaque ligne prise séparément
    • Continuer à fusionner de nouvelles séquences avec les rectangles existants lorsque c’est possible
  • Cette approche n’est pas optimale, car elle ne regarde pas au-delà d’une seule ligne
    • Elle peut manquer des cas où une fusion qui semble mauvaise maintenant devient bonne si l’on prend en compte les lignes suivantes

Trois méthodes de génération de motifs pour éviter les goulots d’étranglement

  • De nombreuses chaînes de recherche se situaient autour de 500 à 2 000 caractères, mais certaines images produisaient des chaînes dépassant 10 000 caractères
  • Les longues chaînes de recherche font passer la fréquence d’images d’environ 40 FPS à un nombre à un chiffre
  • La longueur de la chaîne de recherche n’est pas un indicateur parfait des performances, mais dans ce cas, de nombreux motifs de longueur similaire sont reliés en OR, ce qui peut faire augmenter à la fois le nombre de motifs et le temps de recherche
  • Plutôt que de trouver un algorithme général optimal, trois algorithmes simples sont tous exécutés, puis le motif de recherche le plus court est choisi
    • Fusion de haut en bas
    • Fusion de gauche à droite
    • Méthode RLE par ligne
  • Le nombre de sélections est le suivant
    • Méthode d’origine, fusion de haut en bas : 1 110 fois
    • Fusion de gauche à droite : 2 239 fois
    • RLE sur une seule ligne : 3 300 fois
  • Le RLE a été choisi le plus souvent, mais dans les mauvais cas il peut devenir très mauvais, donc il n’est pas utilisé seul

Faire défiler les images dans Vim

  • Dans la fenêtre centrale supérieure de Vim se trouve un fichier d’espaces de 90 lignes x 120 colonnes
    • Comme la recherche se fait par lignes et colonnes, les caractères réels ne sont pas nécessaires
  • Des buffers vides sont placés à gauche et à droite pour centrer l’image
  • La fenêtre du bas contient environ 6 500 motifs de recherche, un par ligne
  • La macro lit le motif de recherche de la ligne courante, le place dans le registre de recherche, puis passe à la ligne suivante

  • Macro utilisée

    • La macro a la forme "ay$:let @/=@a^M+
    • Son fonctionnement est le suivant
    • "a : utiliser le registre a comme cible
    • y$ : copier jusqu’à la fin de la ligne courante
    • :let @/=@a : définir le registre de recherche / avec le contenu du registre a
    • ^M : exécuter la commande
    • + : aller au début de la ligne suivante
    • Si cette macro a été enregistrée dans le registre q, 1500@q permet de faire défiler 1 500 images aussi vite que possible
    • Si l’on colle directement une longue requête dans la barre de recherche, comme /^Ra^M, la barre de recherche s’agrandit pour contenir une requête de plusieurs milliers de caractères, ce qui peut provoquer du scintillement et une baisse de framerate
    • En définissant directement le registre de recherche avec let @/=@a, ce problème peut être évité

Limites et code publié

  • Comme la fonctionnalité de recherche par lignes et colonnes de Vim est utilisée, on peut objecter qu’il ne s’agit pas uniquement d’expressions régulières traditionnelles
  • Il n’y a pas de traitement visant à maintenir une fréquence d’images stable
    • Sur l’ensemble de la vidéo, le framerate fluctue par moments
  • Malgré cela, le résultat se rapproche d’une solution générique permettant de lire une vidéo dans Vim uniquement avec des requêtes de recherche
  • Le code n’est pas nettoyé, mais il est consultable dans le dépôt vim-badapple

À lire aussi

1 commentaires

 
GN⁺ 2025-01-13
Commentaires Hacker News

  • Je savais que si c’était nolen, il trouverait le moyen de multiplier ça par 1000 :))) J’ai déjà utilisé des techniques similaires, mais séparément, et certainement pas en une seule journée. Si ça vous intéresse :
    Bad Matrix (affichage de blocs dans le terminal avec tput) : https://www.evalapply.org/posts/bad-matrix/
    Animating Text Art in Javascript (afficher du texte sur une grille fixe et l’animer comme un flipbook) : https://www.evalapply.org/posts/animate-text-art-javascript/...
    oxo (formater et afficher un plateau de morpion dans le terminal, puis faire correspondre les résultats victoire/défaite/nul avec des regex) : https://github.com/adityaathalye/oxo/blob/7681e75edaeec5aa1f...
    Cela dit, ce Bad Apple reste le meilleur

  • La démo technique qui m’a vraiment fait tomber amoureux de Bad Apple, c’était la version qui tourne sur NES
    https://somethingnerdy.com/downloads/
    Voici une vidéo où je l’exécute sur mon Everdrive
    https://inversethought.com/jordi/video/badapple.mp4
    Il y a même l’audio complet. Les données font environ 1 Go, sur un système où les jeux ordinaires dépassent rarement quelques centaines de Ko et dont le CPU n’a que 3 registres 8 bits pour les calculs

    • Impressionnant. Pour avoir un peu touché au développement NES, j’imagine que faire tenir les performances graphiques n’a pas dû être simple. En général, il suffit de quelques sprites sur une même ligne pour que la NES commence à les “faire fondre”, je ne connais pas le terme exact
      Je me demande s’ils ont utilisé la tile map de fond au lieu des sprites. Même dans ce cas, c’est très impressionnant en termes de bande passante graphique
      Il est indiqué « taux de lecture audio total (44.2kHz) », et c’est aussi étonnant que le son soit aussi net. Je me demande si c’est une capacité ajoutée par la cartouche. De mémoire, le canal PCM de la NES n’approche pas du tout ce débit, et la taille des échantillons devait être de 8 bits aussi
    • Selon ce qui t’a amusé là-dedans, tu aimeras peut-être aussi une version similaire de Bad Apple sur NES. Difficulté supplémentaire : elle s’exécute via l’ACE de Super Mario Bros., et toutes les données sont diffusées en streaming par la manette
      https://www.youtube.com/watch?v=lfG8DbxFibY
      Il y a aussi une vidéo d’explication réalisée avec
      https://www.youtube.com/watch?v=Wa0u1CjGtEQ
    • C’est vraiment génial, et si jamais il y a un article récapitulatif sur ce travail, j’aimerais beaucoup le lire

  • Pour rendre une macro Vim « rejouable », la partie finale qui passe à la ligne suivante peut aussi être remplacée par une exécution de la macro une fois par ligne avec la commande suivante
    :%norm @q

    • Wow, j’apprends ça aujourd’hui. Je suis assez surpris de n’avoir jamais connu cette astuce
      À l’époque où je faisais du Vim golf, je fabriquais plutôt des macros récursives. J’enregistrais la macro et je la terminais par +@q, autrement dit on passe à la ligne suivante puis on relance la macro
      Comme ça, une seule exécution de la macro parcourt toutes les lignes
      C’est très efficace en nombre de frappes, mais en pratique c’est difficile à concevoir et pas très naturel à utiliser, donc je ne l’ai pas souvent fait. Cela dit, pour le golf, c’est une technique amusante

  • Le mois dernier, ces Govee Curtain Lights étaient en promo
    https://us.govee.com/products/govee-curtain-lights
    Je crois qu’on peut y envoyer des GIF animés. Du coup, j’ai ajouté à mon kanban la tâche de fabriquer un GIF de « Bad Apple », mais je ne sais toujours pas combien de mémoire l’appareil a ni à quel point ça tournera bien
    De temps en temps, la scène où Remmy Scarlet déploie ses ailes me donne encore des frissons dans le dos

    • J’ai essayé de faire ça avec des lumières Twinkly, mais malheureusement la mémoire côté éclairage est insuffisante pour tenir plus de quelques secondes
    • J’ai un GIF de Bad Apple en 64x32, il fait un peu moins de 1 Mo
      https://ezgif.com/ m’a énormément aidé

  • On ne se lasse jamais de Bad Apple. C’est la meilleure chose sur Internet. Et presque à chaque fois que je le vois, je ressens un peu de jalousie en me demandant pourquoi ce n’est pas moi qui ai eu l’idée avant
    J’aime aussi énormément l’implémentation des notes de bas de page de ce blog. Je pense que je vais la réutiliser

    • Ces notes de bas de page viennent du site d’un ami talentueux, Jake (https://jakelazaroff.com/). Tu as peut-être déjà vu son travail passer ici
      Sur grand écran, elles s’affichent comme des sidenotes, et sur petit écran elles deviennent des notes de bas de page intégrées qu’on peut déplier au clic. Sers-toi librement

  • Sur le problème de minimisation par rectangles, le problème ici semble différent de celui discuté sur StackOverflow. Le fil SO traite d’une partition en rectangles non chevauchants, alors que ce projet Vim autorise les recouvrements
    Il est donc possible que trouver la solution optimale soit bien plus facile

    • Du point de vue algorithmique, c’est en fait l’inverse. Le problème de couverture minimale en autorisant les recouvrements est NP-difficile, alors que le problème de partition minimale sans recouvrement admet un algorithme en temps polynomial. Voir l’article de 1984 de Franzblau et Kleitman, « An Algorithm for Covering Polygons with Rectangles » : https://core.ac.uk/download/pdf/82333912.pdf
      Bien sûr, ce n’est qu’une parenthèse académique, et ça ne veut pas forcément dire que l’un des deux est réellement plus simple quand on cherche juste à faire tourner quelque chose dans un projet d’un après-midi
    • Bon point. Oui, j’étais complètement passé à côté du fait que les rectangles peuvent se chevaucher. Je vais probablement m’arrêter là sur ce projet, et je suis déjà assez content de la solution actuelle, mais c’est vrai que cet aspect simplifie beaucoup le problème

  • Le générateur parallèle de solutions candidates est vraiment une excellente idée, mais il me faut toujours du temps pour réaliser qu’il n’est pas nécessaire de construire l’algorithme ultime. J’ai toujours l’impression qu’avec encore quelques retouches, je pourrais faire une solution qui marche dans tous les cas

    • C’est probablement une de mes façons préférées de prototyper suffisamment vite. C’est un plaisir à chaque fois que ça fonctionne
      En revanche, je suis d’accord : c’est vraiment difficile de prendre du recul et de voir qu’on peut utiliser cette approche au lieu de chercher quelque chose de « parfait »

  • Assez cool. Belle créativité. Les jeux dont c’est inspiré sont aussi très bons, et les danmaku sont hypnotiques

  • Les gens qui font tourner Doom ou Bad Apple d’une manière complètement imprévue sont vraiment remarquables
    Il y a aussi des cas intéressants, comme Doom lancé sur un test de grossesse

    • Là-dessus, j’ai du mal à être d’accord. En réalité, c’était plus proche de faire tourner Doom sur un microcontrôleur arbitraire placé dans la coque d’un test de grossesse

  • Ça me rappelle quand je regardais la Coupe du monde 2006 au travail. Je me connectais en ssh à mon serveur maison et je pouvais voir le match dans le terminal
    La bande passante était trop limitée pour le regarder autrement