Skip to content

Blog

SHA-1 from scratch in assembly

Lors de ma deuxième année d’étude, dans le cadre d’un cours d’assembleur j’ai eu l’opportunité de me lancer un défi : créer un système d’authentification sécurisé simple, permettant à un utilisateur de se connecter à une application fictive. Le coeur principalement intérêssant de ce projet résidait dans le traitement sécurisé de mots de passe, ce qui signifiait implémenter un algorithme de hashage.

Pour cela je me suis orienté vers l’algorithme SHA-1, bien qu’il soit considéré comme cryptographiquement dépassé aujourd’hui, celui-ci reste proche algorithmiquement de son évolution SHA-2 (qui lui est toujours valide à ce jour) tout en limitant sa complexité d’implémentation, et évitant tout de même d’être ridiculement faible à la manière du MD5.

Mon approche pour ce projet s’est déroulée en trois étapes clés :

  1. Compréhension théorique : Pour la compréhension conceptuelle de l’algorithme je me suis servis de cette page de Brilliant, qui explique rigouresement d’un point de vue mathématique comment fonctionne l’algorithme.

  2. Prototypage : Partir d’une page blanche et convertir directement l’algo de la théorie à l’assembleur est une tâche difficile. Pour créer une étape intermédiaire, je me suis basé sur une implémentation Javascript de référence. A partir de celle-ci, j’ai ensuite utilisé ChatGPT comme un outil d’assistance pour traduire la logique en C. L’objectif était d’obtenir rapidement un code “proche de la machine”, qui manipulait directement les octets et les mots, afin d’avoir un modèle clair avant de descendre au niveau des registres.

  3. Conversion en Assembleur : Cette étape a représenté le coeur du projet. J’ai traduit la logique du programme du C vers l’assembleur, me confrontant évidemment à des défis inattendu, bien au delà de la simple traduction.

Voici un texte hashé avec mon implémentation :

Et le même texte hashé sur un site en ligne :

Un point technique intéressant : Hexadécimal vs sa Représentation

Section titled “Un point technique intéressant : Hexadécimal vs sa Représentation”

Créer un programme de ce type en n’ayant aucune couche d’abstraction nous met parfois face à des problématiques innatendu, généralement implicite dans les langages plus haut niveau.

En effet par exemple, l’algorithme nous permet de générer un hash du contenu d’entrée, qui est affiché en tant qu’une représentation hexadécimale des valeurs réellement utilisé dans le calcul (et donc présente mémoire).
Pour clarifier cela, notez que le chiffre hexa 0x11 est stocké en mémoire tel quel (en tant que 11 hexa), mais sa représentation est stocké avec les charactères texte 1, ayant pour valeur ascii 0x31. Donc la représentation de la valeur 0x11 en mémoire est 0x3131 lorsqu’elle doit être affiché en ascii.

Il y a donc une étape de convertion supplémentaire nécessaire à la fin de l’algorithme, cela est habituellement pris en charge par les fonctions de formatage en C :

// h0 - h4 sont des valeurs hexa pure
// les "%x" indique implicitement à sprintf d'effectuer la conversion discutés
sprintf(output, "%08x%08x%08x%08x%08x", h0, h1, h2, h3, h4);

Réimplémenter ce comportement en assembleur a été un exellent exercice de manipulation de chaîne de caractères au plus bas niveau.

Mon implémentation fonctionne correctement pour les entrées jusqu’à 31 caractères. Au-delà, le hash produit diverge de la référence.

C’est après coup que j’ai découvert la limite, et ne m’étant pas replongé dans le code je ne saurais pas dire d’où vient l’erreur. La coïncidence de la limite à 31 caractères est tout de même suspecte : 32 caractères = 256 bits, ce qui suggère un problème de buffer ou un off-by-one à cette frontière.


Vous trouverez le code source sur le répository suivant :

Hack'in 2025 - Reverse - Animal Fabuleux

Achievement : First Blood sur ce challenge lors de l’événement !

Fichier fourni : animal_fabuleux

L’objectif est de trouver le bon argument (flag) à passer à ce programme.

Un premier file nous indique que nous avons affaire à un binaire ELF 64-bit.

Terminal window
~/Downloads/Hackin  file animal_fabuleux
animal_fabuleux: ELF 64-bit LSB pie executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, BuildID[sha1]=703e8337a1f696300ff09ab3426e26afa98bda38, for GNU/Linux 3.2.0, stripped

Je remarque aussi que celui-ci est stripped, ce qui rendra le travail un peu moins agréable, mais cela reste un inconvénient mineur.

Ensuite effectuer strings filtré par |grep flags révèle les chaînes suivantes :

Terminal window
~/Downloads/Hackin  strings animal_fabuleux |grep flag
wrong flag
well done! you can use this flag to validate the challenge: HNx04{%s}
Usage: %s <flag>

Enfin, avant de commencer le désassemblage, j’essaie de lancer le programme et constate cette erreur :

Terminal window
~/Downloads/Hackin  ./animal_fabuleux blablabla
./animal_fabuleux: error while loading shared libraries: libunicorn.so.2: cannot open shared object file: No such file or directory

Cela nous donne un indice énorme, le programme utilise une librairie nommée Unicorn
Après une rapide recherche google, j’apprends ce qu’est Unicorn : “Unicorn is a lightweight multi-platform, multi-architecture CPU emulator framework.

Ma première réaction a été “Oula, les problèmes”, et réfléchir à changer de challenge. Mais j’ai décidé de ne pas me laisser décourager par l’aura intimidante de celui-ci.

Après avoir installé la librairie, voici le résultat du programme :

Terminal window
~/Downloads/Hackin  ./animal_fabuleux testaaa
wrong flag

J’ai remarqué qu’entre son lancement et l’affichage de “wrong flag”, il y avait un délai, ce qui est probablement une mesure anti-bruteforce.
De plus, nous pouvons nous attendre à ce que la chaîne de retour si nous trouvons le bon flag soit : well done! you can use this flag to validate the challenge : HNx04{cequejaientré}, comme nous l’avons vu dans les strings

Takeaway :

  • Binaire stripped, pas de symbols utile
  • Le flag est au format HNx04{%s}
  • Une librairie d’émulation de CPU est utilisé (Unicorn)

Après avoir passé le programme dans Binary Ninja, je constate que le plus gros de la logique se déroule dans la fonction main. Celle-ci se décompose en 3 parties :

  1. Vérification du contexte
  2. Initialisations
  3. Boucle logique principale

Fonction main, vérification du contexte Le programme demande exactement deux arguments (son propre nom, puis le flag)
Puis il attend une seconde (la mesure anti-bruteforce)
Et vérifie si l’argument 1 (notre flag) a bien une longueur de 8 caractères. Dans le cas contraire la fonction sub_4011d9 (qui après inspection affiche la chaîne wrong flag) est appelé et le programme s’arrête.
Nous pouvons donc renommer sub_4011d9 en showFailText et continuer.

Takeaway : le flag fait 8 caractères

Ici, nous repérons plusieurs utilisations de fonctions commençant par uc_, en remontant à leurs définitions, nous constatons que ce sont des fonctions externes : Ce sont à coup sûr les fonctions venant de UniCorn (UC).

N’ayant pas trouvé de documentation explicite pour ces fonctions, je me suis rabattu sur le tutoriel sur le site officiel d’Unicorn, qui donne une vue d’ensemble de comment s’utilisent ces fonctions. À partir de cela j’ai donc déduit l’utilité de chacune d’entre elles et la signification de leurs paramètres.

  • uc_open
  • uc_mem_map
  • uc_mem_write
  • uc_emu_start
  • uc_mem_read (non présent dans l’exemple)

Prenons ces fonctions une à une :

Nous voyons que uc_open prend un paramètre d’architecture, de mode, et un pointeur sur (supposément) une structure uc_engine.

Dans le fichier unicorn.h trouvable sur github, nous pouvons voir les valeurs associées à ces flags.

Dans notre cas, l’appel était uc_open(2, 0, &var_20) ce qui correspond à uc_open(UC_ARCH_ARM64, UC_MODE_ARM, &var_20).
Le mode pourrait aussi être UC_MODE_LITTLE_ENDIAN, mais cela revient probablement au même si ARM utilise le little endian par défaut.

Takeaway: Le processeur simulé est de l’architecture ARM64 (AArch64).

uc_mem_map semble permettre de définir une plage de mémoire utilisable pour l’émulation du processeur, quant à uc_mem_write, elle semble permettre d’écrire un nombre de bytes à une adresse donnée. Nous avons donc deux fonctions permettant de manipuler les données écrites dans la mémoire virtuelle.

À partir de ces informations, nous pouvons donc modifier les noms/types des variables pour y voir plus clair :

Ce que fait ce code est donc d’initialiser l’émulation du CPU virtuel avec deux zones mémoire. La première se situant à l’adresse 0x1000 jusqu’à 0x1400 (appelons la stack 1), et la deuxième s’étendant de 0x4000 à 0x104000 (appelons la stack 2). Cette dernière a reçu l’écriture d’une suite d’instructions sous forme d’opcodes que nous pouvons trouver dans la mémoire statique du programme.

Enfin, il y a aussi une mystérieuse constante qui est initialisée avec la valeur 0x4c53, que j’ai donc nommée someConstant_4c53.

Takeaway :

  • Deux zones de mémoire virtuelles sont en place : 0x1000 - 0x1400 -> zone pour les données 0x4000 - 0x104000 -> zone pour le code
  • Une constante inutilisée pour l’instant existe, sa valeur est 0x4c53

Rendu à ce moment du désassemblage, il nous reste quelques variables à déduire :

  1. sub_4011ef -> fonction affichant le flag, c’est donc le code que nous visons
  2. var_c_1 -> semble être un compteur s’incrémentant à chaque passage dans la boucle, si nous parvenons à le rendre égal ou supérieur à 2, nous aurons le flag
  3. rax_35 -> clairement un stockage d’erreur
  4. var_30 -> sûrement un booléen, doit être false pour ne pas sortir de la boucle et incrémenter la variable var_c_1 qui nous permettra d’avoir le flag.
  5. data_40210f -> contient deux null-bytes
  6. var_11_1 -> parait parfaitement inutile

Avant de passer à l’interprétation, réécrivons le nom des variables pour clarifier :

Que fait donc cette partie du programme ? Le but pour avoir le flag est de réussir à boucler au moins deux fois dans le while, sans break, afin que counter >= 2 soit true et afficher le flag. Pour ce faire nous devons donc comme dit éviter le break dans le if (isWrongFlag), et cette variable est définie par la lecture de ce qu’il se trouve à l’adresse 0x1005 dans notre stack virtuelle (stack 1).

À partir de là, nous devons comprendre ce qu’il se passe dans le CPU virtuel pour déterminer comment garder isWrongFlag à false.

Tout d’abord la boucle while actuelle ne manipule qu’uniquement la stack 1, cela fait sens, car la stack 2 est réservé aux instructions et ne doit donc pas être modifiée.

Le premier mem_write écrit dans un premier temps 4 caractères à l’adresse 0x1000, venant de notre argv[1] (donc notre flag passé en argument). Ces 4 caractères sont sélectionnés avec un décalage (offset) de counter * 4. Donc offset 0 au premier tour, et offset 4 au second. Autrement dit, si nous passons le flag 12345678 à notre programme, la chaîne 1234 sera écrite à l’adresse 0x1000 lorsque counter est à 0 (première exécution de la boucle while), puis 5678 sera écrit quand counter == 1.

Le deuxième mem_write écrit 1 byte à l’adresse 0x1004 (donc juste après les 4 caractères du dessus), venant de la constante de l’adresse de someConstant (+ counter) qui est égale à 0x4c53. Sachant que ce système utilise le little endian et que nous n’écrivons qu’un byte, le 0x53 uniquement sera lu en premier. Puis une fois que counter sera à 1, l’adresse de someConstant + 1 pointera vers le 0x4c

Enfin, le troisième mem_write écrit un null-byte (0x00), à l’adresse 0x1005, afin de remettre à zéro le booléen de validité du flag, dans la stack virtuelle.

Finalement, nous avons la fonction uc_emu_start qui est appelé et qui lance l’émulation dans ces conditions grâce aux données insérées dans la stack jusqu’à présent.

Nous connaissons désormais tous les tenants et aboutissants, la seule chose restante à comprendre afin de former un flag est ce qu’il se passe dans les instructions du processeur ARM. Ce dernier contient la clé du crackage de ce challenge.

Voici la liste d’opcode écrit dans la stack 2 (d’instructions) du processeur virtuel : 800082d200004039081400d10a0082d2940080524b0140396b01084a7f01007180000054250080d2a40082d2850000f9080900914a050091940600519f020071a1feff5400

N’ayant jamais fait d’ARM auparavant, j’ai dû jongler entre le désassembleur en ligne et de la documentation (assistée par LLM pour accélérer la compréhension des subtilités de l’architecture) pour traduire les opcodes en logique compréhensible.

Grâce au désassembleur de Shell-Storm, nous pouvons spécifier notre architecture, et récupérer de l’assembleur ARM, lisible permettant de travailler : Afin de comprendre ce que cela signifie, essayons de traduire cela en Pseudo-C littéralement : Nous avons une base, mais cela reste peu clair, donc après avoir analysé le sens de mon propre code, voici l’algorithme qui est exécuté sur le CPU ARM :

Grâce à cela, nous savons enfin que la variable mystère someConstant est utilisée comme “clé de chiffrement”, et nous permet de trouver le flag. En effet, comme nous l’avons vu auparavant, cet algorithme sera appelé deux fois pour les deux moitiés de notre flag à 8 caractères. Et grace à ce code, nous voyons que la lettre du flag passée doit être égale à la clé passée, + un ajout de 2 à cette clé à chaque passage. Sans oublier que la clé passée à l’origine se voit soustraire 5.

Nous avons donc pour les 4 premières lettres (key passed: 0x53) : 0x53 - 0x5 = 0x4E -> (+0x2) = 0x50 -> (+0x2) = 0x52 -> (+0x2) = 0x54

Puis pour les 4 lettres suivantes (key passed: 0x4c) : 0x4c - 0x5 = 0x47 -> (+0x2) = 0x49 -> (+0x2) = 0x4B -> (+0x2) = 0x4D

Notre flag théorique final est donc \x4e\x50\x52\x54\x47\x49\x4b\x4d Qui équivaut à NPRTGIKM

Et voilà GG !


C’est maintenant en écrivant ce write-up que je suis tombé sur l’Unicorn Engine API Documentation, ce dernier contient une bonne quantité d’informations dont j’aurais eu besoin pour comprendre le fonctionnement des fonctions de cette librairie sans avoir à les déduire depuis le tutoriel.

Cela m’aurait permis de gagner du temps, mais d’un autre côté avoir été contraint de deviner le fonctionnement de l’API a été un excellent exercice ayant renforcé ma compréhension de la logique bas niveau.

Un autre point d’amélioration possible aurait été de désassembler la chaîne d’opcode elle même, afin de me donner accès directement à du pseudo C, permettant ainsi une compréhension rapide de cette partie.
Cependant n’ayant jamais fait d’ARM auparavant je pense qu’être passé par la manière manuelle a aussi été une opportunité d’en apprendre sur cette architecture, ce qui me fera gagner du temps sur mes prochains challenges. Pour la suite, il faudra que je sache utiliser du désassemblage automatisé pour la rapidité, tout en ayant appris cette architecture pour être capable de descendre à l’assembleur pour comprendre les subtilités quand nécessaire.

Merci à toute l’équipe du Hack’in pour l’événement, et au créateur de ce super challenge !
J’en garde un très bon souvenir, et ai hâte de la prochaine édition :)

(Et merci pour la banane Wannacry et les pins ahah) Image de sacoche "Wannacry" et Pins "Hardcore" et "First Blood"

Créer un système de physique avec SDL

Cet article s’attarde sur la création de comportements liés à la physique (gravité, collisions, rebonds) dans le contexte du développement de DuckDuckGame. Elle ne couvre pas la représentation des objets dans l’espace, mais uniquement la physique appliquée à ces objets.

Pour créer de la gravité, c’est très simple, il suffit qu’à un intervalle régulier de temps (chaque image), la vitesse verticale d’un objet augmente. Pour cela il suffit d’avoir une variable représentant cette vitesse, puis d’y ajouter une valeur définie tel que dans le code suivant :

speed += 0.2;
personnage->rect->y += speed;

Et voila ! Notre personnage tombe.
Il faut noter que cette approche dépend du nombre de fois que cette fonction est exécutée par seconde. Le plus, le plus vite sera la chute. Pour palier à cela il nous faudrait une variable contenant le temps depuis la dernière image (connu sous le nom de DeltaTime), et multiplier notre augmentation de vitesse par celle-ci (afin que si le nombre d’image par seconde est élevé, la distance parcouru soit petite, et inversement).
Cependant obtenir un tel nombre a ses propres défis techniques, et c’est pour cela que dans la suite de ce document nous assumerons que le nombre d’image par seconde est fixe.

Le premier code permettant de gérer des collisions était celui-ci :

speed += 0.2;
if (personnage->rect->y >= 500) {
personnage->rect->y = 500;
speed = 0;
}
personnage->rect->y += speed;
render(personnage);

Il se basait sur une variable speed (qui représentait la vitesse verticale) qui était ajoutée au personnage à chaque frame, le faisant ainsi tomber en accélérant.
En guise de sol, nous avions les coordonnées Y=500 auquel le personnage était ramené s’il les dépassait.

À noter que rect->y représente le bord supérieur du personnage : à y=500 son sommet est à 500, son bas à 500+h, donc légèrement dans le sol. La position correcte serait personnage->rect->y = 500 - personnage->rect->h, mais cela ne change pas la démonstration du principe.

Cependant cette méthode amenait un léger problème :
Quand le personnage tombe de haut, sa vitesse faisait qu’il dépassait visiblement la barrière des 500, et était ramené à l’image d’après, donnant un effet de rollback.

La correction à ceci a été d’anticiper la prochaine position du personnage à l’image d’après pour le placer directement à la bonne position (nous aurions pu vérifier de nouveau la position Y du personnage avant de le render, mais cela revient un peu au même). Ce concept d’anticipation de la prochaine position sera un fondement dans la suite du développement de ce système de collision.

Voici le code implémentant cette idée :

speed += 0.2;
if (personnage->rect->y + speed >= 500) {
personnage->rect->y = 500;
speed = 0;
}
personnage->rect->y += speed;
render(personnage);

(Le ”+ speed” après la position Y du perso, dans le if, modification discrète mais très efficace)

A partir de là, nous pouvons améliorer la structure d’un objet de manière à ce qu’elle puisse stocker les valeurs de vitesse X et Y de l’objet.
Et nous créerons une fonction (GetNextPosition) utilisant cela afin de retourner le Rect de la prochaine position de notre objet.

Maintenant, la prochaine étape sera d’améliorer ce avec quoi notre joueur a une collision. Pour l’instant nous utilisons simplement une hauteur prédéfinie dans le code, alors essayons d’utiliser un autre objet du jeu !

Nous attaquons donc les collisions “Objet - Objet” :
Pour savoir si un objet est en collision avec un autre, nous devons savoir s’ils se chevauchent, en d’autres termes, s’il y a une intersection entre eux.
Comme nous n’utilisons uniquement des rectangles pour l’instant, nous pouvons utiliser de manière très pratique la fonction SDL nommée “SDL_IntersectRect”, qui permet de savoir s’il y a une intersection entre deux Rect, et si oui d’avoir le rectangle représentant cette intersection comme montré dans le schéma suivant :

Dans notre cas, nous aurons un personnage, qui intersectionne avec un rectangle qui représente le sol, comme suit :

Nous constatons donc la collision entre ces deux objets, et la fonction SDL_IntersectRect nous retournerait bien TRUE, de plus nous récupèrerions aussi l’équivalent du rectangle bleu ici, qui représente l’intersection de ces deux Rect.
Additionnellement, ce schéma ne représente pas l’utilisation de la simulation de prochaine position que nous avons créée plus tôt. Dans les faits, à un état de repos le personnage serait situé sur le sol, et gagnerait à chaque frame de la vélocité verticale (due à la gravité). Cela déplacerait sa boite de prochaine position dans le sol, permettant ainsi de détecter la collision, et annulerait la vitesse verticale gagnée -> faisant donc effectivement rester le personnage immobile sur le sol, l’empêchant de le traverser.

Dans notre code, tout ce que nous aurons à faire c’est détecter avec la fonction SDL_IntersectRect s’il y a une collision entre la future position de notre personnage, et l’objet collisioné. Et si c’est le cas, déplacer le joueur au dessus de celui-ci :
personnage->y = obstacle->y - personnage->height
OU
personnage->y = personnageNextPos->y - IntersectRect->height

SDL_Rect* intersect = (SDL_Rect*) malloc(sizeof(SDL_Rect));
SDL_Rect* colliderNextPos = GetNextPos(collider); // GhostBox : projection de la position future du joueur
//N'oublions pas l'astuce d'utiliser la prochaine position de l'objet.
SDL_bool hasCollided = SDL_IntersectRect(colliderNextPos, collideePos, intersect);
if (hasCollided == SDL_TRUE) {
collider->rect->y = collidee->rect->y - collider->rect->h;
}
free(intersect);

Maintenant, nous avons enfin un système permettant au personnage de tomber sur un objet, et d’y rester sans bouger !

Cependant, nouveau problème :)
Le code présenté ci-dessus engendrerait des situations comme celle-ci :

Si notre joueur entre en collision depuis le côté avec ce qui représente le sol, il se fait téléporter au dessus de celui-ci.
Ce n’est de toute évidence absolument pas le comportement que nous désirons, nous devons donc adapter notre code afin qu’il puisse être plus généraliste.
L’objectif est de permettre de gérer proprement les collisions, qu’elles viennent aussi bien du côté, dessus ou dessous !

Mais pour commencer cantonnons nous à faire fonctionner les collisions pour 1 axe.
Notre code actuel fonctionne pour une collision sur 1 seul axe, ET en venant d’un seul côté de cet axe. En effet, si nous entrons en collision avec le sol que nous avons codé juste au dessus, nous nous faisons téléporter dessus ce dernier.

Pour commencer la résolution de ce problème, changeons d’abord d’axe. L’axe Y que nous utilisions jusqu’à présent était intuitif du point de vue de la gravité, cependant le fait que sa valeur augmente en descendant, ne l’est pas.
Prenons donc l’exemple d’un mur, et définissons les termes de l’explication :
Dans les exemples qui suivent, nous ferons référence à la prochaine position du joueur en tant que GhostBox, celle-ci est simplement une projection du joueur à partir de sa vélocité actuelle.

Très bien, grâce à ce que nous avons défini précédemment, cette collision serait résolue en plaçant le player juste collé au mur.

Voici le code complet implémentant les collisions de tous côtés, avec plusieurs objets simultanément :

WindowElement* collider = personnage;
SDL_Rect* colliderNextPos = GetNextPosition(collider); // GhostBox : projection de la position future du joueur
// Sachant que obs représente les objets du monde
for (unsigned i = 0; i < obs->lenght; ++i) {
WindowElement* collidee = obs->objects + i; //mieux que &obs->objects[i]
SDL_Rect* collideeNextPos = GetNextPosition(collidee);
SDL_Rect* intersect = (SDL_Rect*) malloc(sizeof(SDL_Rect));
SDL_bool hasCollided = SDL_IntersectRect(colliderNextPos, collideeNextPos, intersect);
if (hasCollided == SDL_TRUE) {
// À chacun de ces `if`, on vérifie la position du collider par rapport au collidee en utilisant leur position actuelle,
// donc PAS leur future position. Mais tout en sachant que leur prochaine position est bien entrée en collision
// Ici par exemple on sait qu'il VA y avoir collision, et on regarde si la collision vient du haut
if (collider->rect->y + collider->rect->h <= collidee->rect->y)
{
collider->vY = 0;
colliderNextPos->y -= intersect->h;
}
else if (collider->rect->y >= collidee->rect->y + collidee->rect->h) // collision vient du bas
{
collider->vY = 0;
colliderNextPos->y += intersect->h;
}
if (collider->rect->x + collider->rect->w <= collidee->rect->x) // collision vient de gauche
{
collider->vX = 0;
colliderNextPos->x -= intersect->w;
}
else if (collider->rect->x >= collidee->rect->x + collidee->rect->w) // collision vient de droite
{
collider->vX = 0;
colliderNextPos->x += intersect->w;
}
}
free(intersect);
collidee->rect->x = collideeNextPos->x;
collidee->rect->y = collideeNextPos->y;
}
// Maintenant que nous avons crafté une prochaine position cohérente, nous l'appliquons
collider->rect->x = colliderNextPos->x;
collider->rect->y = colliderNextPos->y;

Cette implémentation a une subtilité : les collisions sont résolues dans l’ordre du tableau obs->objects. Dans DuckDuckGame, deux sols se téléportent en boucle pour simuler un défilement infini, et le joueur peut se retrouver simultanément en collision avec les deux à leur jonction.

Si A est résolu en premier, seule une collision verticale est détectée, elle est résolue correctement et B ne pose plus problème. En revanche si B est résolu en premier, la GhostBox déborde à la fois sur Y et sur X : les deux résolutions sont mutuellement exclusives. Notre code vérifiant Y avant X, le comportement dépend de laquelle des deux conditions est satisfaite, et au niveau d’une jonction, le joueur glissant horizontalement peut déclencher la collision X en premier, le faisant bloquer comme contre un mur invisible.

À noter que résoudre X avant Y ne réglerait pas le problème au niveau moteur : cela inverserait simplement le cas problématique. Deux murs superposés verticalement formeraient alors une plateforme invisible.

Plusieurs approches ont été envisagées pour déterminer l’ordre de résolution :

  • Distance naïve (centre à centre) : trier par distance entre le centre du joueur et le centre de chaque objet. Rejeté : si A et B ont des tailles radicalement différentes, la distance est biaisée par la taille et non par la proximité réelle.
  • Surface d’intersection : résoudre en priorité l’objet avec la plus grande surface de collision. Rend le problème moins probable mais ne le supprime pas.
  • Double calcul : calculer les deux résolutions possibles et retenir la plus éloignée. Coûteux et probablement soumis à des edge cases.
  • Projeté orthogonal : pour chaque objet, projeter orthogonalement le centre du joueur sur l’objet pour obtenir le point le plus proche lui appartenant, puis trier par cette distance. Règle le biais de taille tout en restant simple.

Dans la pratique, le problème était imperceptible dans le jeu final, donc cette approche est restée au stade de la réflexion.

Cette approche est parfaitement fonctionnelle pour une utilisation classique, cependant elle a certaines limites dans des cas extrêmes. Imaginons que le Player aille à une vitesse très élevée, il serait possible que sa “GhostBox” passe directement derrière l’obstacle et par conséquent que le joueur le traverse. Voici un schéma illustrant ceci :

Nous pouvons essayer d’implémenter une solution avec SDL_UnionRect permettant de récupérer le rectangle contenant le joueur jusqu’à sa GhostBox (position future).

La seule différence par rapport au code précédent est la détection : au lieu d’utiliser directement la GhostBox, on construit une deltaBox couvrant le joueur de sa position actuelle jusqu’à sa GhostBox, puis on vérifie l’intersection avec celle-ci. La résolution reste identique.

SDL_FRect* deltaBox = (SDL_FRect*) malloc(sizeof(SDL_FRect));
SDL_UnionFRect(collider->rect, colliderNextPos, deltaBox);
SDL_bool hasCollided = SDL_HasIntersectionF(deltaBox, collideeNextPos);
free(deltaBox);

Après avoir testé cette méthode je vois un problème et en théorise un autre.
Le problème que je constate est que si le personnage est sur une plateforme qui monte, il ne peut plus sauter. Après investigation cela est dû au fait que dans ce code la boite d’union comprend la position actuelle du personnage et n’est pas basé uniquement sur ses positions futures. Cela a pour effet de créer une collision alors que dans le futur il n’y en aurait pas eu.
Ce problème peut être mitigé en enlevant la largeur et hauteur du Rect du perso à cette box et en la décalant dans la bonne direction.
Cependant ce problème m’a fait penser à un autre, ce système de boite d’union est présent pour avoir des collisions continues même si l’objet va à une haute vitesse. Cependant si l’objet va en diagonale la boite va s’étendre dans les deux directions diagonales tangentes et potentiellement entrer en collision avec un mur alors que l’objet serait simplement passé à côté avec un calcul normal. Pour régler cela il faudrait utiliser des raycasts afin de vérifier si une intersection LINEAIRE existe. Voir le schéma suivant :

Le système initial étant déjà suffisant pour ce que nous faisons, et n’ayant pas un temps illimité pour expérimenter, nous allons revenir à la version précédente du système de collision qui fait déjà suffisamment l’affaire. Cependant nous savons que si nous nécessitons éventuellement d’une version plus robuste, nous avons le modèle ici.

Implémenter un système de rebond une fois les bases physiques posées est plutôt simple.
Il nous suffit de définir un coefficient de rebond pour les objets du jeu, et de multiplier la vitesse du joueur sur l’axe de la collision par le négatif de ce coefficient ; inversant ainsi sa direction d’un facteur défini.
Exemple :
Le joueur avance de 5 vers la droite (mouvement sur X), il rencontre un obstacle avec un coefficient de rebond de 1.
Nous avons donc vitesse_joueur * -(coeff_rebond) = new_vitesse_joueur,
donc ici 5 * -1 = -5, notre joueur ira donc dans l’autre sens sans perte de vitesse, soit le comportement attendu.

Voici ce que cela donne en code :

// ...
// Si collision :
// Coefficient de rebond :
// 0 -> Aucun rebond
// 1 -> Rebond total, aucune perte de momentum
float bounciness = 1;
// Si collision sur axe Y, venant du dessus
if (collider->rect->y + collider->rect->h <= collidee->rect->y)
{
// Négation de la vitesse Y et multiplication par le coefficient de rebond
collider->vY *= -bounciness;
// Gestion de la collision
}
// Gestion de l'axe Y venant du dessous et axe X similaire
// ...

À noter que cette formule suppose que le collidee est statique, ou du moins qu’il ne réagit pas à la collision (il pourrait par exemple être en mouvement linéaire, comme une plateforme qui se déplace). Dans le cas où les deux objets sont en mouvement et réagissent l’un à l’autre, il faudrait introduire la notion de masse et appliquer la conservation de la quantité de mouvement pour calculer les nouvelles vélocités des deux objets.