- Une implémentation qui fait lire Bad Apple!! en temps réel sur le moteur lent de Minecraft, dans la résolution originale de 512×384, à 20 fps et en niveaux de gris
- L’idée clé consiste à faire en sorte qu’un structure block en mode
LOADse remplace lui-même par la structure de l’image suivante, tout en dépassant la limite de 10 Hz de la redstone grâce à deux horloges déphasées - Comme utiliser un bloc pour un pixel imposerait de mettre à jour 768 chunks à 20 Hz, l’auteur réduit la charge en utilisant des textures, modèles et blockstates personnalisés dans le pack de ressources afin qu’un seul bloc représente davantage d’informations à l’écran
- Le goulet d’étranglement ne venait pas tant de la redstone ou de l’éclairage que de
setBlocket du traitement des événements, donc le volume de mises à jour a été réduit via le codage delta et le remplacement des sprites 4×4 qui changent souvent - Le rendu final a été affiné avec 6 niveaux de gris, un tramage en bruit bleu et une correction du bruit de compression avec pertes, mais la réduction de la source de 30 fps à 20 fps n’a pas été entièrement résolue
Conditions pour une lecture au plus proche de l’original
- L’objectif était de lire Bad Apple!! dans Minecraft en restant aussi proche que possible de l’original
- la vidéo est lue à 20 fps
- la résolution est de 512×384, comme l’animation d’origine
- ce n’est pas du noir et blanc pur mais du niveau de gris
- sur des CPU et GPU modernes, on peut la regarder à 20 fps réels sans enregistrer puis accélérer la vidéo
- aucun bloc de commande n’est utilisé
- Les contournements trop faciles ont été exclus des contraintes de réalisation
- aucun mod n’est utilisé comme méthode d’implémentation, seuls des mods d’optimisation pour tests sur machines peu puissantes sont autorisés
- pas de blocs de commande, pas de
/setblock, pas de datapacks - pas de textures animées non plus
- Sur les machines modestes, VulkanMod ou Sodium peuvent être nécessaires
- il faut éviter C2ME, dont la sauvegarde automatique dégrade les performances
Les limites rencontrées par les implémentations précédentes
- Les versions précédentes de Bad Apple!! restaient pour la plupart limitées à de petits écrans ou à des rendus lents
- l’essai de catlord5 atteignait 512×384 et 30 fps, mais avec un rendu environ 40 fois plus lent
- certaines implémentations temps réel basées sur la redstone tournaient à 5 fps ou à très basse résolution
- Minecraft est lent non seulement côté simulation, mais aussi côté rendu, et la charge augmente avec le nombre de chunks
- rerendre un chunk 16×16×16 coûte cher quel que soit son contenu
- il est donc essentiel de réduire le nombre de chunks couverts par l’écran
- La redstone est difficile à utiliser telle quelle pour du 20 fps, car les générateurs d’horloge pratiques produisent généralement un signal à 10 Hz
- la redstone dust est un composant clé sans délai, mais elle coûte cher en performances
Expérimentations sur le stockage des données
- La méthode de la hopper line est un stockage classique où des objets stockés dans des coffres sont extraits par des hoppers puis lus via des comparators
- un hopper a un intervalle de transfert de 0,4 seconde, soit un framerate maximal de 2,5 fps
- pour atteindre 20 fps, il faudrait plusieurs hoppers en parallèle, avec des problèmes de tiling et de coût de simulation
- Une autre tentative consistait à lire une valeur de 1 à 15 à l’aide d’un jukebox et de disques musicaux afin de stocker presque 4 bits
- en dépliant les bits sur l’axe temporel, 2 hoppers pourraient théoriquement viser 20 fps
- mais la logique de décalage de bits nécessaire et la redstone dust étaient trop lentes, et même le prototype manquait de performances
- La repeater delay line consiste à attribuer une ligne de repeaters à chaque pixel pour sortir une valeur au bon moment
- un tiling en pixels 1×1 est alors possible
- mais comme des implémentations existantes bien plus petites demandaient déjà une accélération de 20×, ce n’était pas suffisant
Faire défiler les images avec des structure blocks
- Un structure block peut sauvegarder une zone avec
SAVEpuis la recharger ailleurs avecLOAD- on ne peut pas l’obtenir en survie, mais contrairement à un bloc de commande, il ne remplace pas tout d’un seul ordre
- il peut être activé par un signal redstone
- L’élément clé est qu’un structure block en mode
LOADpeut charger une zone qui chevauche sa propre position- si le structure block actuel est remplacé par le suivant, alors chaque activation charge l’image suivante
- Mais si on remplace simplement le bloc, le nouveau structure block détecte immédiatement le signal redstone voisin et s’active récursivement
- cette récursion continue jusqu’à atteindre la limite dure de Minecraft
- elle s’arrête avant même la fin de la mise hors tension de la redstone dust, en laissant des états d’alimentation anormaux
- Ajouter un délai d’1 redstone tick avec un repeater permet d’éviter cette activation récursive
- les structures doivent être créées sous
/tick freezeafin d’enregistrer le repeater à l’état éteint - après chargement, on passe à la structure suivante un redstone tick plus tard
- les structures doivent être créées sous
Gérer les ticks pour tenir les 20 fps
- Minecraft distingue les game ticks et les redstone ticks
- le moteur du jeu recalcule la physique à 20 Hz
- les composants redstone planifient généralement leurs mises à jour par pas de 0,1 seconde, soit 10 Hz
- En pratique, les événements sont traités toutes les 0,05 seconde, et selon le moment où arrive une entrée utilisateur, la réaction de la redstone peut aussi se décaler sur cette phase
- Pour produire 20 fps, quatre structures sont utilisées
- les structures rouge et jaune forment une première horloge à 10 Hz
- les structures bleue et verte forment une seconde horloge à 10 Hz
- en démarrant les deux horloges avec des phases différentes, les quatre couleurs s’affichent à tour de rôle au même endroit à 20 Hz
- Pour lancer les deux horloges avec un déphasage stable, l’auteur exploite un ancien bug où un piston poussant un redstone block met 3 game ticks lorsqu’il est déclenché directement par une entrée utilisateur
Réduire le nombre de chunks via le pack de ressources
- Si un bloc correspond à un pixel, un écran de 512×384 occupe 24 chunks en hauteur et 32 en largeur
- au total, 768 chunks devraient être mis à jour en continu à 20 Hz
- cela se heurte aussi à la distance de rendu maximale vanilla de 32 chunks, donc ce n’est pas réaliste
- Avec des textures personnalisées dans le pack de ressources, plusieurs textures de blocs sont modifiées pour faire tenir plusieurs sous-pixels dans un seul bloc
- 16 variantes de bloc correspondent à 4 bits
- avec 256 blocs et des couleurs supplémentaires, on peut représenter du niveau de gris au lieu du simple noir et blanc
- Cette approche divise la résolution en blocs par 4, pour obtenir une représentation en 256×192 blocs
- le nombre de chunks à mettre à jour tombe à 192
- mais même ainsi, une mise à jour à 20 Hz reste très lourde
File de rendu et codage delta
- Le moteur de rendu de Minecraft traite en priorité les mises à jour de chunks proches du joueur
- plusieurs threads construisent les chunks en parallèle et récupèrent d’abord, dans la file d’attente, ceux qui sont les plus proches du joueur
- si les N chunks les plus proches sont mis à jour en continu à 20 Hz, eux seuls peuvent être traités tandis que les autres ne s’affichent jamais
- Avec Spark, le principal goulet d’étranglement observé venait des mises à jour génériques plutôt que de la redstone ou de l’éclairage
- en particulier
setBlocket les event handlers
- en particulier
- La solution consistait donc à réduire le nombre de mises à jour, en appliquant un codage delta qui ne met à jour que les blocs ayant changé entre deux images
- comme la plupart des images changent relativement peu, il y avait théoriquement un vrai gain de performance à attendre
- Un structure block ne peut charger qu’un volume maximal de 48×48×48 blocs, donc l’écran est découpé en 6×4 sous-écrans de 48×48
- Le prototype initial prenait environ 7 minutes à lancer et nécessitait
/tick freeze, 24 boutons, puis/tick unfreeze, mais il fonctionnait- le codage delta seul ne suffisait toujours pas à atteindre la vitesse voulue
Optimisation des modèles et des blockstates
- Les modèles de Minecraft définissent la forme des blocs à l’aide de cuboïdes, et les coordonnées peuvent dépasser la plage
(0,0,0)à(16,16,16)pour aller de -16 à 32- avec un bon réglage, un bloc peut être rendu comme s’il était jusqu’à 3 fois plus grand, et ainsi remplacer une zone de 9 blocs
- comme il n’y a pas assez de blocs pour couvrir toutes les combinaisons, cela n’est utile que dans des cas fréquents, comme une zone 6×6 entièrement noire
- Sur environ 600 blocs disponibles, 256 servent à la représentation de base des sous-pixels, et une partie du reste est utilisée pour l’optimisation
- L’approche finale consiste à découper l’écran en cellules de 2×2 blocs et à considérer le sprite 4×4 pixels de chaque cellule comme candidat à un remplacement par un seul bloc
- la différence entre deux images consécutives est calculée
- un score est ajouté aux versions avant et après des cellules modifiées
- dans les scènes rapides, les cellules où davantage de pixels changent reçoivent un score plus élevé
- les blocs disponibles sont affectés en priorité aux sprites les mieux notés
- Pour dépasser la limite du nombre de blocs de base, l’auteur s’est penché sur les
blockstates- comme
oak_log, certains blocs choisissent un modèle différent selon leurs propriétés - comme
grindstone, d’autres utilisent plusieurs combinaisons de propriétés comme clé
- comme
- En extrayant les variantes de blockstate des assets de base et en filtrant les propriétés incontrôlables, le nombre de modèles accessibles passe d’environ 600 à 1700
- le nombre de couleurs passe à 6
- le nombre de blocs optimisés monte à 400
Audio et dispositif de démarrage
- La musique est gérée en remplaçant, dans le pack de ressources, le son d’un disque musical
- la durée de lecture d’un disque reste fixe, même si l’audio est remplacé
- le disque Relic est utilisé car sa durée est la plus proche de celle de “Bad Apple!!”
assets/minecraft/lang/en_us.jsonest modifié pour que les sous-titres du jeu affichent “Now Playing: Bad Apple!!”
- Un assemblage de bouton, dropper, hopper et jukebox permet d’insérer le disque dans le jukebox et de lancer la lecture avec une seule pression
- à la fin de la lecture, le hopper renvoie le disque vers le dropper pour préparer la lecture suivante
- À cause de la quasiconnectivity, le signal redstone émis par le jukebox pendant la lecture perturbait l’état du hopper et du dropper
- l’entrée du bouton est donc arrangée pour que la redstone dust mette à jour le dropper
- puis, un redstone tick plus tard, un repeater réactive le dropper afin d’insérer le disque
- Pour envoyer un signal depuis la position du spectateur vers le dispositif situé derrière l’écran, l’auteur a créé un instant wire basé sur des structure blocks
- un structure block charge une redstone torch alimentée dans le segment suivant, puis celle-ci s’éteint au tick suivant à cause d’un redstone block
- cette impulsion active alors le structure block suivant et propage le signal
- comme un structure block peut couvrir jusqu’à 48 blocs, cela permet d’envoyer le signal de départ à la grille de sous-écrans 48×48
- Les quelque 150 blocs entre le spectateur et l’arrière de l’écran sont reliés par une structure séparée réinitialisable
- elle transmet le signal en créant et supprimant en chaîne des couples structure block + redstone block
- comme cette structure était difficile à enregistrer à la main en creative, les fichiers de structure ont été générés avec une bibliothèque Python
- Le mécanisme final est intégré dans une boîte 4×2×3 activable par un bouton extérieur
Prétraitement des images et qualité vidéo
- Les derniers problèmes de prétraitement étaient de réduire une vidéo en couleur complète à 6 couleurs, et de convertir une vidéo 30 fps en 20 fps
- Bad Apple!! n’utilise pas seulement du noir et blanc pur, mais aussi du niveau de gris dans de nombreuses scènes
- motion blur
- objets de luminosité différente
- dégradés dans les transitions de scène
- effets de feu, soleil, ombres ou ondulations
- Arrondir simplement à la couleur la plus proche provoque du banding
- le dithering atténue ce problème en remplaçant les couleurs intermédiaires non représentables par des motifs de couleurs voisines représentables
- Un dithering global de haute qualité peut produire des résultats très différents d’une image à l’autre
- l’œil humain remarque facilement ce manque de cohérence
- et cela génère trop de mises à jour pour Minecraft
- Un dithering local comme le Bayer dithering était stable mais de qualité insuffisante, et un ordered dithering à base de bruit bleu a servi de compromis
ffmpegne prend pas en charge le dithering en bruit bleu- les textures de bruit bleu de Christoph Peters ont été découpées en 512×384 puis appliquées avec un script Rust
- La vidéo d’origine venait d’un upload Niconico compressé avec pertes, donc bruité
- après dithering, le bruit devenait plus visible dans les zones noires et blanches
- les presque-noirs ont été arrondis au noir, les presque-blancs au blanc, et les tons intermédiaires ont été diffusés de façon à préserver la continuité
- Le problème de la réduction de 30 fps à 20 fps n’a pas été entièrement résolu
- supprimer chaque troisième image donne un espacement du mouvement différent sur les images paires et impaires, ce qui se voit
- le volume de mises à jour suit aussi un motif en dents de scie
- les versions 60 fps de Bad Apple!! trouvées en ligne avaient souvent été upscalées par IA ou par outils automatiques, avec de nombreux artefacts dans les transitions rapides
Résultat et travaux suivants
- Le projet est parti d’une résolution 48×36 en 2 couleurs, est passé par 128×96 et 10 couleurs, puis 256×192, pour finalement atteindre 512×384 et 6 couleurs
- Une tentative de lecture musicale avec des note blocks a aussi été faite, mais obtenir une bonne qualité aurait demandé un projet à part entière, donc l’idée a été abandonnée
- L’auteur a développé une technique de structstone, qui utilise les structure blocks comme de la redstone, et a aussi commencé un prototype d’ordinateur fondé sur ce principe
- Pendant le développement,
ffmpeg,mpv, la crate image de Rust, du code Minecraft décompilé et des techniques de réduction de la taille du dossier du monde ont été utilisés - L’ensemble du travail a pris plus d’un mois, avec l’aide d’amis, et a offert une manière inhabituelle d’aborder et de résoudre les problèmes
1 commentaires
Avis de Hacker News
J’ai appris beaucoup plus de choses sur l’infographie que je ne m’y attendais, et chapeau à l’auteur
Une petite correction : l’image que l’auteur appelle « The sun » montre en fait Eirin [0] en train de regarder la lune. Dans cette scène [1], Eirin tend la main vers la lune dont elle a été exilée, mais hésite puis la retire ; dans la scène suivante, Kaguya [2] tend elle aussi la main vers la lune, mais sans hésiter. D’après le wiki Touhou, le plan visant à voler la lune était celui d’Eirin, donc je ne sais pas très bien ce que symbolise exactement ce passage
[0] https://en.touhouwiki.net/wiki/Eirin_Yagokoro
[1] https://youtu.be/FtutLA63Cp8?t=99
[2] https://en.touhouwiki.net/wiki/Kaguya_Houraisan
Eirin a choisi de couper délibérément le lien avec la lune pour protéger Kaguya
Je ne comprends pas vraiment pourquoi Bad Apple est en train de devenir le Hello World de fait du rendu graphique, mais c’est amusant à voir en temps réel
J’ai aussi vu cette démo qui utilise Bad Apple pour montrer de l’hypermédia à haut framerate : https://data-star.dev/examples/bad_apple
À bien des égards, Touhou était proche d’un prototype des fandoms Internet modernes, contrairement aux fandoms précédents, et les vidéos Bad Apple utilisant le même audio ne sont pas retirées
Ensuite, le format de théâtre d’ombres reste facilement reconnaissable, même à très basse résolution. J’ai même déjà vu un exemple sur une grille 3x3. En plus, c’est du noir et blanc, donc seulement deux couleurs, 1/0, ce qui rend très facile de transformer les frames dans presque n’importe quel format imaginable, dès lors qu’on connaît le niveau « Hello World »
Ça tourne sur un CPU entièrement programmable fabriqué en Redstone. Les caractéristiques de l’IRIS Computer sont : un CPU 16 bits personnalisé, 8 kB de RAM, 64 kB de ROM, 1 kB de ROM de textures, un écran 96x64 pixels en 16 couleurs, une unité de virgule flottante (add/sub/mult/div/sqrt), une horloge à 173 ticks Redstone, pas d’accélération matérielle graphique 3D, exécution de programmes écrits en URCL, et, grâce au serveur MCHPRS, exécution à un million de ticks par seconde, soit une fréquence d’horloge de 5,8 kHz
Plutôt que de la musique avec un tempo et des mesures régulières, ça devient beaucoup plus logique si l’on imagine écouter les bits pairs d’un bus 16 bits reliés à des instruments pendant le démarrage de MS-DOS. Comme ce sont des morceaux composés par le développeur des jeux Touhou, qui créait seul des shoot’em up hardcore pour PC-88/PC-98 sans formation formelle en théorie musicale, cela semble être un résultat naturel ; c’est peut-être pour cela qu’ils peuvent paraître plus familiers à des ingénieurs en matériel embarqué qu’à des auditeurs de musique ordinaire
Un autre facteur a été la communauté nicovideo.jp / nico-tech, issue de la culture 2ch/futaba. Des utilisateurs dont l’expertise dépassait largement toute rémunération ou ambition financière — à l’époque, beaucoup étaient aussi étudiants en STEM — investissaient leur technique dans des remix juste pour le plaisir. Des magiciens FPGA inconnus, des spécialistes de drivers de moteurs et des monteurs vidéo surgissaient soudainement, lâchaient des vidéos hallucinantes puis repartaient ; c’était vraiment absurde. Maker Faire Tokyo a même, un temps, placé dans une zone séparée du site les personnes soupçonnées de porter des chemises nico-tech, au profit de développeurs web en t-shirt cherchant à sauver les apparences. L’épisode était ironique, a conduit à la naissance de rencontres nico-tech, et ne s’est pas répété. Cette densité absurde, en qualité comme en quantité de contenu, a créé l’inertie du PV Bad Apple!!
Le dernier élément clé est que le PV était monochrome — plus précisément en niveaux de gris. C’est probablement pour cela que c’est cette vidéo, et non une autre de l’âge d’or de nicovideo.jp, qui s’est imposée
1: https://www.youtube.com/watch?v=Yw5HTeT_dis
C’est aussi une œuvre d’art agréable et marquante en soi, avec beaucoup de qualités susceptibles de plaire notamment aux gens de la demoscene
Il existe aussi d’autres clips vidéo en couleur : https://youtu.be/mgfwwqwxdxY
« Bad Apple sur tout ! » fait partie de mes mèmes de geeks préférés
Quand je l’ai vu pour la première fois sur Genesis/Mega Drive, j’ai été stupéfait que ce soit possible sur un matériel aussi limité. J’aime voir de nouveaux ports réalisés sur des machines manquant de puissance. Je ne pense pas être assez doué en programmation bas niveau pour en faire moi-même, mais j’ai énormément de respect pour celles et ceux qui en sont capables
Le passage disant que « cette récursion se termine quand Minecraft atteint une limite dure et, avec un peu de chance, un bloc jaune est généré au lieu d’un bloc rouge » fait penser à l’ancien glitch de suppression de mise à jour (https://mcdf.wiki.gg/wiki/Java_Edition:Update_Suppression)
La population suppression, plus délicate (https://mcdf.wiki.gg/wiki/Java_Edition:Population_Suppressio...), peut elle aussi laisser le moteur du jeu dans un état glitché similaire, ce qui permet aux blocs de tomber immédiatement
Mon algorithme de dithering préféré pour la vidéo est le dithering de Yliluoma : https://bisqwit.iki.fi/story/howto/dither/jy/
Il est particulièrement utile pour les contenus en niveaux de gris, car trouver la matrice de dithering optimale dans la palette disponible n’est qu’un simple calcul exact, et le résultat peut être placé dans une table de correspondance pour du rendu en temps réel. Personnellement, je trouve le rendu bien meilleur que le dithering de Bayer ou aléatoire, surtout dans les dégradés
Dire quelque chose comme « la poussière de redstone est quasiment le seul composant qui ne crée pas de délai de tick, mais elle est très lente. On dirait qu’il n’y a personne chez Mojang qui connaisse les algorithmes de graphes » est excessif
Depuis l’article cité comme source par le billet original, c’est devenu beaucoup moins lent, et il y a eu de nombreuses améliorations ces trois dernières années, dont une récente. Mojang se fait beaucoup critiquer de toutes parts. Si cela a pris si longtemps de rendre la redstone moins lente, c’est parce qu’au moindre changement touchant à la redstone, la communauté crie, et qu’elle crie aussi quand du travail est fait sur autre chose que l’ajout de nouvelles fonctionnalités, ce qui rend l’effort moins rentable. S’énerver sur Internet en disant qu’ils ne connaissent pas les algorithmes de graphes n’aide pas. Mojang a recruté à plusieurs reprises des talents remarquables de la communauté Minecraft, comme Panda4994, Kingbdogz ou Gnembon, et dispose de l’expertise technique nécessaire pour faire ce qu’il veut. Ce qu’ils n’ont pas, c’est un temps et un budget infinis. Maintenir et synchroniser à la fois une base de code Java vieille de 15 ans et une énorme application C++ multiplateforme est vraiment difficile, donc j’aimerais qu’on fasse preuve d’un peu d’indulgence. Je suis fatigué de voir cette haine déferler de partout toute la journée, et j’aimerais simplement pouvoir dire que Minecraft est génial
Avant, cela m’agaçait davantage, mais j’ai fini par comprendre que c’était moins de la suffisance qu’une forme de naïveté propre aux 16–21 ans ayant peu d’expérience « professionnelle »
Ils n’ont pas vraiment l’air de se soucier de la compatibilité entre versions
Depuis le lycée, je ne suis plus assez à fond dans Minecraft pour construire des dispositifs redstone sérieux
Aujourd’hui, j’y joue avec des amis quelques fois par mois, quand l’envie de construire quelque chose et d’explorer me reprend soudainement. Quand je regarde l’écosystème redstone actuel, il est tellement différent qu’il en devient méconnaissable, et je me demande si je ressentirai quelque chose de similaire à mesure que je deviendrai progressivement ingénieur logiciel senior. J’imagine qu’avec les années, en regardant une stack que je n’ai pas touchée professionnellement depuis longtemps, je serai émerveillé par la vitesse à laquelle la technologie évolue et par les nouveautés que les gens construisent dessus
Je ne suis pas d’accord avec la réaction du type « Et… c’est tout ? Avec le recul, le résultat semble presque trivial à obtenir, et on se demande pourquoi personne ne l’avait fait avant »
C’est un excellent journal de développement, et une petite leçon sur la façon de découper une tâche qui paraît écrasante en morceaux presque impossibles, mais possibles. J’ai vraiment beaucoup aimé. À noter que cette implémentation rend Bad Apple à 20 fps dans Minecraft vanilla avec une seule texture personnalisée et quelques définitions d’objets personnalisées modifiées pour autoriser davantage de textures. Tout le reste est très exotique, mais vanilla
C’est assez amusant de voir autant d’efforts consacrés à la vidéo elle-même
En général, quand je termine une implémentation de Bad Apple, je suis trop épuisé pour penser au dithering ou au framerate : je la passe simplement dans ffmpeg et je considère que c’est fini
Il y a aussi une version de Bad Apple faite avec un monde Minecraft qui vaut le détour : https://www.youtube.com/watch?v=RN3QW9SVnds