Des pentes et des testpoints ...

Je relisais ce document sur la réalisation du jeu M.C. Kids, et j'ai enfin compris pourquoi ils avaient eu tant de mal à prendre en compte les pentes dans la "gestion des collisions". (J'ai un peu du mal à parler de détection de collision entre sprite et décor, vu que j'ai utilisé ce terme pour les collisions sprite-sprite pendant des années ;)

Bref. L'idée globale des testpoints, c'est s'assurer que le testpoint situé sous le personnage soit toujours à la frontière entre le "ciel" et le "sol". Ultra-simple sur des horizontales, un peu plus subtil sur une pente (mais grosso-modo il suffit d'ajuster le déplacement vertical en fonction du déplacement horizontal). Le hic, c'est de passer d'une surface horizontale à une pente. LE hic, c'est que la pente commence devant notre personnage alors que le point-test que l'on doit garder sur cette pente est sous le personnage (ici, yelloworm). En clair, notre worm va soit s'arrêter avant la pente (s'il la considère comme un mur), soit rentrer dans le premier tile puis s'arrêter au premier bloc de "mur" complet.

Dans M.C. Kids (et selon les dires de l'auteur, dans SMB3 également), ils résolvent le problème en introduisant un nouveau type de tiles: le "bas de colline", qui est placé dans le sol, dans le prolongement de la pente à amorcer. Ca marche, bien sûr, mais personnellement, je trouve ça un peu "bricolage". Un autre point qu'ils mettent en avant, c'est l'importance de garder un nombre de "test de map" fixe et le plus réduit possible -- de préférence un tile par testpoint.

Mais nous avons de toutes façon un testpoint devant notre personnage: celui qui sert à déterminer si oui ou non on arrive dans un mur. Et il est important de s'assurer qu'il soit suffisamment bas pour qu'il stoppe Bilou (et le yelloworm) même si le mur est très bas.

Du coup, on peut en profiter pour détecter le début d'une pente quand on arrive un tile avant. Il nous reste alors à ajuster la vitesse verticale de manière à ce que, un tile plus loin, on soit monté d'un pixel. On sera alors effectivement "sur" la pente. Bingo.

Il faudra évidemment s'arranger pour que l'angle entre les deux testpoints soit suffisant par rapport à l'angle de la pente la plus forte dans le jeu, mais ça, ça ne devrait pas nous poser de problème particulier.

Voilà. C'était ma cogitation du dimanche un peu en retard ... j'espère que c'était suivable ^_^

The Lost Tiled Tutorials

Many of the tutorials I had encountered between SEDS and LEDS are now out of the web. Too bad, they were key material I sent readers towards when I did not feel like translating some lengthy explanation about tiled games in general. Since I'm editing some part of the blog as if it was going to be the Chapter 1: Tiled Games of a book, I found myself digging through archive.org to find the original material, print it and review it as much as possible. 

The most influential of them all was certainly the MC Kids big post. Where we have Greggman discussing *really* how they made the game back on NES days. It details several clever tricks that help making a quite-sized game on limited resources, some of which make mostly sense if you're on #6502 CPU (like having a set of byte tables rather than structures), but also the key gamedev concept of a "hotspot", a single point that will be used to model the position of the character on slopes.

It is also the most official one, as the post was originally written in 1992 for the Journal of Computer Game Design while the game was from 1992 as well. And since there was an official body publishing it, I can't quite just bring in many pictures of it ... but I guess it's fair to study it, take notes and then post my own notes about what was being said.  

Salut. Je vous traduis tout ça plus tard, hein ;)

The paper goes into significant details of how the levels are encoded (1 byte per 16x16 block, that is used to lookup the 4 tiles composing the block and its type among 100 possible types), how collision with terrain are handled (with direction-conditional testpoints and 5 collision functions per tile type). The author relates the fight to get that extra memory and how you could map the whole level into memory and thus make it easily explorable and transformable thanks to this, but how 8x8 granularity would have explosed the RAM space budget.

It is also completed with retrospective thought of the author about how they'd have inserted "beginning of hill" and "end of hill" types (helpful to save lookups in the slope management) and how they'd have made the "how do I move left[tiletype, xpos]" array providing absolute position rather than relative (+1, 0, -1) positions in a revised version of the engine.

Retrospectively, most of it did not end up in the GEDS engine. With a 66MHz CPU, if you realize that you need one extra memory lookup to get proper slope implementation, you go for that extra lookup. And if you may need more than one, you just write a loop. It's not about being lazy or not, it's about getting the most of what you have. And nowadays, you could "easily" add some "start-of-slope", "end-of-slope" meta tiles by means of auto-tiling rules.

The second note-worthy series are Tony PA tutorials about tiled games development. These were for flash games, with full-running examples at each step and detailed ActionScript code. Smartly enough, Tony starts his tutorials with top-down playfield in which the character can move freely, and then step by step introduces gravity, moving platforms, ladders and finally slopes. 

I was enjoyed to start reading it as it featured a picture of Charlie the Duck (which may explain why I was researching about it in 2007 and certainly why I just posted about it, btw :P) and saying "Sure if our hero is a jumper-type of hreo, he could still [proceed forward in a stair-like, slopeless ground], but normal heroes are very happy if they can avoid jumping. It could have been a good resource, but I knew from the time I've spotted a drawing with "impossible slopes" that I couldn't derive from what was presented there.

During this 2026 retro-review, I noted that most of the slope logic seems to imply that only the display of the character is aligned with the slope. The logic entity made of testpoints and hitboxes simply moves along a stair. The two locations are only re-aligned if we jump from a slope. It also bypass the problem of solid-ground-tiles-and-slopes by disabling all horizontal checks while you're on a slope. That explains some of the "forbidden tile combinations", and implies that if you make a slope in a path that is high enough for certain characters in your game but not all, the engine will completely ignore the fact that the monster you're fleeing through that narrow passage should get hit in the face and not be able to follow you. And that has been a critical thing to address for my games even before I started working with the Nintendo DS.

So why would you put slopes in a Mario game ? so that your koopa shell keeps flowing forward and not bounce back in your face. Here's why. (Or simply to make your organic level feel organic and not just look organic). 

A last one ? Hopefully, the video from Vblank Entertainment about the conversion of Retro City Rampage into ROM City Rampage is still online. It goes into details about what tiles are and how it allows a large world to run on a sub-MegaByte cartridge, what palettes are, why you need to care about not putting too many sprites per line and so on. If you ever need a primer to the "Retro Game Mechanics Explained" series and feel like sitting idle for 10 minutes, this is the best I can think of at the moment.

(The author ended up writing his own NES emulator full with debugging features and his own high-level assembly -- NESHLA hosted on sourceforge -- in the process)

Higher Order Blog ...

Of course, it's been a long time since I first read the guide to implementing 2D platformers on the Higher Order Fun blog. I believe it's been part of my research on how people implement slopes together with the MC Kids talk on implementing sophisticated platformers on NES. So somewhere around 2007.

Un tout bon blog, qui continue à nous proposer des conseils pour implémenter un jeu de plate-forme 2D depuis facilement 2007, époque où j'ai dû le rencontrer pour la première fois. Mais en repassant dessus il y a quelques mois (magie Twitter), je me rends compte qu'il y a encore un bon nombre de fonctionnalités discutées que je n'ai pas encore implémentées dans mon moteur à moi (échelles, plate-formes dont on peut redescendre), et d'autres qui sont en cours de révision (pentes, plate-formes uni-directionnelles). Je repasserai dessus dans les jours à venir (j'espère)

There's still a number of topics I haven't implemented in GEDS that are discussed in that post, including ladders, refined slopes and one-way platforms. So I finally printed it all so I could take the time to read it quietly and take notes on what was neat and what needs more thinking. That was over 6 months ago.

So unfortunately, the toughts aren't fresh in my mind anymore. I'll have to read them back *too* before I can talk about it more.

The blog post presented different ways to implement a platformer. Tiles-based, of course, as it was de-facto technique used on virtually all 8-bit and 16-bit consoles that used tiles-based hardware (and still an efficient technique on page-flipping hardware), but also vector-based levels (only mentioned, though) and bitmap-based. I wish there was more being said about the techniques used with bitmap-based level modeling, as I believe it was the technique used in Fury of the Furries. 

Mais une particularité de l'article de Rodrigo Monteiro, c'est qu'il ne se limite pas aux jeux basés sur des tiles: il discute aussi le cas des niveaux modélisés par des vecteurs (Braid), à positionnement forcé sur des tiles (Prince of Persia, Flashback) et basés directement sur un bitmap (Worms). Et là, je trouve qu'il a peut-être été un peu léger en oubliant de mentionner Lemmings. Bon, d'accord, l'article est bien plus ancien que le talk de Mike Dailly présentant le fonctionnement (et l'éditeur de niveau :P) de Lemmings 1 et 2. Bon, on est d'accord: ni Lemmings ni Worms ne sont à proprement parler des jeux de plate-formes, mais ils restent en vue latérale avec de la gravité, et à voir la physique du personnage dans Fury of the Furries, je dirais qu'on pourrait bien en avoir un troisième.

I also know for sure it was used in Lemmings for levels up to 5 screens-wide (that would be about half the conventional RAM available on an IBM-PC, btw). 

Since the storage space on floppies was limited, levels weren't stored as a large bitmap, though: they were stored as a set of 'paint brush A at location (X, Y)' plus a set of (deluxe paint) brushes -- think of them as 256-color stamps The level editor calls them 'rocks' and reports how much are used so far. Some brushes may even be used as 'clearers' instead of 'drawers', exactly like what is seen in the New Super Mario Bros. level editor.

A true puzzle for those who later had to port DMA Design's success title to tile-based consoles of the time, if you ask me. But it allowed complete freedom that was precious to design appealing and challenging levels. Lemmings 2 was later developed based on an editor that aligns everything on a grid to ease porting to Nintendo and Sega (?) consoles, and while it had charming new themes, I never felt them attractive the way the original Lemmings were to me.

A noter que traiter la map comme un gros bitmap n'implique pas forcément de stocker la map comme un gros bitmap. En fait, pour la majorité des machines d'avant le CD-ROM, ç'aurait été tout simplement impensable même avec des niveaux de taille modeste comme ceux de Lemmings (5 écrans). Pour faire tenir tout ça sur une diskette, les gens de DMA design ont construit leur niveaux sur base 1) d'une palette de 'brosses' (des bitmaps de taille quelconque provenant de Deluxe Paint) et une série de commande 'ajoute la brosse A aux coordonnées (X, Y)'. L'éditeur permettant d'ailleur de garder une idée du nombre de 'coups de pinceau' utilisés jusqu'ici dans le niveau.

Bon, vous l'aurez compris, cette technique bitmap pour les données d'un niveau marche surtout bien pour les jeux où l'environnement est complètement destructible (chose qui devenait moins vrai avec Lemmings 2, prévu pour consoles 16-bit) et à un style graphique plus proche d'un Rayman que d'un Mario. D'une façon assez amusante (mais foireuse), c'est aussi ce qui était utilisé pour la version BASIC de Bilou's Adventures ;-)

Vous courriez ? J'en suis fort aise! Eh bien, Sautez, maintenant...

Je discutais DS et bilous avec Dider, mon beau-frère informaticien, et je me rends compte que des techniques que j'ai apprises "sur le tas" avec mon Bilou's Adventure en QuickBasic peuvent parfois être pas si évidentes que ça pour des personnes qui ne baignent pas dedans depuis 15 ans ^_^

Outre les aspects techniques qui font que les images du jeu s'affichent convenablement, une question-clé était "mais comment programmes-tu les murs, les sauts, etc." Rappelons-nous tout d'abord que sur une console de jeu, l'écran (en tout cas pour les modes 2D) ressemble plus au carrelage d'une salle de bain qu'à n'importe quoi d'autre. Vous avez de jolis pavés (parfois appelés "tiles" ou "blocs" selon les cas) sur lesquels vous avez amoureusement dessiné des bouts de livre, d'encrier, de crayon, etc. Chacun porte un numéro et il suffit d'inscrire son numéro dans une grande grille pour construire l'image voulue.



Bion. Maintenant qu'on sait ça, on voudrait pouvoir détecter s'il y a ou non un sol en-dessous de Bilou, histoire de s'avoir s'il doit tomber ou rester sur place. Rien de plus simple: on va calculer les coordonnées d'un "point-test" situé juste en-dessous de Bilou et regarder le numéro du pavé au-dessus duquel il se trouve. S'il s'agit d'un crayon, d'une latte, etc. on ne bouge plus! Sur PC, j'avais traduit ça en une division des couleurs du jeu en deux sous-ensembles: les couleurs "solides" (pour dessiner les livres, etc) et les couleurs "de fond" (pour dessiner le fond. warf.), mais sur une console comme la DS, on a généralement plusieurs plans de décor, et pour commencer, on peut tout à fait décider que tout ce qui n'est pas "solide" set sur un autre plan: lors du calcul du "point-test", on verra soit le pavé #0 (du vide), soit un autre pavé, qui indique qu'on a affaire à du sol.





Bien sûr, ce que je fais avec Bilou et ses points-test peut être généralisé à tout le reste du jeu: les éponges, les crayons, les gommes, les gouttes d'encre et tout le tintouin. Il suffira de programmer les routines de déplacement de chaque élément du jeu pour qu'il fasse ses propres tests et réagisse en conséquence (passage de l'état 'sur le sol' à l'état "dans le vide", par exemple). Avec ça, vous ne devriez pas avoir trop de mal à vous construire un petit perso qui tombe quand il n'y a pas de sol et qui avance quand il est au sol.
Maintenant, quid des sauts et compagnie ? Bon, si vous avez déjà suivi un petit cours de physique, vous savez qu'un objet qui bouge a un vecteur-vitesse. En clair, si Bilou avance vers la droite, son vecteur-vitesse vaut p.ex. (5,0), c'est à dire qu'à chaque "tranche de jeu" (ou 'tic'), il sera 5 pixels plus loin sur la droite mais qu'il ne monte pas et qu'il ne descend pas. A l'inverse avec un vecteur-vitesse (0,5) Bilou descend comme s'il était sur un ascenseur. Pour donner l'impression qu'il tombe, il suffit d'augmenter la vitesse verticale à chaque tic. Mieux, même, si je démarre avec (0,-5) et que je garde la politique "augmente la vitesse verticale à chaque tic tant qu'il n'y a pas du sol en-dessous de Bilou", il va faire un gentil saut sur place.

Avec un petit calcul niveau secondaire-sup, vous pouvez même calculer la vitesse initiale à donner à Bilou lorsque le joueur appuie sur le bouton de saut pour qu'il puisse (par exemple) faire un saut suffisant pour grimper par-dessus un obstacle de 64 pixels de haut. Facile: il faudra au moins une vitesse initiale de 11. Et c'est là que le bas blesse: on vient de dire que 8 était un maximum :-/ Résultat,

• on pourrait diminuer la gravité (se dire que tomber d'un pixel tous les 1/60 secondes, c'est un peu beaucoup: vous avez traversé 1/3 de la hauteur de l'écran en seulement une seconde)
• on pourrait ajuster nos routines de tests pour qu'une vitesse de plus de 8 pixels sur 1/60 secondes ne pose pas de problème technique
• on pourrait revoir le modèle du saut et "tricher" un peu avec les lois de la physique...

En pratique, si vous regardez sauter Mario, vous vous rendrez compte qu'on a pas vraiment respecté les bonnes vieilles lois de Newton dans les sauts, et pour cause: le joueur doit pouvoir doser son saut, et la manière la plus naturelle de le faire, c'est de relâcher plus ou moins tard le bouton de saut. Dans la réalité, bien sur, ça ne correspond à rien: une fois que vous êtes lancés, vous ne pouvez plus décider que "oups, non, finalement, il faudrait que je saute un peu moins loin si je ne veux pas me tordre la cheville en retombant".

On pourrait faire comme dans ninji & zarbi et demander au joueur de laisser le bouton enfoncé d'autant plus longtemps qu'il veut sauter loin (mimant alors une "accumulation d'énergie" avant le saut) et ne faire le saut que lorsque le joueur relâche le bouton, mais je vous laisse imaginer sauter de passerelle en passerelle sur ce principe.
Non, ce que l'on va faire, c'est considérer que l'énergie dont notre Bilou dispose pour le saut n'est pas consommée complètement en un instant pour lui donner la vitesse (0,-11), mais plutôt que pendant une première phase du saut, Bilou conserve une vitesse verticale plus basse, mais n'est plus soumis à la pesanteur (en gros, il monte à vitesse constante) aussi longtemps que le joueur garde le doigt sur le bouton de saut. Avec un bon dosage de la durée max de cette "phase ascenseur", on pourra atteindre la hauteur souhaitée sans dépasser la vitesse qu'on s'est fixée.

Reste le coup du saut pendant la course. Le premier jeu bilou était assez déroutant dans ce sens. J'avais voulu obtenir un effet "à la Sonic" ou le personnage saute d'autant plus haut et loin qu'il avait pu prendre de la vitesse. L'ennui, c'est que je passais simplement de (v,0) à (v,-v) au moment du saut. Si vous faites le calcul, ça veut dire que au moment où le jouer appuie sur le bouton, c'est comme si l'énergie de Bilou était subitement doublée ... d'où un saut qui n'a rien à voir avec la vitesse de Bilou à ce moment-là. Idéalement, j'aurais plutôt du prendre quelque-chose comme (sqrt(v),sqrt(v)) pour conserver sa quantité d'énergie ...

On testera tout ça...

Sorry non-frenchy folks, this one is a big too large for inline translation. i might come with a dedicated post with translation when i'll have a bit more free time... and implemented the stuff ^_^ Meanwhile, i suggest that you read Gregg Iz-Tavares and Dan Chang's article on M.C. Kids for the NES, which basically covers the same kind of topic.