Harry Potter et le python matriciel

Qui veut un puzzle marrant inspiré de l’univers de Harry Potter, généré avec du fourchelang le langage python et les librairies numpy + opencv ?

Voilà comment ça se présente :

(click to enlarge, biâtch)

Ceci est un quadrillage composé de 12 cases (3 lignes 4 colonnes), chaque case contient un groupe de 4 clés.

Chaque clé est présente une ou deux fois dans tout le quadrillage.

Si vous prenez deux cases adjacentes, elles ont toujours une clé en commun. Leurs emplacements à l’intérieur des cases sont aléatoires.

Or donc, :

• pour les cases du milieu, les 4 clés ont une jumelle sur chacune des 4 cases adjacentes,
• pour les cases du bord, 3 clés sur 4 ont une jumelle, et la quatrième est unique (sont emplacement à l’intérieur de la case est aléatoire),
• pour les cases des coins, 2 clés sur 4 ont une jumelle, les deux autres sont uniques.

Imprimez cette feuille, découpez les cases, mélangez-les et essayez de retrouver la disposition originale. Quel distrayant puzzle !

Il m’en faut plus

Pas de problème, en voilà un fonctionnant sur le même principe, mais sur un quadrillage de 8×8 cases.

Pour des images plus grandes et de meilleure qualité, c’est par ici dans ce repository git. Elles doivent être disposées comme ceci :

plank_00.png | plank_03.png | plank_06.png | plank_09.png
plank_01.png | plank_04.png | plank_07.png | plank_10.png
plank_02.png | plank_05.png | plank_08.png | plank_11.png

Comment c’est construit ?

Les clés

Pour commencer, il vous faut des images pour générer les clés.

Nous avons donc : (3 types d’aile) x (4 types de bas de clé) x (4 types de haut de clé) x (3 types de tige). Soit 3 * 4 * 4 * 3 = 144 combinaisons différentes de clés.

On peut maintenant construire une image d’une des clés à partir d’un numéro entre 0 et 143. Il vous faudra effectuer quelques divisions entières, quelques modulos et utiliser open-cv (la lib python de manipulation d’image). Je vous fais grâce de ces détails bassement techniques.

Les associations horizontales

Vous prenez ensuite tous les nombres entre 0 et 143, vous les mélangez, et vous les séparez en deux listes de 72 nombres chacune. La première servira pour les clés définissant les liens d’adjacence horizontaux, la deuxième sera pour les liens verticaux.

Réarrangez la première liste en un rectangle de 8 lignes 9 colonnes. Mettons que ça donne ceci :

  7  17  38   4 68 125  96 135  16
101 118  97  73 46 143  92  89   2
 86  14  62  56 10   9   6  19   3
134  36  37  93 13  57  81  52  74
 66   8  71 109 60  40  65  69  27
 59 105   0  76 41  49  91 107  99
115  95  75  48 83 142 141 130  64
  1  51 104 102 22  54  80  34 129

Ensuite, vous recopiez la deuxième colonne juste à sa droite, puis la troisième, et ainsi de suite jusqu’à l’avant-dernière. Ça donne ce rectangle de 8 lignes 16 colonnes (que je vous mets sous forme de tableau, sinon ça fait des retours à la ligne pourris dans wordpress) :

7	17	17	38	38	4	4	68	68	125	125	96	96	135	135	16
101	118	118	97	97	73	73	46	46	143	143	92	92	89	89	2
86	14	14	62	62	56	56	10	10	9	9	6	6	19	19	3
134	36	36	37	37	93	93	13	13	57	57	81	81	52	52	74
66	8	8	71	71	109	109	60	60	40	40	65	65	69	69	27
59	105	105	0	0	76	76	41	41	49	49	91	91	107	107	99
115	95	95	75	75	48	48	83	83	142	142	141	141	130	130	64
1	51	51	104	104	102	102	22	22	54	54	80	80	34	34	129

Pour finir, sur chaque ligne, vous regroupez les numéros par couple. Ce qui vous donne un rectangle de 8 lignes et (8×2) colonnes :

7,17	17,38	38,4	4,68	68,125	125,96	96,135	135,16
101,118	118,97	97,73	73,46	46,143	143,92	92,89	89,2
86,14	14,62	62,56	56,10	10,9	9,6	6,19	19,3
134,36	36,37	37,93	93,13	13,57	57,81	81,52	52,74
66,8	8,71	71,109	109,60	60,40	40,65	65,69	69,27
59,105	105,0	0,76	76,41	41,49	49,91	91,107	107,99
115,95	95,75	75,48	48,83	83,142	142,141	141,130	130,64
1,51	51,104	104,102	102,22	22,54	54,80	80,34	34,129

Chaque couple de deux numéros correspond à deux clés, dans une case du quadrillage initial de 8×8. Il s’agit des clés réalisant les adjacences horizontales.

Les deux autres clés de chaque case ne sont pas encore définies, ce qui nous amène au chapitre suivant.

Mais avant, une petite pause. Puisque nous sommes dans l’univers de Harry Potter, voici Dawn French, l’actrice qui joue « La Grosse Dame » dans le Prisonnier d’Azkaban.

Les associations verticales

C’est pareil, mais en inversant les lignes/colonnes.

Prenez les 72 valeurs qui restent, disposez-les randomement dans un rectangle de 9 lignes 8 colonnes.

 12 114  15  45 128 120  44  28
  5 110 136 132 126  72  39  88
 78  11  70 127  47 124 117  33
 25 103  20  82  29 139  26 113
106 140 123 122  94  30 119  32
 79  23  21  98  24  55 137 111
 77 138 108 100  53  67  85 133
 58 112  84  90  35 131 121  31
 43  61  87 116  63  42  50  18

Au lieu de doubler les colonnes, doublez les lignes : de la 2ème à l’avant-dernière. Ce qui donne un rectangle de 16 lignes 8 colonnes :

 12 114  15  45 128 120  44  28
  5 110 136 132 126  72  39  88
  5 110 136 132 126  72  39  88
 78  11  70 127  47 124 117  33
 78  11  70 127  47 124 117  33
 25 103  20  82  29 139  26 113
 25 103  20  82  29 139  26 113
106 140 123 122  94  30 119  32
106 140 123 122  94  30 119  32
 79  23  21  98  24  55 137 111
 79  23  21  98  24  55 137 111
 77 138 108 100  53  67  85 133
 77 138 108 100  53  67  85 133
 58 112  84  90  35 131 121  31
 58 112  84  90  35 131 121  31
 43  61  87 116  63  42  50  18

Faites des couples, en prenant deux valeurs l’une au-dessus de l’autre. Ça donne un carré de 8×8. Cette fois-ci, je le mets sous forme de texte-code, car les lignes sont plus courtes et ne vont pas faire de stupides retours à la ligne. Tant que ça ne nuit pas à l’affichage et à la présentation, je préfère le texte brut, c’est plus facile à générer et à copier-coller dans l’article. Vive le texte brut !

 12|114| 15| 45|128|120| 44| 28
  5|110|136|132|126| 72| 39| 88
-------------------------------
  5|110|136|132|126| 72| 39| 88
 78| 11| 70|127| 47|124|117| 33
-------------------------------
 78| 11| 70|127| 47|124|117| 33
 25|103| 20| 82| 29|139| 26|113
-------------------------------
 25|103| 20| 82| 29|139| 26|113
106|140|123|122| 94| 30|119| 32
-------------------------------
106|140|123|122| 94| 30|119| 32
 79| 23| 21| 98| 24| 55|137|111
-------------------------------
 79| 23| 21| 98| 24| 55|137|111
 77|138|108|100| 53| 67| 85|133
-------------------------------
 77|138|108|100| 53| 67| 85|133
 58|112| 84| 90| 35|131|121| 31
-------------------------------
 58|112| 84| 90| 35|131|121| 31
 43| 61| 87|116| 63| 42| 50| 18

Chaque couple de deux numéros correspond aux deux autres clés, dans chaque case du quadrillage initial de 8×8. Elles définissent les adjacences verticales.

Enfin, pour chaque case, vous mélangez randomement les 4 clés contenues dedans.

Y’a plus qu’à coder tout ça. Vous avez une implémentation (un peu à l’arrache) dans ce repository, dans lequel je stockais déjà d’autres bazars pour des mini-jeux et mini-énigmes.

Vérification de l’unicité de la solution

J’ai vérifié avec mon feeling de maître de conférence en arithmancie combinatorio-serrurologique, j’en conclus que oui c’est bon. Aux rotations et aux symétries verticales/horizontales près : y’a qu’une solution.

J’ai utilisé ce puzzle pour une sorte de mini escape-game en famille, et j’ai profité des rotations et symétries pour ajouter une mini-post-énigme. J’ai écrit une lettre derrière chaque carte. Une fois que le puzzle était reconstitué, il fallait toutes les retourner, et retrouver la phrase composée par ces lettres. L’astuce amusante, c’est qu’on ne peut pas déterminer à l’avance le sens de lecture, ni la position de la carte de départ, ni celle d’arrivée. Ça dépend de la manière dont le puzzle a été résolu. Il faut donc tester différents sens pour trouver la phrase finale. Hi hi hi !!

Et hop, d’autres chouettes images de Dawn French.

Tchuss.

TUR-ROX-👁 Post-creationem-challengem

Heeey !

J’ai terminé la réalisation de mon challenge de hacking pour la THCON. Je l’ai soumis aux personnes qui organisent l’événement. Je ne sais pas encore s’il sera accepté. Dans tous les cas, je ne peux rien vous révéler avant la fin du Capture The Flag, qui aura lieu entre le 16 et le 17 avril.

Cependant, ça me démange de ne pas pouvoir vous parler de mon œuvre, alors je vais vous révéler son contexte et tout ce qui m’est passé dans la tête durant sa création. Ça ne devrait rien spoiler, je ne décris pas les énigmes en elle-même.

Le contexte

J’en ai déjà parlé un peu à la fin de cet article.

Il s’agit du jeu vidéo Eye Of The Beholder, dont j’ai modifié les plans des niveaux et les événements à l’aide de l’outil All-Seeing Eye et de son éditeur.

Pour résoudre le challenge, il faut jouer à la version modifiée tout en inspectant son contenu avec All-Seeing Eye. Il faut analyser les scripts et en déduire les actions à faire dans le jeu, pour obtenir le code secret permettant de valider le challenge. Je ne vous en dis pas plus.

Ce challenge, ainsi que les deux autres créés pour la précédente THCON, s’inscrivent dans un objectif plus global : l’instauration d’une nouvelle catégorie de challenge de hacking, que j’ai sybillinement baptisé « TUR-ROX ». Ça signifie « TURing-appROXi-complete video games ». C’est même pas un vrai sigle, c’est pas du tout les initiales des mots, mais j’m’en fous total, j’suis un ouf’ rebelle malade.

Principe des challenges de type TUR-ROX

Le principe consiste à trouver un jeu vidéo comportant un système de script intégré, à le modifier dans le but d’y implémenter un algorithme plus ou moins simple, et à faire en sorte que le flag ne puisse être découvert que lorsque cet algorithme est compris.

L’inspection et la modification du jeu peuvent être effectuées par un outil « officiel » (comme l’éditeur de ZZT), ou bien par un outil ne provenant pas des personnes ayant créé le jeu (comme All-Seeing Eye). Le système de script peut être plus ou moins élaboré. Au minimum, il doit pouvoir accéder à certains éléments du jeu. S’il comporte quelques structures algorithmiques de base, (if, while, …), c’est déjà bien.

En général, on fournira cet outil avec le challenge, afin de donner tous les moyens nécessaires à sa résolution. Mais on pourrait faire exception à cette règle.

Beaucoup de jeux actuels sont fortement moddables et scriptables. Les gens qui les développent ont réfléchi deux secondes et se sont dit qu’il serait bon de profiter des expériences du passé. Les scripts s’appuient maintenant sur des langages de programmations standards, multi-usages et documentés. Par exemple : Roblox utilise le Lua, Twine utilise du JavaScript, les gros moteurs de jeux comme Unity autorisent plusieurs langages (python, C#, …).

C’est la meilleure démarche possible, ça facilite les liens entre les personnes qui veulent créer des jeux vidéos et qui ne savent pas (encore) coder, et les personnes qui codent sans créer de jeux.

Mais ce n’est pas avec ça que je peux faire des chouettes challenges TUR-ROX. Du code à rétro-ingénierer dans un langage connu, c’est trop facile. Un foisonnement de documentation, d’outils d’analyse et de debugging sont à portée de clavier. Une solution serait de faire exprès d’écrire du code le plus incompréhensible possible, mais serait alors un challenge de type obfuscation, et non plus un TUR-ROX. Il existe déjà une foule de gens capable de créer des challenges d’obfuscation, et ce mieux que moi.

Un TUR-ROX est un mix entre un jeu vidéo et du code source à décortiquer, le système de script doit donc être spécifique au jeu. En revanche, il peut être obscur et mal documenté, ça fait partie du challenge de le comprendre avec les moyens disponibles. C’est pour ça que je préfère utiliser des jeux anciens ou exotiques. On est obligé de se plonger dans leur histoire, de retrouver comment pensaient les concepteurtrices de jeux à une époque où il y avait moins de standards.

Et cette année, j’ai choisi Eye Of The Beholder. Mais pourquoi donc ?

Attention : Turok ≠ TUR-ROX

Eye Of The Beholder, parce que nostalgie

Ce n’est pas la première fois que j’écris un article sur ce jeu. Il a marqué mon enfance. Je l’ai commencé alors que j’étais en sixième, en explorant un peu au hasard. Une solution a été publiée dans un magazine Tilt, j’ai demandé à mon frère de la photocopier. On a commencé à s’en servir avec mon autre frère, on est allé jusqu’au niveau 7. Ensuite, notre intérêt pour le jeu a diminué. De plus, ce niveau est graphiquement plus inquiétant que les précédents (très sombre, des symboles d’araignés omniprésents), et il commence par un difficile combat contre un groupe d’elfes noirs. J’ai douté de mes capacités à en venir à bout, j’ai laissé tomber.

Moustache ! moustache !

Je me suis fait engueuler par mon frère, qui m’a reproché que les photocopies avaient été faites pour rien puisque je n’étais même pas foutu de les utiliser entièrement.

Quelques années plus tard, j’ai recommencé le jeu seul. J’ai pris le temps d’élaborer une équipe bien équilibrée, couvrant le plus de classes possibles. J’ai tué tous ces tocards d’elfes noirs et je suis arrivé au niveau 10. Il comporte un générateur de Mantis Warrior. J’avais réussi à faire abstraction du générateur d’araignée géante présent au niveau 4, mais celui des Mantis m’a psychologiquement bloqué.

Ce que j’aime dans ce jeu, c’est le sentiment de « nettoyer » les souterrains. On explore partout, on tue tous les monstres qu’on rencontre et on prend tous les objets. À chaque fois qu’on finit un niveau, on peut se dire : « Voilà, il n’y a plus aucun danger. Je pourrais revenir me promener dans ce niveau sans aucune crainte ». Concrètement, on n’a pas besoin d’y revenir, mais j’aimais éprouver cette sécurité et cette impression de rendre le monde meilleur. Or, les générateurs de monstres enlèvent complètement ce sentiment.

Encore une ou deux années plus tard, je me dis que c’est quand même dommage d’être allé aussi loin dans le jeu sans le finir. Je détruis 4 Mantis Warrior à la suite dans le niveau 10. Je parviens à me faire une raison : les prochains seront générés dans longtemps, je peux toujours éprouver un sentiment de nettoyage même provisoire, et si il faut vraiment sécuriser entièrement les souterrains, eh bien les notables de la ville de WaterDeep n’auront qu’à envoyer des magiciens destructeurs de générateurs de monstres !

J’écume les derniers niveaux, je bute Xanathar à la bourrin (je possédais le « Wand of Silvias », mais je n’avais pas compris qu’on pouvait s’en servir pour le faire reculer jusque dans des pics où il se plante stupidement). Mon frère revient à la maison pour des vacances. Je lui annonce que j’ai terminé le jeu. Il est heureux pour moi, mais ne s’excuse pas de m’avoir engueulé des années auparavant. Il ne se souvenait certainement pas de ce passage de sa vie.

Maintenant que j’y pense, ce même frère m’avait soutenu lorsque je suis allé rapporter à la FNAC un jeu qui ne marchait pas. On a pu obtenir un avoir, ce qui n’était pas gagné d’avance, et je crois que je ne l’ai jamais remercié pour ça.

D’autres années plus tard, je commence un tout petit peu Eye Of The Beholder 2, mais je ne prends pas le temps de me lancer vraiment dedans. J’essayerais peut-être de le faire un jour, en live sur Twitch, avec vous.

Pour finir, j’ai négationné mes deux frères et je me sens mieux. Je ne détaille pas plus, je ne veux pas vous embêter avec des histoires idiotes.

Aujourd’hui, j’ai retrouvé la solution, sans faire de photocopies. Merci au site abandonware-magazine !

Eye Of The Beholder, parce que script

Je me souvenais d’énigmes et d’événements tellement étranges que ça laissait supposer la présence d’un système de script relativement générique. Quelques exemples :

• Vous avancez dans un couloir et automatiquement vous faites un demi-tour, sans être prévenu.
• Vous posez certains objets à certains endroits, ça déclenche l’apparition d’un monstre et/ou d’autres objets.
• Vous entrez dans une pièce, vous ramassez une potion, vous sortez, vous re-rentrez par une autre entrée, une deuxième potion est apparue, vous la ramassez, ainsi de suite jusqu’à 4 potions.
• Des rencontres avec des PNJ déclenchant des dialogues, des ajouts de nouveaux personnages, des attaques, etc.
• Des téléporteurs, des murs qui disparaissent quand on appuie sur un bouton, des plaques de pression qui déclenchent des ouvertures/fermetures de portes, etc etc.

J’ai cherché un éditeur de niveau et je suis très vite tombé sur « All-Seeing Eye », créé par Joonas Hirvonen (je sais pas qui c’est). Il permet de modifier beaucoup de choses, y compris les scripts.

Au bout de quelques soirées et quelques week-ends, j’avais assez bien appréhendé le « EOB-script » (appelons-le comme ça) et j’avais une idée assez précise des énigmes que je pouvais créer.

J’ai été impressionné. Ça date de 1991 et c’est une machine virtuelle fonctionnant avec du bytecode. Son langage, comme dirait les Inconnus, est « souple et solide à la fois ».

Voici les fonctionnalités de l’EOB-script qui m’ont beaucoup plues.

• 32 variables booléennes locales à chaque niveau + 32 variables booléennes globales.
• Opérations booléennes complexes à l’aide de la notation postfixe .
• Beaucoup de fonctions pour analyser l’état du jeu : présence de monstre à un endroit, type de mur d’une case spécifique, présence d’un type d’objet sur une case, position de l’équipe de personnages, classe et race des personnages, …
• Et aussi beaucoup de fonctions pour agir sur le jeu : créer/supprimer des objets/murs/monstres, lancer un sort, émettre un son, infliger des dégâts, …
• Branchement conditionnel (if – goto), mais aussi sous-fonctions grâce aux instructions gosub et return, dont j’ai grandement profité !
• Gestion d’événements couvrant un large spectre : on peut exécuter un script sur une récupération ou un dépôt d’objet, une arrivée ou une sortie sur une case, un clic dans la zone réactive d’un mur (manette, serrure, rune, …).
• Cohérence dans la gestion d’événements : une téléportation déclenchera le « on_enter » de la case d’arrivée, un lancer d’objet déclenchera le « on_put_item » de la case sur laquelle l’objet atterrit.
• Robustesse : sur un seul événement, il est possible de déplacer des dizaines d’objets, modifier des dizaines de murs, exécuter des dizaines d’instructions, écrire des dizaines de messages (même si seuls les trois derniers sont visibles), tout ça sans problème, sans plantage, sans ralentissement.

En revanche, All-Seeing Eye n’est pas toujours à la hauteur de la magnificence de l’EOB-script. En particulier, on ne peut pas changer les dialogues et les événements des rencontres avec les PNJ. Je ne sais pas si c’est dû à un simple manque de motivation ou à une impossibilité technique. Je ne sais pas si ces événements sont écrits en EOB-script ou codés en dur. Je ne sais pas non plus où ils sont stockées, (pas forcément dans les fichiers EOBDATA.PAK).

J’ai beaucoup de remarques et de propositions d’améliorations, ce qui nous amène au chapitre suivant.

Ils sont meugnons !

Review de All-Seeing Eye (Pour plus tard)

Je vais faire un petit don de 20 euros sur le Paypal de Zorbus.net. C’est amplement mérité. S’ils n’avaient pas créé All-Seeing Eye, je n’aurais jamais pu créer ce challenge de hacking dont je suis assez fier.

Comme j’ai bien utilisé et exploré leur outil pendant plusieurs semaines, et que j’ai un peu galéré à cause de certains bugs, j’ai souhaité rassembler mes remarques dans un même document, que je leur transmettrais.

Et comme j’aime bien rentabiliser les textes que j’écris, je mettrais ces remarques aussi dans ce blog. Mais pas tout de suite, ce sera l’objet du prochain-prochain article. Il sera en anglais, mais vous vous débrouillerez bien.

Je vous laisse avec des yeux tatoués sur des seins. Je trouve ça très rigolo.