Aladdin Sources Analysis

They made a wonderful job at gamehistory.org, based on an in-depth analysis of the sources of the Mega-drive game "Aladdin". The game was made by David Perry's team who also brought us Cool Spot. At the core of their work is a technique and a toolset to allow more flexibility in animating graphics on 16-bits system that had read/write video memory on-board (as opposed to NES with read-only video memory alone, on the cartridge) and fixed-size sprites (e.g. 16x16, 16x32, 32x32).

Everything else will seem silly to you if you do not accept that, by then, getting more KB of memory for your game was very - very - hard. The size of your game was decided by non-technical people based on how much the console vendor would charge for a 2Mbit chip, when the game should came out and how much kids would be allowed to spend given which license you'd be using. So they have early planning deciding how much to dedicate to sprites, levels, code, maps, etc. Based on that, they'll decide how much levels there will be in the game, etc.

Of course, game characters animation all started by having characters whose size fit the hardware requirements (mario nicely stands within a 16x16 box and a 16x16 mushroom makes him 16x32), flipping from one sprite to another within an all-in-VRAM bank. Then some special characters (the hero) would get a special status and only get one or two VRAM slots dynamically updated. To crunch more animation frames, one could use run-length-encoding compression that does wonders on row of pixels of identical color. Others have used 2/3-bit-to-4-bit decompression once realizing that Link sprite (and all others) only need 8 colors per palette, not 16. But all this requires CPU, and the CPU resources too, were limited (Not even 8MHz. Less than my good old 80386).


If we could instead keep the same binary format between the ROM and the RAM, having the right picture in video memory at the right time is all a matter of "blasting" them through the Direct Memory Access chip. See that big line on my notes ? that's the DMA doing its job, while the CPU can focus on crunching numbers to make the game physics stunning and fun...

To make that possible with fun stretch-and-squash, cartoon-like animation, they ultimately relied on their chopper tool that cuts pictures into hardware-sized sprites. Just like the one I imagined for Titus's Prehistorik II sprites.

Ok, granted, it doesn't look completely automated. But the idea is clearly there. And ultimately, it would run on a system that has 1/4 of the power of my Nintendo DS.

So, am I allowed to dream of porting some libgeds game on 16-bit engines ? Well, with the engine refactoring that splits script parsing, it is pretty tempting to see what we could do about it.


Let's start with the animations, thus. What is weird with the animations is that their code has to interrupt every here and there when there is some delay. In high-level language, we'd likely use a switch construct branching you to frame T or frame T+1 code depending on some argument we'd pass to the function. But if we're generating machine code instead, we can do much better. We can then have the actual next animation instruction remembered, rather than an index into an array of virtual instructions. No more conditionals and branch delays on that non-speculating old CPU. Just one jump.

Implementing "keep that state for N screen refreshes" is then looking a lot like software multi-threading: you have a call to some yield_animation micro-routine (and saving your current position into the generated animation code on the stack), which will pop that resume position into some CPU register (an internal scratch variable, in case you didn't know yet), and then return to the code that called animate_aladdin, letting it save the next animation position where it sees fit. Looping animation ? super-easy ! Have you seen how much boilerplate the current virtual-RISC-processor-for-animations of libgeds and AnimEDS must deal with instead ?

What else ? State machine of course. State machines are built with simple expressions used either to guard transition (only let them used when some condition is met) or to define what to do when the transition occur (besides changing states, that is, like playing a sound, changing speed, etc).

The collision system currently will follow a list of GobExpressions calling eval(guard_predicate) until one returns true, then proceeding with eval(action) and changing state. Instead, with generated machine code, that would all be packed into a sequence of predicate code that branch to the appropriate action code or keep testing until we hit the "okay, then nothing happens" terminator that returns to the collision system itself.

One day ... maybe. That would be much more interesting on 16-bit than it would be on DS or native x86_64 code, anyway.

edit: for more background information about how things actually came into existence, seeing tools and teams in action, don't miss the excellent "Splash Wave" episode on the game.
 

Tutoriel Libgeds - Jour 1

Salut à tous. Vous le savez déjà, je fais des programmes et des jeux sur Nintendo DS. L'idée, c'est que tout ce que j'ai fait devrait permettre à d'autres d'en faire autant. J'ai commencé une repasse sur mon code pour montrer petit à petit comment se servir de mes outils et de mon moteur de jeu.

Pour ça, il vous faudra d'abord le kit de développement non-officiel pour NDS et GBA. Ils ont fait du bon travail et il y a un installeur automatique pour ceux qui travaillent sous Windows.

De mon côté, j'ai préparé une structure d'accueil pour les programmes. Règles de génération des ROMs nds à partir des sources et des données du jeu, les petites bibliothèques supplémentaires pour faire de la musique, etc. Et un un premier programme à faire tourner sur DS. Evidemment, on est sur une machine "bare metal", sans système d'exploitation, donc il y a un peu plus de code d'initialisation qu'à l'habitude, mais le fait de créer un objet "Engine" fait déjà une grande part du travail.

Code:

void setactive() {
    FileDataReader fd("efs:/sndtrk.xm");
    ntxm9->stop();
    u16 err = ntxm9->load(&fd);
    ge.setWindow(active);
    if (err!=0) iprintf("ntxm says %x\n",err);
}

Un premier morceau, qui charge un morceau de musique (on en trouve d'autres du genre sur modarchive.org). Il sera joué sur le processeur secondaire de la console, l'ARM7. L'objet ntxm9 nous permettra de transmettre des commandes du genre "passe moi la fanfare de fin de niveau" ou "joue un bruit d'explosion" au fil du jeu.

Je propose deux manière d'interagir avec les boutons et l'écran tactile de la console: l'un pour la partie "action" du jeu (pas encore dans le tuto), et l'autre qui me sert pour les éditeurs: ge.setWindow() a défini notre objet window comme étant l'activité actuelle, donc le moteur appellera la fonction ci-dessous chaque fois qu'on pousse sur un des boutons.

Code:

bool handle(uint& keys, Event evt) {
    if (keys & KEY_A) {
      ntxm9->play();
    }
    if (keys & KEY_Y) {
      ntxm9->stop();
    }
    return true;
}

Allez, la prochaine fois je vous raconterai comment mettre des images à l'écran

Tutoriel libgeds - jour 2

Bon, avant de voir comment le moteur 'GEDS' peut charger des images dans la mémoire vidéo de la Nintendo DS, il faut que je vous explique un peu comment son processeur graphique construit les images que l'on voit à l'écran. J'utilise le mode "texte", ici, où les images sont composées d'élément de 8x8 pixels appelés "tiles" (prononcez 'taïlesz') que l'on dispose sur une grille.

Vous avez tous déjà utilisé un éditeur de donjons RPG où l'on travaille carré par carré (je crois qu'on dis volontiers des 'chips' ?) plutôt que de mettre un arbre ou une maison d'un coup. Le mode texte de la DS va un cran plus loin: la mémoire de la machine elle-même est découpée en une région pour retenir des pavés de 8x8 (le 'tileset') et une région pour indiquer quel pavé montrer à quel endroit (la 'map' de l'écran, couvrant généralement 256x256 pixels pour la DS). Parfois, on mettra le même tile à plusieurs endroit de l'écran (en inscrivant juste son numéro dans plusieurs cases de la map), et parfois un tile ne sera pas repris (pour l'instant). C'est une technique a peu près aussi vieille que les machines 8-bit et qui a perduré pendant toute la période 16-bit (mais ça, c'est une autre histoire). Ce qui a changé au fil du temps, c'est le nombre de couleurs autorisées par tile (de 3 pour la NES à 255 pour la NDS) et le nombre de calques que l'on peut superposer pour obtenir l'image souhaitée (jusqu'à 4 sur la NDS).

Les fichiers .spr créés par le SpriteEditor pour DS sont principalement une sauvegarde du contenu de la mémoire vidéo tel qu'on voudrait l'avoir pendant le jeu. Du coup, il n'y a vraiment pas grand-chose à faire pour pouvoir les importer dans son programme.

Code:

  SpriteRam myRam(WIDGETS_CHARSET(512));
  SpriteSet mySet(&myRam, BG_PALETTE);

  mySet.Load("efs:/bg.spr");

Et voilà. quelques précisions pour dire au moteur de jeu où mettre les graphismes (ici, sur l'écran "du haut", en laissant 512 emplacement pour une police de caractère et pour les 'maps' des différents calques) et où mettre la palette de couleur présente dans le fichier .spr (également dans la mémoire de palette de l'écran supérieur). La classe SpriteSet du moteur de jeu s'occupe de manipuler le fichier et d'en reconnaître le format. On pourrait aussi prendre le contrôle de toute la mémoire vidéo en utilisant directement myRam(BG_GFX), mais c'est un peu moins confortable pour la suite.

Bon, malheureusement, avoir des graphismes en mémoire ne suffit pas pour les avoir à l'écran. La démo n°2 doit aussi configurer la puce graphique pour qu'elle utilise nos données et remplir la grille/map d'un des calques.

Code:

REG_DISPCNT|=DISPLAY_BG2_ACTIVE;
REG_BG2CNT=BG_MAP_BASE(GEBGROUND)|BG_TILE_BASE(0)|BG_COLOR_256;

La configuration, on va régler ça en programmant directement les registres de la puce graphique. C'est tellement facile sur DS . J'active le bit correspondant au calque n° 2 (j'l'aime bien, celui-là) dans le contrôle principal de l'écran (REGister_DISPlayCoNTrol), puis je donne les paramètres de ce calque dans son registre à lui: les données des tiles seront interprétées comme ayant 256 couleurs, quelle grille utiliser comme map, et si je veux ajouter automatiquement un décalage à tous les numéros de tiles de la map (BG_TILE_BASE) par rapport à la position dans la mémoire du tileset (ce que je ne fais pas ici).

La bibliothèque 'libgeds' donne des paires de noms à différentes grilles: un nom pour la configuration de BG_MAP_BASE, et un nom pour le tableau correspondant dans la mémoire vidéo (WIDGETS_BACKGROUND). Du coup avec la configuration qu'on vient de faire, on peut changer le pavé en haut à gauche de l'écran en écrivant dans WIDGETS_BACKGROUND[0]. Dans celui en haut à droite avec WIDGETS_BACKGROUND[31] (parce qu'il y a 32x8 dans 256 ) et WIDGETS_BACKGROUND[32] sera le pavé juste en-dessous de WIDGETS_BACKGROUND[0]. Et ainsi, ligne après ligne. Bref, avec un peu de sucre et une feuille de papier, vous arriverez rapidement à voir que WIDGETS_BACKGROUND[32*ligne+colonne] vous permet de modifier n'importe quel emplacement de l'écran.

Code:

for (int l=0; l<32; l+=2) {
  for (int b=0; b<8; b+=2) {
    WIDGETS_BACKGROUND[b+l*32]=tile++;
    WIDGETS_BACKGROUND[b+l*32 +1 ]=tile++;
    WIDGETS_BACKGROUND[b+l*32 +32]=tile++;
    WIDGETS_BACKGROUND[b+l*32 +33]=tile++;
  }
}

Moi, j'avais envie de montrer l'ensemble des graphismes de mon fichier .spr, tels qu'on les voit dans l'éditeur. Et dans le quart le plus à gauche de l'écran (une zone de 64x192 pixels). Il reste un petit truc à régler: l'éditeur travaille par blocs de 16x16 pixels, pour le confort du graphiste. En interne, un bloc est composé de 4 tiles de 8x8 pixels, agencés eux aussi suivant le mode "une ligne, puis l'autre". Si je veux que les blocs ne se retrouvent pas coupés en 2, je dois respecter cet agencement au moment de remplir la grille:

Code:

/* 0 1
 * 2 3
 */

D'où les boucles qui passent une ligne sur deux et les quatres écritures à WIDGETS_BACKGROUND par itération.

Voilà. Le code est sur github, donc. Avec le fichier .spr (creative common)


N'hésitez pas à me ralentir avec quelques questions si ça va trop vite pour vous.

Tutoriel libgeds - jour 3

Un des éléments les plus importants dans un jeu vidéo (2D), ce sont sans doute les sprites. Rien à voir avec une boisson pétillante, il s'agit du terme consacré pour les objets graphiques librement déplaçable à l'écran, y compris le personnage principal, les adversaires, mais aussi certains power-ups ou des effets spéciaux.

Les sprites ont besoin de données graphiques (des valeurs de couleurs) tout comme les décors, et ces données sont de nouveau constituées de "tiles". On va utiliser surtout des blocs de 16x16 pixels ici (et donc constitués de 2x2 tiles) mais la DS peut en réalité utiliser des sprites de 8x8 à 64x64 pisxels (avec quelques restrictions quand-même).

Mettre à jour la mémoire vidéo pour que les sprites s'affichent à l'écran (quels graphismes, quels réglages, etc) est délégué à la classe SpritePage dans la libgeds, et la fonction "sync()" de GuiEngine fera le nécessaire pour mettre à jour les coordonnées en respectant les timings de la puce vidéo (et faire en sorte que ça ne clignote pas, par exemple).

The English version of these tutorials sit at https://gbatemp.net/threads/tutorials-for-my-game-engine.497728/, where they are hopefully more likely to connect to potentially interested users. I once had the French version hosted on a forum too, but that forum is now defunct, so I'd rather bring them back home before the forum goes broken.

Les SpritePages ajoute un niveau de correspondance entre les identifiants logiques des graphismes (ceux que le développeur utilise, "c'est sur la page 3, deuxième ligne, première colonne) et les emplacement "physiques" dans la mémoire vidéo (42eme bloc sur 256 en mémoire). Bref, le contenu de la SpriteRam est généralement un joyeux chaos résultant des créations et supressions de blocs alors que chaque SpritePage est organisée exactement comme l'utilisateur le décide.

le brol de la SpriteRam	la SpritePage, aussi organisé que vous

Code:

class Hero : private UsingSprites {
  NOCOPY(Hero);
  const SpritePage *page;
  unsigned x, y;
  oamno_t oam;
public:
  Hero(const SpritePage *pg) : page(pg), x(128), y(96),
         oam((oamno_t) gResources->allocate(RES_OAM))
  {
    page->setOAM((blockno_t)2, sprites);

  }

  void move(int dx, int dy) {
    x += dx; y += dy;
    iprintf("(%u,%u)", x, y);
    page->changeOAM(sprites + oam, x, y, (blockno_t) 4);
  }
};

Notre petite classe 'Hero' montre tout ce qu'il faut pour avoir un objet mobile:
- se souvenir des coordonnées (le bon mot pour parler de la position à l'écran) actuelles;
- une SpritePage qui sait comment mettre à jour les entrées de la "MAO" (ou Mémoire des Attributs d'Objets -- Object Attribute Memory -- le terme de Nintendo pour parler des blocs de contrôle des sprites);
- avoir réservé une entrée de MAO et en retenir le numéro.

En disant que notre classe dérive de "UsingSprites", on obtient l'accès au tableau des MAOs (le tableau 'sprites[]') que le moteur de jeu va utiliser pendant la fonction sync(), mais aussi au gestionnaire de ressources (`gResources`) qui nous donne notre numéro de MAO. Du coup, la SpritePage a tout ce qu'il lui faut pour faire son travail.

Code:

void setactive() {
   SpriteRam myRam(WIDGETS_CHARSET(512));
   SpriteSet mySet(&myRam, BG_PALETTE);

   mySet.Load("efs:/bg.spr");
/*+*/ sprSet.Load("efs:/hero.spr");

  // rest of MetaWindow::setActive() as defined in previous tutorial
/*+*/ hero = new Hero(sprSet.getpage(PAGE0));
}

Charger les graphismes des sprites en mémoire vidéo ressemble très fort à ce qu'on a déjà fait pour les décors dans le tutoriel précédent. Sauf que cette fois, il faut s'assurer que les objets "SpriteSet" et "SpriteRam" resteront 'en vie' au moins aussi longtemps que notre Hero (qui les utilisera à travers la SpritePage). Du coup, on en fait des membres de la MetaWindow, plutôt que des variables temporaires. Ça signifie aussi qu'il nous faut attendre que les données soient chargées avant de pouvoir créer notre Héro.

Puis il n'y a plus qu'à tester l'état de la croix directionnelle (et les transmettre par des appels à la fonction 'move()') pour pouvoir déplacer le personnage en réaction aux mouvements imprimés par le joueur. Bon, ne vous attendez pas à quelque-chose de fluide ici: j'utilise toujours l'interface utilisateur prévue pour les éditeurs du projet "GEDS" qui ne produit un 'évèment DPAD' que lorsqu'on appuie sur une nouvelle direction. On arrangera ça la semaine prochaine avec les Animators.

Code:

if (keys & KEY_UP) {
  hero->move(0, -4);
}
if (keys & KEY_DOWN) {
  hero->move(0, 4);
}
if (keys & KEY_LEFT) {
  hero->move(-4, 0);
}
if (keys & KEY_RIGHT) {
  hero->move(4, 0);
}

Les détails sont sur github, comme toujours.

Biggest Refactory Ever

For me, at least. I wanted to make the scripts occur as soon as possible in my tutorial series, since the GEDS engine is meant to allow game-making even for those who don't know about C++ programming. But I also want to be able to introduce a behaviour editor, which suggests that the same script-parsing logic should be able to drive either the game engine or the state machine model in the editor.

So this last week, I've been busy splitting the big singleton "GameScript" that had both the parsing logic and the engine intimacy into two classes, the ScriptParser that knows the language rules and the Game* objects well enough to create them but has no knowledge about the Nintendo DS resources or the game engine per se, and the GameScript, that knows about the engine's runtime, last as long as the level does, hold resources and the like.

ça bosse ferme ... restructuration du lecteur de scripts pour pouvoir introduire un éditeur de machines d'état ...

I've finally reached a point where all my automated tests work again. Of course, School Rush isn't running fine in this branch ... yet.

edit: Okay, SchoolRush runs fine again in the emulator. Just some un-initialized arrays. -Weffc++ should have caught that, though.

Scribble Widget

quelques petits essais (dans SEDS) de ce que donnerait un système de reconnaissance d'écriture avec soit 8 pixels ou 6 pixels par "cellule". Je préfère 6. La police 8x15 juste à côté servirait pour les caractères reconnus (une fois le tracé terminé).

libgeds Animator system

Je pensais réécrire une partie du système d'animation. Il est inspiré d'un gestionnaire d'évènement à retardements pour systèmes d'exploitations. Sauf que dans le cas des sprites dans libgeds, à peu près tout est exécuté à chaque image. Ne serait-ce que parce qu'il me faut compenser les mouvements de la caméra.

I had somehow convinced myself that the animation scheduler system of libgeds needed a rewrite, that scanning through the list of animators to push new content in the middle everytime some new object was shot was a mistake, and that everything would work better, faster and stronger if I had a list of 'play every frame" in addition to the current list of "play when delay expires". But actually, the insertion policy is somewhat different: we insert _before_ any item that has the same delay, therefore making most in-game insertion as trivial as 'insert at the head of the list'.

Je craignais qu'il y ait régulièrement des éléments qui doivent inutilement être placés en bout de file d'attente parce qu'il y a de nombreux autres sprites à animer, et tous avec le même délai. Mais en fait, il n'y a pas besoin de modification. A cause d'un tout petit détail dans sa définition "place a après tous les animés qui ont un délai strictement inférieur". Donc tous les éléments qui ont le délai minimum (les objets et personnages du jeu) seront placés en tête de liste, temps d'exécution minimum aussi.

libgeds tutorial

I have just started a github with one branch of the dsgametools project: the 'tutorials' branch, where I'm reconstructing and detailing step by step the components of the (refactored) game engine... together with Creative-Commons pictures and sounds to make demos on a regular basis.

Additional chatting and promotion of the tutorials happen in gbatemp and e-magination forums.

Cette fois-ci ça y est. J'ai transféré la branche "un tutoriel après l'autre" sur github. Pour que chacun puisse facilement suivre ma tentative de réécrire le moteur des jeux Bilou. Histoire que les différentes fonctions disponibles soient capturées clairement, et non pas éparpillées sur une demi-douzaine de patches.

On verra bien si ça intéresse du monde...

the mercurial-to-git conversion is performed by the fast-export tool from Frej. The process looks as follows:

cd hg2git/
cd dsgametools-hg/
# hg incoming -r $(hg id -b)
hg pull -r $(hg id -b)
cd ../tutorials-git/
../fast-export/hg-fast-export.sh -r ../dsgametools-hg
# git log
# git push --dry-run git@github.com:PypeBros/libgeds-tutorials.git
git push git@github.com:PypeBros/libgeds-tutorials.git
cd ..

The "last" map

Allez, je me suis bricolé une dernière map pour School Rush: la récompense pour ceux qui seront parvenus à grimper jusqu'en haut du "niveau secret". Il y aura une présentation des monstres, bien sûr, mais aussi une petite surprise qui m'a pris du temps à mettre au point. Au niveau de l'idée, je veux dire.

I sketched up a last map for School Rush, that will be the final reward to players who beat the secret climbing challenge. It took me some time to nail down the idea I wanted to have, but I think all I have to do now is some pixels and some scripting. And making sure I can restrict the part of the level that the camera can show. I'll have to keep the todo list off-line, though so that you have a real surprise ;-).

Côté réalisation, je vais avoir besoin, pour la première fois, de restreindre les mouvements de la caméra. Il me faudra aussi une petite variante de la gomme, quelques graphismes sur tableau vert et un mode "calmos" pour les encriers... Pas facile de se faire une todo liste pour un truc qui doit rester secret >_<

edit: since many of the monsters' behaviour is slightly different here, how about #ifdef LAST_MAP in the .cmd files that can lead to e.g. inkjet.cmd vs. inkjet_last.cmd ?

__lock_jiffies

Perdu dans un petit coin d'un driver Linux, une fonction sympa qui augmente un des verrous avec un chronomètre ... histoire de voir combien de temps on est resté en section critique.

Je devrais peut-être bien ajouter quelque-chose de ce genre avec parseLine() dans GameScript, tiens.

Et capturer le numéro de ligne des transitions crées, ce ne serait pas mal non plus.