Monday, December 22, 2014

Keen's Inception

Coincé entre deux générations de "game engine" de la série commander keen, on trouve un jeu étrange, faisant presque figure de "lost levels": Keen Dreams. Une grande part du design global de l'excellente série "Goodbye Galaxy" est présent: décor en perspective cavalière, personnage de 40 pixels de haut, environnements variés et son SoundBlaster. En revanche, keen se promène en pijama et en pantoufle et ne dispose ni de son neurolaser, ni de son célèbre pogo. A la place, Keen peut lancer en cloche des mines transformant les ennemis en fleurs à leur contact. Le gameplay demande donc beaucoup plus de précision que dans les autres épisodes, d'autant plus que les ennemis ne resteront pas transformés éternellement. Ça n'est pas sans rappeler le lancer de taille-crayon dans Bilou, je l'avoue, mais si je vous en parle, c'est surtout à cause de ses sources, ajoutées sur github début septembre, et que je suis occupé à analyser. Les sources sont essentiellement en C avec quelques blocs d'assembleur en ligne, chose plutôt rare pour l'époque.

Bien sûr, j'aurais préféré que Javier et Chuck nous proposent le code de Goodbye Galaxy, notamment à cause de l'absence de pogo dans cet opus, mais c'est le premier Keen à proposer des pentes, ce qui n'est déjà pas si mal.

Keen Dreams' source code has been released last September. I wish it was the code for one of the Goodbye Galaxy episodes, of course, as it is one of the games I played the most, and the one with the richest features set -- pogo, gun, moving platforms and shooting ennemies -- which isn't crippled with clipping bugs. Anyway, Keen Dreams has slopes and shooting/pushing ennemies. The map design with its "info layer" suggests that most of the engine has been kept between Keen Dreams and Goodbye Galaxy. The character's moves (jump, run and pole-climbing) are direct translation of GG spritesheet. The pogo is missing, and I will have to define how the lone "canteloupe cart" can be ridden. 

Rather than stunning gun, Keen throws "flower power" seeds that are affected by gravity somehow like my dumbladors. Gameplay-wise, I cursed that decision quite often. Aiming for those fast-moving, aggressive vegetables with something that follows an arced curve, bounce on the ground and only stuns for a limited amount of time made imho this episode almost the hardest of the series. So far, I haven't found arced curve of bladors that hard to use, but on the other hand, monsters in Bilou's Schoolzone don't kill you instantly on contact.

N² with high N could turn Nightmare.
En plus de leur calques "graphiques", les niveaux possède une couche "info" qui indique quels monstres créer au chargement du niveau (scaninfoplane et HandleInfo). Les monstres de l'ensemble du niveau sont conservés dans une liste liée, mais seuls sont "actifs" ceux qui sont assez proche dans l'écran. Leurs collisions sont gérées par un parcours imbriqué de la liste (N²) -- rien d'équivalent à mon système de "castes", donc --  mais vu le nombre réduit de monstres par écran dans le level design, celà ne pose pas de réelle difficulté, sauf peut-être dans le niveau des vignes.

Compared to my own engine, code for managing collisions looks quite simple. There is no Hero/Ennemy casts, nor collision masks. The engine checks every pair of "objects" for intersection of axis-aligned bounding-boxes. That could easily turn into programmatic nightmare in a game with heavy number of monsters like Apple Assault (up to 10,000 checks per frame), but here, the test is skipped as soon as one of the monsters is off-screen (active is false), and there quite little places where the screen shows more than a handful of ennemies at once. 

Funny enough, although everything may have its own contact() function and both are invoked when two objects come in contact, there is no passive/active role... yet, monsters typically don't use their contact() function at all, and whether Keen should die or be granted more points is all encoded in Keen's own contact() function, and contact() function for the flower-power seeds has knowledge of which monster can be stunned and which object shouldn't be affected.

Casts make it linear and scalable
On a une fonction "contact()" pour chaque monstre qui régit les changements en cas de collision. Pas non plus de notion de "actif/passif" mais une organisation où "PowerContact" (pour l'arme de Keen) transforme tous les objets en fleurs et KeenContact() mêne à la mort de Keen presque systématiquement. Ces fonctions contact ont la possibilité de faire n'importe quels tests (on est dans du code C), y compris aller tester l'étape d'animation de l'objet avec lequel on est entré en contact ... ce qui permet de concentrer toute la logique de collision dans quelques objets. Pour les monstres, il n'y aura en fait aucun code pour les contacts.

Ça vaut aussi la peine de regarder de plus près le système des "ticks" qui règle le comportement des personnages. Ce type de code est le plus souvent absent sur console. La vitesse du CPU est connue et la mise à jour de l'image à l'écran assez rapide vu la structure choisie pour le processeur graphique. Mais on est ici sur (vieux) PC, avec une vitesse quelque part entre 6 et 40MHz pour le processeur principal et un système de rafraîchissement de l'écran passablement complexe. Le jeu ne tournera certainement pas à 60 images par secondes, ni même à 30 ou à 12. On aura plus que probablement un temps de rendu (entre l'instant où la logique du jeu a fini sa mise à jour et le moment où la nouvelle image est effectivement visible à l'écran) variable.

The game logic is built around the notion of time ticks, which are a virtual equivalent to video frames on a game console like the Nintendo DS. However, unlike a console, the PC (ranging from 6 to 40MHz by that time) cannot guarantee we'll have a new frame rendered every 1/60th of second -- maybe not even every 1/12th of second. It's much more likely that the framerate will be irregular, depending on bus availability for memory transfers and complexity of the current scene. ID software developers thus measure how much time elapsed since the last rendered image and deduce how much game logic _ticks_ corresponds to this time. The StateMachine() function then compensates by stepping the characters by (xspeed,yspeed) the appropriate number of time, invoking the think() function when needed. Rather than experiencing slow downs, we'd experience a drop in the frame rate, but no kid on earth would complain about that from a shareware

The code logic deciding whether think() should be called or not is quite complex, allowing some part of monster behaviour code to indicate "do not think for N ticks, and slide me at constant speed" or "only invoke think() when time is ready for the next animation frame", etc. The benefit is that most of the code that accommodates for "process N ticks at once" is in that generic logic, and the monster-specific code remains as simple as updating speeds, not moving coordinates. Another function will then react() to the new position of the character on the level (does it still has ground under its feet ?)

L'idée (toujours présente dans les Quake modernes, pour ce que j'en sais) consiste à mesurer le temps qui s'est écoulé depuis la dernière demande d'affichage et à exécuter k "pas" (les ticks) de la logique de jeu, où k * durée_d'un_pas = temps_écoulé. Ainsi, la fluidité varie mais le timing du jeu reste constant et on ne perçoit pas de réel "ralentissement". Ce qui témoigne de la qualité du design, c'est le fait que le code du comportement des personnages peut être écrit sans devoir se soucier de ce mécanisme: les fonctions DoActor et StateMachine prennent intégralement ce comportement en compte et sont capables de gérer une transition d'état au milieu du laps de temps à simuler sans pour autant faire N appels aux fonctions think() des personnages. Autre élément qui se retrouve aussi dans les FPS d'ID software: la fonction "think" n'est pas forcément appelée à chaque moment. Selon les besoin, elle peut être invoquée sur les étapes d'animations, à intervalle régulier ou aléatoire.

Dernier traît intéressant dans les grandes lignes de l'organisation du code: la fonction think() d'un personnage ne se préoccupe généralement pas des collisions avec les murs. Elle se contente de lire l'état du jeu et de décider de la direction/vitesse/animation à suivre. Une deuxième fonction, react(), associée elle aussi aux états du personnage, sera appelée après que le déplacement ait eu lieu et s'occupe d'aligner un personnage qui aurait rencontré un mur. J'y reviendrai dans le volet prochain.

1 comment:

Cyborgjeff said...

C'est plus parlant que directement Githlub ;)