Tout vient d'la cache

Quand Eric parlait de faire des mises à jour à la volée de la mémoire au fil de l'animation des sprites, je pensais spontanément à un système semblable à celui de Donkey Kong Country: chaque personnage se voit attribué un emplacement en VRAM et les mises à jours pour ce personnage-là viennent systématiquement à l'emplacement alloué à l'apparition du personnage. Du coup, s'il y a deux "kritters" en même temps à l'écran, il n'y aura aucun partage entre eux: le nombre d'objets à l'écran devient fortement contraint, même s'il y a peu d'images indépendantes, comme dans le cas d'Apple Assault.

In my first attempt to understand Eric Zmiro's animation engine I thought the video memory would be managed somehow similarly to what happens in DKC on SNES: every new object on screen would receive a chunk of video memory large enough for the most complex frame it has to render and it would update its content during the vertical synchronization timeslice (or at some other time slice when the GPU isn't busy looking up those pixels). To some extent, the DKC engine would be an auwfully bad choice to implement a game such as Apple Assault, where there are a large number of similar ennemies on screen and high probability that a single block of VRAM is in use by multiple ennemies at the same time. That was failing to include the key ingredient in Zmiro's engine.

J'avais oublié un élément essentiel des moteurs de jeu à la sauce Zmiro:

Chez moi, tout est en cache : Fichier, sprites, palettes, bloc... tu n'allais tout de même pas dupliquer les blocs autant de fois qu'il y a d'instance ? si ? [...] avec ce systeme (développé sur GBA en 2000), on fait actuellement l'affichage de fonte (du texte!) avec caractères proportionnel sur XBOX one et PS4, codé en utf-8 et disposant de toutes les langues y compris chinoix, japonais et coréen ! Tu vois, c'est souple.

Like for tileset used by a gigantic and varied map, Eric introduced cache management algorithm deep into the animation rendering. Animation data refer to logical blocks and the mapping to VRAM location happens dynamically, reusing blocks when possible, importing new ones only when they are not yet in VRAM somewhere else and dropping unused one only when room is needed, keeping them available for the next animation cycle when you have few sprites on screen.

With this approach, no need for pre-defined locations, no need to do spritesheet optimizations such as "let's keep only one VRAM slot for the stunned dumblador and update it from main RAM to get the desired animation on screen". For every block in the SpriteSet, all we need is an additional short integer indicating whether the block is currently missing in VRAM or stored at some location between 0 and 1023. Everytime an OAM need to be patched to reference one logical sprite block (like "page 4, block 21), you can check the corresponding VRAM slot in the spriteset and copy to a free VRAM slot if none is currently assigned.

Fini donc les emplacements pré-établis. Finies les acrobaties du genre "je vais garder une seule image pour 'dumblador assomé' sur la spritesheet et j'aurai un SprAnim qui change son contenu depuis la banque d'image restée en RAM (je fais pareil avec les vagues d'encre actuellement): pour chaque bloc de données contenues dans le spriteset, il nous faut un nombre supplémentaire, entre -1 (absent) et 1023 qui indique l'endroit en VRAM où on peut trouver cette image-là.

A chaque fois que l'on veut reprogrammer un OAM pour qu'il fasse référence au bloc "page 4, image 21", on regarde l'emplacement VRAM associé, et on en alloue un en réutilisant un emplacement libre si le bloc correspondant n'est pas encore en VRAM. Avec 1024 blocs de 16x16, on peut avoir assez de pixels différents dans les sprites pour couvrir 5 fois l'écran de la DS. Le risque d'un objet invisible par faute de mémoire vidéo est virtuellement nul. Dans mon organisation actuelle, j'ai 128Ko pour les sprites, soit moitié moins, mais ça reste tout à fait viable.

Le côté génial du truc, c'est que tant qu'on alloue sur des blocs qui ne sont pas actuellement présents à l'écran (marqués comme libres), on peut faire la mise à jour de la mémoire vidéo pendant la phase longue où le GPU retrace les pixels à l'écran. Seules les substitutions où on est obligé d'éjecter un bloc utilisé lors de l'image actuellement dessinée devront se faire pendant la phase courte émulant un "retour de balayage".

Now, how would that work with Bilou's spritesheet ? I'm currently using about 1/4th of the video memory for Bilou's heads while only one is shown at every single frame. Streaming Bilou's head into a double-buffer as the animation needs it was one of my top improvements for AnimEDS. With a Zmiro-cache, I no longer need to allocate VRAM slots to GOBs. I no longer need AnimEDS updates. And potentially, I could have the whole set of heads used by the current animation in video memory, having only gradual updates of the VRAM as I switch between actions.

Alors, est-ce que ça marcherait avec Bilou ? Un bon quart de la VRAM est utilisé actuellement pour toutes ses "têtes" et une seule est affichée à la fois. J'avais bien l'intention de faire une sorte de "streaming par double-buffer de la RAM vers la VRAM" dans une révision de AnimEDS. Le Zmiro-cache permet de passer souplement d'un double-buffer à "seules les têtes utilisées dans l'action en cours restent en mémoire vidéo". Je gagne de la place et je peux (enfin) me permettre d'autres petites animations avec des grimaces, etc.

Les mains et pieds partagés par les crayons, les taille-crayons et Bilou ? Ils n'occupent pas beaucoup de place et ont de bonnes chances de rester présents en permanence.

Shared hands and feet (used by Bilou, pendats and dumbladors) only use a small area of the whole spritesheet. It's likely a 'least-recently-used' policy would keep them permanently in video memory. Bonuses, ink drops, dust clouds would likely come and go as needed, giving more room for ennemies frames.

How many ennemies could we host ? Well the critical point is more "how much VRAM slots will be off-screen at every frame?". If you have a free (off-screen) slot for every block you need to bring in for the next frame, then you don't need time-critical copies during the blanking interval. You have 128KB of sprites memory, which means 512 different 16x16 blocks. enough to cover 2.5 times the 256x192 screen of the NDS. The gameplay will become cluttered well before you hit the cache limits. 

Les bonus, gouttes d'encre et autres nuages-de-poussière-encore-à-dessiner ferait probablement des apparitions éphémères, forçant des objets dont l'animation tient plus déjà du "streaming" (p.ex. inkjet) à faire revenir une image de la mémoire centrale vers la VRAM.

Bref, vu le nombre de fois où je me suis "cogné la tête au plafond" de la quantité de VRAM disponible juste sur le projet "School Rush", introduire cette technique de cache pour gérer la mémoire vidéo serait sans doute la bienvenue avant d'envisager un jeu plus ambitieux ... disons de la taille d'un Commander Keen ?