L’Adaptive Tile Refresh de Commander Keen

 (fabiensanglard.net)
2 points par GN⁺ 2023-07-29 | 1 commentaires | Partager sur WhatsApp
  • Adaptive Tile Refresh (ATR) est la technique de défilement utilisée dans Commander Keen 1 à 3 pour éviter le rafraîchissement plein écran trop lent de l’EGA, en ne redessinant que les tuiles modifiées au lieu de toute l’image
  • Le mode EGA Dh stocke un affichage 320x200 en 16 couleurs dans 4 plans (C0 à C3) et, si l’on écrit les 32 Kio de l’écran complet à chaque frame via le bus ISA, on tombe à environ 5 fps, ce qui rend un rafraîchissement à 60 Hz difficile
  • ATR gère les déplacements verticaux et horizontaux dans un écran virtuel via les registres CRTC_START, OFFSET et PEL, puis lorsqu’on atteint un bord, effectue un jolt pour recentrer la référence de l’écran avant de réécrire uniquement les tuiles nécessaires en VRAM
  • Le coût d’un jolt dépend du nombre de tuiles à redessiner ; dans l’exemple de Commander Keen 1, seules 40 tuiles sur 250 changent, soit seulement 16 % de l’écran, et les performances dépendent donc fortement d’une conception de carte riche en tuiles répétées
  • Commander Keen 4 à 6 abandonnent ATR au profit d’un défilement continu exploitant le wraparound de l’ouverture VRAM de 64 Kio, où seules les bandes de bord nouvellement révélées sont dessinées ; certaines cartes Super VGA ont cependant posé des problèmes de compatibilité en faisant entrer l’affichage dans de la mémoire non initialisée

Les limites de bande passante rencontrées sur EGA

  • Commander Keen fonctionnait au mieux sur les PC équipés d’une EGA (Enhanced Graphics Adapter), où la programmation graphique passait par des registres de configuration et une fenêtre mémoire de 64 Kio mappée sur la VRAM
  • L’EGA stocke ses données internes dans 4 plans C0, C1, C2, C3
    • C0 contient le bit de poids faible (LSB) de chaque valeur de pixel sur 4 bits
    • C3 contient le bit de poids fort (MSB)
    • Chaque plan comprend 200 lignes de 40 octets chacune
  • Cette architecture en 4 banques a été conçue pour fournir la bande passante nécessaire afin de suivre l’affichage CRT, le CRTC lisant 4 octets en parallèle
  • Le mode EGA Dh utilisé par Commander Keen offre une résolution de 320x200 en 16 couleurs
    • Il n’utilise pas la méthode du mode 10h, qui recompose l’encre à partir de 64 valeurs de couleur
    • Même en mode Dh, il est possible de modifier les couleurs de la palette parmi les 16 couleurs de base, ce qui sert aux effets simples de fondu d’entrée/sortie dans Commander Keen

Comment l’Adaptive Tile Refresh évite le redessin complet de l’écran

  • Le principal goulet d’étranglement résolu par ATR est la bande passante
  • Écrire à chaque frame les valeurs 4 bits des 320x200 pixels, soit environ 32 Kio, impose une charge excessive au bus ISA
  • Une boucle naïve qui rafraîchit l’écran complet à chaque fois plafonne à environ 5 images par seconde
  • L’EGA permet aussi certaines écritures simultanées sur les 4 banques, utiles pour effacer l’écran ou dupliquer les colonnes dans Wolfenstein 3D, mais peu adaptées au problème de défilement de Commander Keen

Un défilement fluide construit avec des registres

  • ATR commence par créer en VRAM un écran virtuel plus grand que la zone affichée, puis déplace cette fenêtre visible en modifiant CRTC_START, qui détermine l’endroit où le CRTC commence sa lecture
  • Le défilement vertical est relativement simple
    • En ajoutant 16 lignes au-dessus et au-dessous de l’écran visible, on utilise 40 x 232 = 9 280 octets par plan
    • Pour déplacer l’écran d’une ligne vers le haut, on augmente CRTC_START de 40 octets
    • Pour déplacer l’écran d’une ligne vers le bas, on diminue CRTC_START de 40 octets
  • Le défilement horizontal utilise conjointement les registres OFFSET et PEL
    • En réglant OFFSET à 2, on ajoute 16 octets de padding entre les lignes, ce qui laisse une marge de 16 pixels à gauche et à droite de l’écran virtuel
    • Si l’on augmente CRTC_START de 1, la structure en plans fait bouger l’écran par pas de 8 pixels, ce qui est trop grossier
    • Le Horizontal Pel Panning, c’est-à-dire le registre PEL, permet de sauter jusqu’à 7 bits après CRTC_START, rendant possible un défilement horizontal au pixel près
  • En pratique, le déplacement horizontal consiste à ajuster CRTC_START avec la coordonnée divisée par 8, puis à régler PEL avec le reste (% 8)

Le jolt et les mises à jour partielles par tuiles

  • Quand on atteint le bord de l’écran virtuel, ATR effectue un jolt pour recentrer l’écran virtuel
  • Comme un redessin complet prend environ 200 ms et fait chuter l’affichage à 5 fps, le jolt ne redessine pas tout l’écran, mais réécrit uniquement les tuiles modifiées
  • Les niveaux de Commander Keen sont construits en tuiles 16x16
    • L’artiste dessine les tuiles, puis le système de build attribue un identifiant unique à chacune
    • Le level designer place ces identifiants de tuiles dans un éditeur 2D pour construire la carte
    • Le moteur suit quels identifiants de tuiles sont présents dans l’écran virtuel
  • Au moment du jolt, il compare les identifiants de tuiles de l’état actuel de l’écran virtuel avec ceux de l’état cible une fois recentré
    • Les tuiles identiques sont ignorées
    • Seules les tuiles différentes sont réécrites en VRAM
  • L’efficacité du jolt est inversement proportionnelle au nombre de tuiles à redessiner ; les game designers devaient donc construire des tilemaps contenant beaucoup de tuiles répétées
  • Dans l’exemple de Commander Keen 1, après un déplacement fluide vers la droite qui amène l’écran virtuel à sa limite, un jolt de 16 pixels vers la gauche ne modifie que 40 tuiles sur 250
    • La part redessinée ne représente que 16 % de l’écran
  • Au-dessus du fond est dessiné un calque de sprites
    • Le moteur conserve une liste des coordonnées des tuiles salies par l’écrasement des sprites
    • À chaque nouvelle frame, il parcourt cette liste de zones sales pour restaurer les tuiles de fond avant de redessiner les sprites

Double buffering et drifting dans la seconde trilogie

  • Pour éviter les artefacts visuels, l’ensemble du système est dupliqué avec deux framebuffers
    • Pendant que le CRTC lit l’un, on peut écrire dans l’autre ailleurs en VRAM
    • Chaque buffer utilise (320 + 32) * (200 + 32) * 4 / 8 = 40,832 octets
    • Le double buffer complet occupe 40,832 * 2 = 81,664 octets, au-delà des 64 Kio de la carte EGA IBM d’origine
  • Selon VileR, seule la carte EGA IBM d’origine était équipée de 64 Kio ; la plupart des clones EGA apparus vers 1986-1987 embarquaient 256 K, et au moment de la sortie de Commander Keen, les cartes EGA de moins de 256 K étaient devenues rares
  • Dans Commander Keen 1 à 3, les motifs répétitifs exigés par ATR sont très visibles à l’écran, contrairement à Commander Keen 4 à 6 où cette caractéristique est beaucoup moins marquée
  • La seconde trilogie Keen exploite le comportement de wraparound qui fait revenir CRTC_START au début du bloc une fois la fin du bloc de 64 Kio atteinte
    • L’écran peut continuer à se déplacer, et seules les rangées de tuiles de bord nouvellement visibles sont dessinées
    • Le jolt disparaît, ce qui réduit le besoin de créer de grands champs répétitifs de couleur similaire
  • Il ne s’agit pas tant d’une nouvelle fonctionnalité que d’une amélioration supprimant le jolt
    • Les deux éléments du double buffer dérivent dans l’espace VRAM à la même vitesse, ce qui les empêche de se recouvrir
    • Dans la plupart des cas, cela fonctionne très bien
  • Certaines cartes Super VGA ont toutefois posé problème
    • Sur des cartes à l’implémentation non standard et disposant de davantage de mémoire, l’affichage pouvait ne pas revenir au début en wraparound, mais entrer dans de la mémoire réelle non initialisée
    • Plutôt que de gérer séparément chaque carte non standard, Carmack a choisi une solution plus simple : accepter un hitch à la fin de l’écran et recopier tout l’écran vers le haut
  • Cette technique de drifting a peut-être empêché de stocker tuiles et sprites en VRAM afin d’utiliser des copies rapides de VRAM à VRAM, mais comme la quantité à dessiner à chaque frame restait très faible, cela n’a probablement pas eu de gros impact

À lire aussi

1 commentaires

 
GN⁺ 2023-07-29
Avis de Hacker News

  • La fluidité du défilement dans Commander Keen 4 à 6 est restée sans équivalent sur PC pendant des années, même après le passage des jeux aux graphismes en 256 couleurs
    Grâce au travail technique impressionnant de John Carmack et aux illustrations en palette 16 couleurs d’Adrian Carmack, id a en quelque sorte créé, pendant une partie des années 1990, les jeux de plateforme les plus beaux sur PC
    Adrian Carmack n’a aucun lien de parenté avec le Carmack le plus célèbre, mais je le considère comme un maître méconnu de la palette 16 couleurs

    • C’est assez étrange de se dire que tous les jeux Commander Keen classiques ont été développés et sortis entre décembre 1990 et décembre 1991
      Le rythme des progrès graphiques et de gameplay était vraiment énorme
      L’évolution depuis le premier jeu : https://en.wikipedia.org/wiki/Commander_Keen_in_Invasion_of_...
      L’évolution jusqu’au dernier jeu : https://en.wikipedia.org/wiki/Commander_Keen_in_Goodbye,_Gal...
      J’y ai joué moi-même enfant à l’époque, et j’avais oublié à quel point tout était allé vite
    • Pour le plus beau jeu de plateforme PC d’une partie des années 1990, je choisirais Prince Of Persia
      Ce n’est pas pour dénigrer Commander Keen, mais les visuels et les mécaniques de jeu de PoP me semblaient sans équivalent pour l’époque
      Quand j’y ai joué pour la première fois vers 7 ans, ça m’a paru magique, et comme c’est encore aujourd’hui mon jeu de plateforme préféré, je suis forcément biaisé
      Bien sûr, PoP n’a absolument aucun défilement, et c’est là que Commander Keen relève de la magie noire
    • C’est peut-être un regard rétrospectif, mais une grande partie de ce développement innovant paraît assez simple comparé au développement actuel
      « La mémoire est lente, donc ne redessinons que ce qui a changé » est aujourd’hui une idée presque évidente
      Cela dit, les optimisations des épisodes 4 à 6 sont intéressantes. Dans les épisodes 1 à 3, ils faisaient tout le travail en supposant que le tampon ne revenait pas au début, mais en réalité il le faisait, ce qui rendait ce travail inutile — c’est aussi un point fascinant
    • Et Jazz Jackrabbit ? Ce jeu aussi avait un défilement VGA vraiment fluide

  • J’ai déjà créé un jeu à base de tuiles sous Windows 98 avec DirectX 5, et au départ j’avais implémenté une approche proche de celle décrite dans cet article
    L’écran ne défilait pas, mais comme il pouvait falloir redessiner beaucoup de tuiles, la situation était un peu plus simple
    J’ai fini par retirer tout ce code, parce qu’en profilant le coût du rendu plein écran sur une carte RIVA TnT, le temps pris était si faible qu’il était même impossible à mesurer
    Je suis content d’avoir raté l’époque EGA dans le développement PC. À cette époque-là, je crois que je n’aurais jamais rien terminé

    • Moi, au contraire, j’aimais cette programmation bas niveau
      Optimiser avec des décalages de bits au lieu de multiplications, écrire le code critique en assembleur, puis, à mesure que les processeurs progressaient, écrire 16 ou 32 bits à la fois
      J’avais peu de ressources, alors je continuais à apprendre avec des livres de la bibliothèque locale et des disquettes remplies de fichiers txt
      J’étais trop jeune et trop inexpérimenté pour terminer quoi que ce soit, mais j’avais réussi un défilement vertical fluide, presque fait fonctionner le défilement horizontal, et implémenté le double buffering d’un cube 3D en rotation. Ça incluait même le tampon de profondeur, les maths et le dessin de polygones ligne par ligne
      Puis DirectX est arrivé, le contact direct avec la machine a disparu, et faire tourner un cube 3D est devenu si facile que ce n’était plus amusant
    • Déjà à l’époque, l’écart entre les cartes graphiques les plus lentes et les plus rapides se creusait beaucoup
      Le bus passait de 8 bits à 16/32 bits, les cartes graphiques prenaient en charge les écritures différées (posted writes), ce qui faisait moins attendre le CPU, et les CPU devenaient aussi plus rapides, si bien que les systèmes rapides pouvaient écrire un écran 640x480x256 à plus de 300 images par seconde
      Dans ce cas, il s’agissait peut-être d’un tampon en mémoire système mise en cache avec copie DMA, ou bien le blitter se chargeait du dessin. Mais même à l’époque de Windows 98, certaines cartes 3D bas de gamme avaient un accès CPU très lent, à peine meilleur que celui de vieilles cartes sur bus ISA
      Avec la hausse énorme des résolutions d’écran, on observe aujourd’hui une sorte de retour en arrière partiel. Même si l’on peut redessiner un plein écran 4K à 60 images par seconde, on peut difficilement dire que ce soit efficace
      Les jeux redessinent généralement toujours tout, mais les compositeurs de bureau font pas mal d’optimisations, par exemple en affectant dynamiquement des couches à des plans matériels pour réduire les zones à redessiner

  • Je travaillais à la même époque dans une autre société de jeux, et j’avais trouvé moi-même une technique de défilement similaire à la deuxième approche
    Je ne pense pas que ce soit si extraordinaire. Si l’on résolvait le même problème à l’époque, on serait probablement arrivé à une conclusion semblable
    J’avais aussi créé mon propre pilote audio PWM pour jouer des échantillons sonores sur le haut-parleur PC, et il semble que tout le monde faisait pareil
    Le PC n’a pas reçu assez d’amour avant que nous passions tous aux consoles. Des démos comme 8088 MPH de Hornet me donnent encore des frissons

    • Si le jeu est sorti, pourrais-tu donner son titre pour qu’on puisse comparer ? Je suis d’accord que la plupart des gens auraient imaginé des solutions similaires, mais je suis curieux de savoir si le résultat en jeu donnait la même impression
    • Si ce n’était pas si impressionnant, pourquoi tant de jeux de plateforme à défilement parmi les meilleurs de l’époque étaient-ils encore aussi saccadés ?
      Ce n’est pas une condition indispensable pour qu’un jeu soit amusant, mais la fluidité montrée par Keen, surtout sur du matériel modeste à moins de 10 MHz, était vraiment spectaculaire pour l’époque
    • La réputation vient souvent non pas de l’invention elle-même, mais de la capacité à la commercialiser et la promouvoir
      Il a dû exister d’innombrables grandes inventions restées inconnues pendant des millénaires
      Moi aussi, j’ai « inventé » quelque chose de similaire à LinkedIn dix ans avant son arrivée, mais je n’ai pas réussi à le commercialiser. Je pense que la plupart des inventions ne deviennent jamais largement connues
      C’est pour cela que beaucoup de startups démarrent à deux personnes : un expert et un commercial
      Donc ce n’est pas faux. Cette invention n’a peut-être rien d’exceptionnel en soi, mais elle l’est devenue par la combinaison de la nouveauté, de l’utilité et d’une commercialisation réussie

  • L’excellent livre Masters of Doom explique que Keen était un jeu à la Mario, c’est-à-dire à défilement horizontal.
    id avait proposé cette technologie à Nintendo comme option pour porter Mario sur PC, mais Nintendo a refusé, et c’est ainsi que Keen est né.
    Ce fut un énorme bond en avant pour le jeu PC, et cela a ouvert une nouvelle ère du jeu sur PC.
    Ce que je ne comprends toujours pas très bien, en revanche, c’est ce qui différenciait tellement les technologies de la NES et du PC pour que Nintendo ait pu implémenter le défilement horizontal plusieurs années avant le PC.

    • EGA fournit essentiellement un grand framebuffer.
      En mode graphique EGA, on peut dessiner arbitrairement ce qu’on veut — des lignes, des cercles, des pixels individuels, etc. — et c’était conçu pour être utilisé ainsi.
      Mais le scrolling n’est pas gratuit. Il faut copier directement de la mémoire, et comme le montre l’article lié, si l’on force brutalement la chose, la limite de bande passante du bus ISA fait qu’on n’obtient qu’environ 5 images par seconde.
      La NES et les autres consoles 8/16 bits n’étaient pas conçues pour dessiner n’importe quoi. Elles étaient conçues pour rendre des tuiles.
      Il suffisait de définir une grille de tuiles d’arrière-plan et de fournir un offset de défilement. Les sprites fonctionnent de manière similaire, mais peuvent se déplacer indépendamment. Tout cela est fourni gratuitement à 60 images par seconde.
      L’inconvénient, c’est qu’il n’est pas facile de rendre des éléments arbitraires. Par exemple, colorier un seul pixel quelque part demande des contournements assez lourds.
      Ce n’est pas tant que Nintendo aurait « découvert » le problème avant IBM : IBM a conçu un système graphique généraliste adapté aux ordinateurs polyvalents et aux graphismes statiques, offrant un contrôle fin sur chaque pixel. Quand on regarde une carte EGA, c’est un dispositif assez massif, avec beaucoup de silicium.
      À l’inverse, Nintendo a conçu un système graphique dédié beaucoup plus simple, optimisé pour faire glisser des tuiles.
    • En réalité, ils avaient créé un portage de SMB3 et l’avaient montré à Nintendo.
      Quand Nintendo n’a pas accepté, ils ont créé de nouveaux assets, qui sont devenus plus tard Keen.
      La vidéo du portage est ici : https://youtu.be/1YWD6Y9FUuw
    • Je n’en suis pas certain, mais si je comprends bien, la NES avait une puce graphique dédiée à la manipulation des sprites, alors que sur PC tout cela devait être fait en logiciel.
    • La méthode décrite dans l’article consiste à imiter en logiciel, avec un framebuffer de pixels indépendants, les tuiles gérées par le matériel.
      Pour la NES, https://www.nesdev.org/wiki/PPU semble être un bon point de départ.
      Le cœur du défi n’était pas « trouver comment faire du défilement horizontal » en soi, mais adapter un moteur de jeu à défilement horizontal pour qu’il fonctionne bien malgré l’espace mémoire et les contraintes de bande passante d’un système complètement différent.
    • Il me semble que la NES et la GB étaient basées sur des tuiles.
      Comme les jeux étaient construits autour de sprites avec des couches, cette façon d’« accélérer » la 2D avait pas mal de sens.

  • Dans l’interview de John Carmack par Lex Fridman, ils passent en revue toutes les grandes innovations de chaque jeu.
    C’est un épisode vraiment passionnant, que je recommande fortement si vous avez le temps. Il dure environ 5 heures.

  • Je me souviens encore de l’époque où je croyais connaître presque tous les secrets de Commander Keen Goodbye Galaxy.
    Des camarades de classe me demandaient de leur révéler les secrets des niveaux auxquels ils jouaient sur les ordinateurs de l’école après les cours.

    • Quelle chance. Dans mon école, à ma connaissance, j’étais le seul geek à avoir jamais entendu parler de Commander Keen.

  • Quand je vois fabiensanglard.net, je recommande immédiatement.

    • C’est vraiment une pépite. Son livre sur le CPS1 est également excellent.
      Si quelqu’un connaît d’autres blogs de jeux rétro avec une vraie profondeur technique, j’aimerais qu’il les partage.
      https://nicole.express/ et https://sudden-desu.net/ font aussi partie de mes favoris.

  • J’ai compris comment le défilement vertical fonctionne quand on ajuste le point de départ du framebuffer par scanline, mais au début je ne voyais pas clairement comment le défilement horizontal pouvait être possible sans tordre fortement le framebuffer.
    En y réfléchissant un peu plus, j’ai réalisé que c’était un peu comme dessiner une image sur le côté d’un cylindre. Peu importe où l’on dessine le bord gauche de l’image : en faisant tourner le cylindre et en réglant les registres CRTC_START et PEL, il existe toujours un moyen de voir l’image entière nettement.
    Le passage disant qu’« une fois arrivé au bord de l’écran, la solution simple consistait à accepter un à-coup et à copier tout l’écran vers le haut » est également intéressant.
    Je me souviens qu’au lancement de Keen, un message du genre « VGA compatibility mode enabled » apparaissait généralement, et je me suis toujours demandé ce que cela signifiait.

  • Commander Keen était vraiment un petit jeu adorable
    Il faut que je trouve un moyen de le relancer
    Mais comment faire au mieux ? Je n’ai pas utilisé Windows depuis environ 20 ans, depuis que je suis devenu « adulte » ; comment puis-je y jouer sous Debian ?

    • Jouable directement : https://archive.org/details/msdos_Commander_Keen_1_-_Maroone...
    • Je ne suis pas d’accord. C’était un jeu pour les enfants qui, pour une raison ou une autre, avaient accès à un ordinateur mais pas à une Nintendo
      À l’époque, les ordinateurs coûtaient environ 10 fois plus cher que les consoles, donc c’était généralement parce que les adultes avaient des idées bien arrêtées sur ce que l’enfant devait faire
      Comparé aux jeux NES et Genesis, il manque d’âme. Je l’aimais bien à l’époque, mais en y rejouant récemment dans DosBox, j’ai clairement senti qu’il ne tenait pas la comparaison
    • DosBox fait très bien tourner les vieux jeux VGA, et fonctionne sur presque toutes les plateformes, y compris dans le navigateur : https://archive.org/details/msdos_Commander_Keen_1_-_Maroone...
    • Ce sera probablement DosBox
    • Commander Keen et Jill of the Jungle sont les jeux qui m’ont fait découvrir le PC à l’époque. De très bons souvenirs

  • Il y a quelques années, j’ai implémenté la deuxième méthode, mais même en ne dessinant que le bord avant, c’était très lent
    Cela dit, c’était écrit en C, et je n’ai jamais vraiment appris la programmation en assembleur
    https://github.com/geon/kate/blob/master/src/platform/dos/eg...