SANS HITBOX PAS DE PLAISIR

06/11/2019 11:54

EDIT: Ce billet a un peu vieilli mais je l'ai complété en bas de page avec plein de liens plus récent vers mes nombreux threads twitter très détaillés sur les hitbox de jeux NES et illustrés de moultes gifs.

Je me suis amusé à convertir une quinzaine de script pour les rendre compatible avec l'émulateur Mesen et dont le thème commun est d’afficher les hitbox dans des jeux NES. C'est un type de script vraiment intéressant et ça méritait d'être archivé sur cette émulateur à l'avenir prometteur. Et donc par la même occasion partager avec vous ce qu’on peut observer grâce à ces scripts et voir s' il y a des choses a dire. On va donc parler de Hitbox!

Les bases

La hitbox c’est la solution classique pour tester les collisions entre objets. On définit des boîtes englobantes autour des objets à tester et si 2 box sont partiellement superposées c’est qu’il y a collision. Faire ce genre de test sur des box c’est relativement trivial tout en étant assez efficace donc ça s’est naturellement imposé.

Sur les plus anciennes consoles comme l’Atari 2600, l’Intellivision ou la Videopac y avait une autre solution alternative, une solution hardware aux problème des collisions par l’intermédiaire de flag géré par le chip graphique. Des flag (des bits hardware dans un registre) qui s’activaient si des pixels de l'écran était commun à 2 sprites ou commun a un sprite et au background. Une fonction hardware possible grâce au nombre limité de sprites à cette époque. C'était pas toujours exploitable, fallait réunir certaines condition, mais cela pouvait dépanner (et ça faisait des collisions au pixel puisque c'était sensible uniquement aux pixels opaques des sprites). Il reste un reliquat de cette époque sur NES avec le flag du sprite zéro mais qui a pris un tout autre rôle (il sert de signal de synchronisation entre le code et l'affichage). Mais en dehors de ces quelques exceptions et tentatives à résoudre les collisions de façon hardware on peut dire que les hitbox, qui sont une approche software, sont vite devenu la solution la plus viable et flexible pour répondre a peu prêt a tous les besoins.

On peut distinguer 2 grandes familles de collision. D'abord les collisions objet > environnement (ici on peut remplacer le terme objet par sprite si l'on souhaite). Par exemple pour empêcher le joueur ou les ennemis (les objets) de traverser le sol et les murs (l'environnement) ou alors pour prendre en considération les éléments de l’environnement qui sont destructibles par les bullets ou qui sont létal pour le joueur. Ce type de collision ne sont pas très coûteuse car l’environnement (la tilemap, le plan de construction du décors) est déjà comme un empilement de box (les tiles ou metatiles) toutes de même taille et parfaitement ordonnées les unes aux côtés des autres. Ça simplifie les choses et donc ce genre de collision est peu coûteuse. Cela a par exemple été beaucoup exploité dans les shmups verticaux des années 80 pour avoir quelque chose de très dynamique et spectaculaire avec beaucoup d’interaction comme ici dans Blade Buster un homebrew NES de type Caravan Shooter disponible gratuitement

Beaucoup de collision entre bullet et environnement

Mais ce qui va nous intéresser dans ce billet (ce que permet de visualiser les scripts que j'ai convertie pour Mesen) ce sont plutôt les collisions objet > objet (ou sprite > sprite). Ce sont ce type de collisions qui font le plus usage de hitbox (parfois les collisions avec l’environnement nécessite aussi des hitbox pour avoir une granularité plus fine et précise). Ces 2 familles de collisions ne font pas appel aux mêmes algorithmes et aux mêmes données. Elles sont traitées indépendamment.

Le coût des collisions objet > objet gonfle bien plus vite que le nombre d'objet et c’est donc la partie sensible du moteur de collision. Si chaque objet peut être en collision avec tous les autres ça implique qu’avec 5 objets à l'écran il faut faire 5x5= 25 tests de hitbox. Si y a 20 objets ça veut dire 20x20= 400 tests! On voit que ce n’est pas un simple problème linéaire, ça augmente selon le carré du nombre d’objet d'où le challenge.

La première simplification c’est de définir 2 sous-ensembles dans cette famille de collision. D’un côté les objets “player”, c'est-à-dire le sprite du joueur (ou des joueurs) et ses bullets par exemple. Pas besoin de tester les collisions entre les bullets du joueur et le joueur lui-même ni entre les bullets elle-même donc on ne fait pas de test de collision entre les objets de ce sous-ensemble. Et l’autre sous-ensemble va plutôt concerner les ennemis et leurs bullets. Ainsi l’objectif va être de tester les collisions entre ces 2 sous-ensembles et dans les 2 sens. On va tester les collisions player > ennemi (pour savoir si les bullets du joueur ont touché un ennemi) et les collisions ennemi > player (pour savoir si l'ennemi a touché le joueur. Que ce soit par contact direct ou par l’intermédiaire d’une bullet). Ça c’est la théorie! Maintenant allons voir ce qu’on peut observer concrètement dans les jeux avec ces fameux scripts ça sera plus rigolo.

Place aux exemples

Visualiser les hitbox ça permet notamment de voir qu’elles sont souvent permissives. On voit ici en rouge les hitbox ennemi et en bleu la hitbox player. Par exemple, cette flèche dans Holy Diver semble particulièrement dangereuse mais au final plus de peur que de mal, les 2 hitbox ne se touchent pas.

Dans Contra Force on peut constater que les presses (qui ici sont des objets constitués d'éléments du décors, sur NES on essaye de faire des économies de sprite autant que possible) ont de minuscules hitbox placé à l'avant. On comprend mieux alors pourquoi il y a un safe spot qui semble défier ce que l’image nous montre.

L’action de porter une attaque prend souvent un certain nombre de frames d'animation mais la plupart du temps une seule des frames qui compose cette animation a une hitbox active. Donc la aussi on peut parfois être un peu tromper par ce que l'image nous montre. Donner un coup de fouet dans Castlevania prend une vingtaine de frames mais seule la 17 ème est active et ne se trouve même pas parmi les premières frames d'animation du fouet en position tendue.

Vice Project Doom

Vice project doom fait partie de ces jeux NES de grande qualité mais peu connus (d'autant qu'il n'existe pas en PAL). Et contrairement aux apparences c’est la véritable alternative à Ninja Gaiden. Bien plus qu’un Shadow of the Ninja (Blue shadow) par exemple car on retrouve ici la même dynamique, le slash très bref et précis à faible porté, le saut sans nuancier vertical, le knockback, les ennemis très nombreux et agressif qui vous poussent dans les trous mais qu'on one-shot tous, le respawn violent, le découpage des stages, le format de cutscene... C’est du ninja gaiden 100% avec en plus des variations de gameplay (par l'intermédiaire de phase à la Spy Hunter et Opération Wolf) et un pixel art plutôt inspiré de Batman et sa descendance (Shatterhand, Kabuki...). Mais y a aussi un autre truc sympa dans ce jeu c’est un certain effort pour tenter d’avoir des hitbox qui collent au mieux à ce que le joueur voit à l'écran.

Par exemple, la hitbox du slash est très intéressante. C’est en fait 4 hitbox successives qui dure donc 4 frames et qui accompagnent littéralement tout le mouvement d'animation du slash. On peut donc frapper derrière, au- dessus, devant, a nos pieds mais successivement. Ainsi le timing est différent selon que l’on veut frapper un ennemi derrière ou à nos pied ce qui demande une phase d’apprentissage d’autant plus que le slash a un cooldown, on ne peut pas bourriner (max 6 coups par secondes). C’est l'élément le plus intéressant du jeu (j'aime bien aussi le fait de pouvoir courir accroupi).

La grenade aussi a le droit a une hitbox dynamique en 2 étapes pour simuler le souffle de l'explosion (ainsi qu'une minuscule hitbox pour la phase de lancement) et tenter encore une fois de coller au visuel.

On retrouve la même démarche sur les phases de shmup vertical. Le jeu nous donne la possibilité de modifier notre vitesse de déplacement avec un bouton et ce changement de vitesse est représenté par une petite flamme d’échappement a l’arrière du véhicule comme dans d’autres shmup sauf qu’ici cette petite flamme est matérialisé aussi par une hitbox qui peut donc détruire un ennemi derrière soit, classe!

Meme les flammes d’échappement ont leur hitbox

Ninja Gaiden

On va maintenant parler des 3 Ninja Gaiden. On a la chance d’avoir un script pour chacun d’entre eux et il y a pas mal de choses à dire. Faisons dans l’ordre et commençons par le premier Ninja Gaiden. Je vous ai dit que les collisions box > box c’est un grand succès car c’est trivial et simple a faire même pour des vieilles machines mais on peut encore simplifier pour gagner quelques cycles notamment en faisant des collisions line > box ou point > box et c’est toujours bon a prendre sur une NES.

(J'ai retiré le passage sur Ninja Gaiden 1 qui était obsolète étant donné que j'ai recodé mon propre script plus correct avec plein de nouvelle chose a dire dans un prochain thread tout comme j'ai retiré aussi le passage sur Megaman 4 obsolète aussi.)

Passons maintenant à l'épisode 2 de Ninja Gaiden. Un truc intéressant sur ce script ainsi que celui de Ninja Gaiden 3 c’est que l’information sur les hitbox n’est pas simplement récupérée en RAM ou en ROM mais directement au moment de l'exécution du test de collision par le CPU qui génère alors une interruption du script. Ça veut dire que le script ici n’affiche les hitbox que lorsqu’il y a concrètement un test. La conséquence c’est par exemple que les hitbox ne s’affiche pas si il n’y a pas d’ennemi car il n’y a pas de test de collision a ce moment la mais surtout ça permet ici de constater que les collisions ne se font qu’une frame sur 2 donc a 30hz. Ce qui permet au moteur de collision d’entrelacer les collisions player > ennemi (box blanche et verte) avec les collisions ennemi > player (box rouge et bleu), chacun son tour, chacun sa frame. Voila un autre moyen assez courant pour faire des économies de ressource CPU sur les tests de collision. Des collisions a 30hz ça reste suffisant en général je pense.

Répartition des tests entre les frames paires et impaires

On remarque aussi que Ryu a récupéré une véritable hitbox sur cette épisode ainsi que les ennemis. Mais ça n’a pas empêché une autre petite optimisation. Cette fois c’est la hitbox du slash qui est réduit à une simple ligne. En terme d'économie ça ne va pas être très perceptible mais en même temps les conséquences négatives sont quasi nulles. Réduire le slash a une ligne reste assez cohérent avec sa représentation à l'écran. L’attaque devient alors encore plus chirurgicale que jamais surtout lors des déplacements verticaux (saut ou chute) il faut vraiment appuyer a la bonne frame pour toucher sa cible. Les ennemis ont de la place pour passer en dessous ou au-dessus. Peut être le Ninja Gaiden le plus chirurgical.

Un slash chirurgical aussi fin qu'une ligne

En ce qui concerne Ninja Gaiden 3 cette fois il n'y a plus de ligne, on a uniquement de vrai hitbox. Par contre on retrouve un moteur de collision qui tourne à 30 hz donc une frame sur 2 mais en plus de cela l’algo découpe les ennemis en 2 pools de 4 (donc maximum 8 ennemis à l'écran, ça inclut leurs projectiles) et ne traite qu’un pool a chaque fois ce qui veut dire que les tests de collisions avec un ennemi en particulier ne se font réellement qu’une fois toute les 4 frames soit a 15 hz (on peut observer cette alternance des box rouges sur le gif).

Ça commence à faire vraiment peu comme fréquence de test. Ça veut dire un input lag du slash qui va varier selon le cycle du moteur de collision en cours de test au moment ou l'on frappe. Le plus problématique dans un moteur de collision à fréquence trop basse c’est pour les projectiles rapide tel que nos pouvoirs magiques (les box blanches sur le gif) au point que les devs en étaient bien conscient et ont donc monté a 20 hz la fréquence de test de nos projectiles magiques (donc une fois toutes les 3 frames) et même à 20 hz malheureusement ça reste trop faible. J'ai speedrunné le jeu (en mode "no damage") et j’ai donc souvent ragé en me prenant un dégât à cause d’une magie qui passe au travers d’un ennemi sans le toucher parce qu'entre 2 tests temporellement trop distant le projectile était passé de l’autre côté de l’ennemi sans qu’il y ai de superposition des hitbox. C’est le risque d’un moteur à trop basse fréquence. En contrepartie le jeu maintient un excellent framerate à 60fps en toute circonstance malgré l'intensité de l'action et ça c'est quand même chouette.

Ce gif nous permet de visualiser à quelle fréquence sont exécuté les différentes collisions et la répartition entre les 2 pools d’ennemis. Le cycle complet pour faire tous les tests est donc dilué sur 4 frames.

Le jeu compense ces petites faiblesses par de grosses hitbox pour nos attaques. On a même 2 types de slash dans cet épisode. Le slash de base dont la hitbox laisse passer certains ennemis par dessous et le super slash proche du slash de strider et qui offre une très grosse hitbox qui protège de nos pieds jusqu'au-dessus de notre tête. Vous pouvez comparer sur ce gif les 2 slash.

Ninja Gaiden 3 c’est aussi l’occasion de parler des bugs que permet de mettre en exergue un script de ce type. Visualiser les hitbox ça permet par exemple de découvrir quand il y a une erreur de format de hitbox. Regardez avec attention les pierres qui tombent du plafond sur cette scène du 6 ème boss dont la stratégie consiste à foncer dans le mur pour créer des éboulements. Y a 7 pierres qui tombent à chaque fois sauf qu’il y a systématiquement l’une d’entre elles qui a une hitbox buggé complètement disproportionné (57x33 au lieu de 9x9, plus grosse même que celle du boss) et qui nous empêche d’esquiver. Seule solution sur ce combat pour ne pas laisser son destin dans les mains du hasard, il faut détruire les pierres au-dessus de vous à l'aide de la magie verticale (vacuum wave art).

J'ai identifié un autre bug lors de mes speedrun. Lors du combat final le boss déclenche des éclairs précisément à l'endroit où vous vous trouvez à cet instant et donc pour les éviter il faut absolument être en pleine course ainsi le temps que l'éclair touche le sol vous vous êtes déjà déplacé. Mais à cause des collisions qui s'exécutent seulement une frame sur 4 on a un test de collision de l’éclaire avec le joueur qui ne se fait pas toujours au même timing dans cette séquence et va varier selon le cycle de test en cours. Le test de collision de l’éclaire avec le joueur se fera donc plus ou moins prématurément avec une variation sur 4 frames.

A cela s’ajoute le fait que la course de Ryu n’est pas linéaire. Pour avoir cette vitesse de déplacement commune a beaucoup de jeu de 90 pixels par seconde ça implique d’alterner entre chaque frame des déplacements de 1 pixel avec des déplacement de 2 pixels (ce qui nous donne bien un déplacement de 1.5 pixel par frame en moyenne soit 1.5 x 60 = 90). Le résultat est que si par malchance on se retrouve dans le cas d’un test de collision de l’éclaire qui se ferait prématurément sur la toute première frame possible (1 chance sur 4) combiné à un déplacement de Ryu de seulement 1 pixel la frame précédente (1 chance sur 2) on se retrouve à subir une attaque d’éclaire fatale (1 chance sur 8) qu’on ne peut pas éviter ce qui est donc une erreur de calibration lié à la basse fréquence du moteur de collision qui n’a pas été repéré lors des playtest.

Malgré tout ce que j’ai pu pointer ici sur Ninja Gaiden 3 c’est un jeu qui est vraiment fun a jouer. L'un des tout meilleurs jeux de la NES. J’ai un très bon feeling dessus malgré tout ça car le jeu compense par d’autres atouts. Je le conseille vivement (surtout pour ceux qui n'aiment pas les Ninja Gaiden, il est très différent des mécaniques du 1 et du 2).

Contra

Terminons maintenant avec l’un des mastodontes de la collision: Super Contra (ainsi que Contra qui utilise quasiment le même moteur). Le jeu autorise le joueur à tirer jusqu'à 10 bullets à l'écran (voir même 16 à 2 joueurs) ce qui est un facteur de stress énorme pour le moteur de collision car ça multiplie par autant les tests de collisions. On est loin des 2 bullets de Contra Force le spin-off qui suivra cet épisode (en général sur NES c’est plutôt entre 1 et 3 bullet pour le joueur). Le moteur autorise aussi jusqu'à 13 ennemis à l'écran donc on a potentiellement 10 x 13= 130 tests juste pour les collisions player > ennemi. Et tout ça avec des collisions 60 hz et même un mode 2 joueurs (qui double donc les collisions ennemi > player ainsi qu'une très bonne stabilité du framerate à 60 fps (loin de Contra Force ).

On devine bien que les algos de collision de Contra et Super Contra sont très optimisés. Ça passe entre autres par le choix cette fois de collision de type point > box pour gagner quelques cycles. Cette fois la hitbox du joueur (et de ses bullets) est donc remplacée par un simple point (la croix bleu au centre du sprite sur le gif). C’est donc la hitbox des ennemis qui va devoir compenser la faible dimension de celle du joueur. Ainsi au lieu d’avoir pour le joueur une hitbox différente pour chacun de ses états (debout, couché...) ce sont les ennemis qui vont avoir autant de hitbox que le joueur a d’état ( debout, couché, accroupi, en saut, dans l’eau ainsi qu’une hitbox pour les collisions avec les bullets du joueur).

Des hitbox dynamiques qui s'adaptent a la position du joueur

Donc la contrepartie c’est que chaque ennemi doit avoir 6 hitbox. On a alors un surcoût de data (mais une hitbox ça pèse pas lourd) et des hitbox aux formes étranges (puisque calibré sur-mesure pour venir toucher le hitpoint du joueur de façon cohérente). Mais au final ça permet les mêmes collisions et avec la même précision qu’en box > box tout en prenant moins de ressource CPU. On voit bien ici les changements de hitbox rouge des ennemis (ou de leurs bullets) selon l’état du joueur et la forme étrange que ça peut donner (la hitbox verte des bullets ennemis qui est complètement excentré pour compenser le fait que le hitpoint du joueur soit lui même excentré quand il est allongé)

Un dernier gif qui montre une scène très chargée en test de collision. Le Spread Gun en démonstration face a plein "d’ennemis". Contra et Super C c’est la crème de la crème du genre sur NES. D'ailleurs faudra qu’on parle aussi un jour du saut particulier de Contra, tellement de choses à dire.

MaJ 2020-2022:

J'ajoute maintenant mes propres pierres à l'édifice en codant moi même des viewers de hitbox (et pas juste convertir pour Mesen des scripts existants).
Ma touche personnelle est d'intercepter directement les routines de collision grâce à Mesen ce qui permet de voir réellement les collisions qui sont exécutés à chaque frame (ca permet entre autre de constater si les collisions sont à 60hz ou moins). Et je crée aussi des liens entre les hitbox qui matérialisent concrètement les tests de collision entre les hitbox concernées. J'adore faire ces scripts! ^^

Je vous renvoie donc sur les nombreux threads twitter de chacun des jeux dont j'ai décortiqué les hitbox avec chaque fois beaucoup de Gifs pour illustrer! Il y a de quoi se faire plaisir si le sujet vous intéresse.