Je voulais créer un jeu, j'ai écrit un compilateur.

Click4 est une fantasy console avec une contrainte de création originale et des limitations techniques très fortes. Tellement fortes, que j'ai fini par écrire mon propre compilateur et IDE pour réussir à créer un jeu dessus.

Dans cet article, apprends-en plus sur les fantasy console, le processeur, l'assembleur, les compilateurs et Godot.

Pas de détails trop complexes, c'est promis.

DISCLAIMER : Mon implémentation est probablement très naïve et loin de ce que pourrait être un vrai compilateur. Le but c'est de comprendre les fondamentaux.

Pourquoi Click4 est un vrai défi.

Click4 utilise des "cartouches" virtuelles pour stocker ses jeux. La cartouche est en faite une image, un fichier .png que la console peut lire. Chaque pixel de cette image sera interprété par la console comme une instruction, une couleur, une valeur, un son.

Par exemple un pixel noir sera lu soit comme "ne rien faire", soit comme la couleur noir, soit comme la valeur 0. Le sens de chaque pixel va dépendre des pixels qui le précèdent.

Il est possible de créer son jeu en dessinant une image, pixel par pixel, dans un éditeur d'image. On peut aussi le faire directement dans la console.

En plus de cette contrainte étonnante, il y a aussi des limitations techniques très fortes:

• Un CPU 4-bits (16 valeurs possibles, de 0 à 15)
• Seulement 13 opérations en assembleur, un langage difficile à utiliser, très proche de la machine.
• Une mémoire de 4096 nombres 4-bits, qui doit tout contenir (code, RAM, sprites).
• Pas de stack, pas de heap, donc une gestion mémoire complexe.

Pour réussir à créer un jeu sur cette console, j'ai décidé de créer une IDE simple. Oui, ça semble un peu exagéré, mais c'est pour le fun.

Comment transformer du code en image ?

Click4 lit chaque pixel de l'image un par un, et le traduit en une instruction assembleur ou une valeur.

Au départ, mon plan était simple :

1. Pouvoir programmer un jeu en écrivant des opérations en assembleur dans un éditeur de texte.
2. Transformer ce texte en image lisible par Click4

Il suffit d'écrire un programme qui lit chaque ligne du code, l'associe à la bonne couleur et le dessine sur une image. Appelons ça un Parser.

Mais comme vous l'avez deviné dans le titre, je ne vais pas me contenter de faire ça...

Godot pour programmer l'éditeur ?

J'ai choisi de créer mon éditeur avec le moteur de jeu Godot. Je sais, ça ne semble pas approprié. Mais Godot a tout ce qu'il faut pour faire rapidement une application fonctionnelle.

En faite, l'éditeur de Godot est lui même programmé avec Godot. Il y a donc déjà beaucoup de widgets et de systèmes pour gérer la GUI.

En à peine 1 heure, j'avais déjà une application basique pour taper du texte.

Le tout est automatiquement responsive grâce au système de container de Godot. Et il existe déjà un node TextEdit avec de nombreux paramètres (afficher les numéros de lignes, afficher une minimap du code, surligner la ligne courante, etc...).

Je ne détaillerais pas plus l'implémentation de l'IDE dans Godot. L'important c'est de noter que je n'ai eu aucune difficulté à faire tout ce dont j'avais besoin avec Godot.

Comment j'en suis arrivé à créer un langage et son compilateur

Trop d'erreur simples à gérer

Je faisais beaucoup d'erreurs simples; Oublier un paramètre, utiliser la mauvaise instruction, etc...

J'ai décidé d'améliorer mon Parser, pour qu'il analyse le code et m'aide à trouver rapidement les erreurs les plus simples.

Difficile de faire des conditions ou des boucles

En assembleur, il n'y pas de concept de condition ou de boucle. À la place, on utilise des conditionnal jumps qui permettent de sauter à une adresse précise en mémoire selon une certaine condition. LE CPU continue d’exécuter le programme à partir de cette adresse.

Mais avec Click4, c'est une autre histoire. L'opération "jmp" prend en paramètre la position (x, y) sur l'image.

On complique encore un peu la chose ? L'image finale a une résolution de 64x64 pixels. Donc on pourrait imaginer vouloir sauter en position (35, 36) par exemple.

Cependant, notre cpu est 4-bits, donc on ne peut pas représenter un nombre supérieur à 15. Il faut utiliser 2 blocs mémoire (2 nombres 4-bits) pour représenter un nombre supérieur à 15.

Alors je ne vais pas vous faire un cours sur le binaire, mais si on veut sauter en (35, 36) il faudrait écrire cette instruction.

jmp 2 3 2 4

Et c'est pas terminé. Dès qu'on rajoute une instruction dans notre code, il faut mettre à jour l'adresse du jump.

On verra plus loin comment j'ai implémenté des labels pour résoudre ce problème.

Pas assez d'opérations

Voici la liste des 13 opérations assembleur disponibles pour Click4 :

• 0 nop : no operation (do nothing)
• 1 set &arg1 arg2 : Set contents of register defined by ARG1 with value of ARG2.
• 2 copy &arg1 &arg2 : Copy the contents of register defined by ARG2 to the contents of register defined by ARG1.
• 3 inc &arg1 : Increment register defined by ARG1.
• 4 dec &arg : Decrement register defined by ARG1.
• 5 nand &arg1 &arg2 &arg3 : NAND the values of registers defined by ARG2 and ARG3 and store in register defined by ARG1.
• 6 crsz &arg1 : Increment program counter by 2 if register defined by ARG1 is zero.
• 7 jmp &arg1 &arg2 &arg3 &arg4 : Change program counter to position X(ARG1,ARG2) Y(ARG3,ARG4). Notice each coordinate is composed of two nibbles to be able to jmp on the whole screen.
• 8 rjmp arg1 : Increment program counter by ARG1 plus 1.
• 9 load : Load contents of X(R1+R2), Y(R3+R4) to R0 (X and Y use two nibbles).
• 10 save : Save contents of R0 to X(R1+R2), Y(R3+R4).
• 11 input &arg1 : Copy values of WASD or Up, Right, Down, Left into the register defined by ARG1.
• 12 draw : Draw area of screen with SourceX(R0+R1), SourceY(R2+R3), Width(R4) plus 1, Height(R5) plus 1, TargetX(R6+R7), TargetY(R8+R9)
• 13 qsnd &arg1 : Enqueue sound from register defined by ARG1.

Pas d'addition, de division, d'opérations logiques ou de moyen de sauter selon des conditions précises.

Cependant, c'est possible de recréer ces fonctionnalités à partir de ces 13 opérations. Par exemple, voici le code pour faire une addition de deux nombres stockés dans les registres r0 et r1 :

;; add r1 to r0 and store the result in r0
@add
crsz r1 ;; if r1 == 0 return
rjmp 4	;; otherwise jump to increment
jmp @endadd
inc r0
dec r1
jmp @add
@endadd

Note que j'utilise des labels pour les jump.

Ça demande pas mal de code et plus d'une vingtaine de bloc mémoires juste pour faire une addition. J'ai écrit une autre version de l'addition pour les nombres 8-bits. Elle utilise 42 blocs mémoires...

Le code sera illisible est dur à maintenir si on doit récrire à chaque fois. Il faudrait pouvoir ajouter des opérations, comme "add" par exemple. Le Parser reconnaît l'instruction add, et la remplace avec le code correspondant.

À partir de maintenant, on ne parlera plus de Parser, mais bien de Compilateur.

La création d'un langage et de mon compilateur

Des mots clés et des commentaires

J'ai rajouté un système de commentaires, du contenu qui sera ignoré par le compilateur.

J'ai aussi rajouté beaucoup de mots clés pour les registres, les couleurs, les sons, les nombres etc... Ils sont ensuite remplacés par des opcodes (0 à 15) à la compilation.

set r0 0     ;; r0 sera remplacé par le nombre 0 à la compilation
set r2 red   ;; red sera remplacé par le nombre 1 à la compilation
set r4 c#    ;; c# (la note de musique) sera remplacée aussi
set r6 b0010 ;; la notation binaire sera remplacé par 2 

Les Defines

J'ai rajouté de quoi associer une valeur à un nom. Très utile pour créer des constantes facilement modifiables et utilisables à plusieurs endroits dans le code.

#define player_start_pos_x 10
#define another_const 2
#define starting_HP 15

Les Labels

Les labels sont là pour répondre au problème du jump. Voici une boucle infinie qui incrémente le registre 0.

@monlabel
inc r0
jmp @monlabel

À la compilation, le "@monlabel" en argument de jmp est remplacée par la bonne position sur l'image.

@monlabel
inc r0
jmp 0 0 0 0

L'important pour le compilateur ici, c'est de bien lire les labels une fois qu'on a toute les instructions. En effet, imaginez qu'on ai ce code :

jmp skip_line
inc r0
@skip_line

Au moment du jmp, on ne connaît pas encore l'existence du label skip_line. Il faut donc :

1. Lire toutes les instructions une première fois
2. Stocker tous les labels existants (et leur associer une position en mémoire)
3. Remplacer les labels dans tous les jumps avec la bonne position.

les Sprites

Les sprites doivent être stockés dans la mémoire. Cette mémoire contient aussi notre code. Il faut faire attention à bien les différencier et ne pas écraser notre code avec les sprites et vice-versa.

J'ai dédié une zone de la mémoire aux sprites.

On "dessine" nos sprites directement dans le code.

;; put your game code here

== sprites

;; sprite 1
0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0
0 0 0 1 1 0 0 0
0 1 1 1 1 1 1 0
0 1 1 1 1 1 1 0
0 0 0 1 1 0 0 0
0 0 0 1 1 0 0 0
0 0 0 0 0 0 0 0

;; sprite 2
0 0 0 0 0 0 0 0
0 0 0 4 4 0 0 0
0 0 0 3 3 0 0 0
0 0 0 2 2 0 0 0
0 0 0 1 1 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

Le compilateur va automatiquement les placer dans notre mémoire réservée.

On peut ensuite utiliser quelque #define pour stocker la position de nos sprites, et utiliser l'opération draw de Click4.

la heap

Click4 possèdent 15 registres pour stocker des valeurs temporairement. Pour stocker des variables sur le plus long terme, il faut les stocker dans notre mémoire (qui contient aussi le code et les sprites).

On peut utiliser les instructions save et load de Click4. Ici on stocke 5 à la position (15,15) en mémoire.

set r0 5
save 0 15 0 15

Ce n'est pas très pratique. Il faut se souvenir de toutes les positions, et s'assurer de ne jamais stocker plusieurs choses au même endroit.

J'ai créé une "heap" basique. En bref, une heap (ou tas en français) est un endroit en mémoire où l'on peut stocker des valeurs et les modifier. Quand vous faites un appel à new en c++, en général un espace sur la heap vous ai réservé.

C'est le système d'exploitation qui s'occupe de donner la mémoire aux programmes. Dans notre cas, il faut le gérer nous-même.

Voici un exemple d'utilisation de ma heap.

#alloc player_pos_x 15

hload player_pos_x ;; load the value stored on the heap in r0
dec r0
hsave player_pos_x ;; save the value of r0 on the heap

A chaque #alloc, le compilateur nous réserve un bloc mémoire pour stocker notre variable. J'ai choisi une position de départ pour ma heap (63, 55). À chaque nouvelle allocation :

1. On réserve la position actuelle pour la variable.
2. On y stocke sa valeur par défaut (15 dans l'exemple)
3. On décrémente la position pour la prochaine variable.

Dans le code final, les instructions hload et hsave sont remplacées par des load et save.

Normalement dans une heap, on peut aussi libérer des variables, pour libérer l'espace mémoire. Celle-ci ne peut pas le faire, les espaces sont réservés pour toujours.

Les opérateurs logiques

On veut pouvoir utiliser des opérateurs logiques comme le OR, le NOT, le AND, etc...

Nous n'avons que le NAND avec Click4. Le NAND a une propriété bien particulière appelée functional completeness. À partir du NAND on peut recréer toutes les autres opérations logiques !

On pourrait même recréer un ordinateur qu'avec des NAND.

Un exemple avec le NOR :

;; r0 NOR r1 into r0
;; A NOR B <=> (A NAND A) NAND (B NAND B)
;;                        NAND
;;             (A NAND A) NAND (B NAND B)
nand r0 r0 r0
nand r1 r1 r1
nand r0 r0 r1
nand r0 r0 r0  

les conditions

En général on utilise les opérateurs logiques dans des conditions.

Click4 ne nous donne que crsz, qui saute 2 blocs mémoires plus loin si r0 == 0 (sinon il passe au bloc mémoire suivant).

Et bien... ça nous suffit pour implémenter le reste.

On va implémenter deux concepts qu'on retrouve dans d'autres langages assembleur :

• cmp
• un ensemble de jump conditionnel

L'opération cmp compare les valeurs dans r0 et r1, et modifie r15 en fonction de la comparaison.

Si r0 < r1, r15 = 1.

Si r0 == r1, r15 = 2.

Si r0 > r1, r15 = 0.

Ensuite on peut implémenter un ensemble de jump conditionnels, qui vont se servir de r15.

• je (jump if equal)
• jne (jump if not equal)
• jg (jump if greater)
• jge (jump if greater or equal)
• jl (jump if lower)
• jle (jump if lower or equal)

Il faut toujours appeler cmp avant n'importe quel saut conditionnels, pour bien mettre à jour r15.

Voici un exemple d'utilisation, si r0 est supérieur à r1 alors on incrémente r1.

set r0 5
set r1 2
cmp
jg @r0_greater_than_r1
inc r1
@r0_greater_than_r1
;; more code...

les opérations arithmétiques

On peut seulement incrémenter et décrémenter avec Click4. J'ai réécrit l'addition et la soustraction à partir de ces deux instructions.

Additionner deux nombres revient à ajouter plusieurs fois 1 (et vice versa pour la soustraction).

Ensuite pour la division et la multiplication, même système. Multiplier par X revient à ajouter plusieurs fois X.

Les algorithmes étaient un peu plus complexes alors pour me simplifier la tâche, je les ai écris et testé en python avant de les traduire en assembleur.

Voici un exemple avec l'addition de deux nombre 8-bits. J'ai crée une classe int4 pour reproduire le comportement d'un nombre 4-bits.

def add(r0, r1, r2, r3):
    while r2 > 0 or r3 > 0:
        if r3 == 0:
            r2 -= 1
        r3 -= 1
        r1 += 1
        if r1 == 0:
            r0 += 1     
    return r0, r1
    
# unit tests
assert(add(0, 0, 0, 0) == (0, 0)) # adding zero to zero
assert(add(0, 0, 0, 1) == (0, 1)) # adding 1 to zero
assert(add(0, 1, 0, 0) == (0, 1)) # adding zero to 1
assert(add(0, 1, 0, 4) == (0, 5)) # no carry
assert(add(0, 10, 0, 6) ==(1, 0)) # carry
assert(add(1, 2, 0, 3) == (1, 5)) # carry + non nul r0
assert(add(0, 3, 1, 3) == (1, 6)) # carry + non nul r2
assert(add(1, 3, 1, 2) == (2, 5)) # carry + non nul r0 and r2

J'essaye d'utiliser au maximum les opérations disponibles dans Click4. C'est pour cette raison que je ne fais que des incréments, décréments et des comparaisons à 0.

J'ai aussi fait quelques tests unitaires pour être sûr du bon fonctionnement.

Voici le add 8-bits en assembleur.

;; Add two 8-bit numbers
;; adds r2-r3 to r0-r1 into r0-r1

@8bitadd
;; while r2 > 0 or r3 > 0 {
;; or r3 r2 into r4
nand r4 r2 r2	
nand r5 r3 r3
nand r4 r4 r5
crsz r4 ;; if r2 or r3 == 0 then return
rjmp 4
jmp @end8bitadd
crsz r3 ;; if r3 underflow then dec r2 too
rjmp 1
dec r2
dec r3
inc r1
crsz r1 ;; if r1 overflow then inc r0 too
rjmp 1
inc r0
jmp @8bitadd
@end8bitadd
;; }

Meilleure gestion de l'input

J'ai rajouté une manière plus simple de gérer l'input clavier.

Click4 possède l'instruction input qui stocke l'état des touches directionnelles du clavier dans un registre donné.

C'est mieux de se le représenter en binaire.

Imaginons qu'on utilise input :

input r0

Si la touche haut est appuyée, r0 = 1 ou b0001 en binaire. Si la touche droite est appuyée, r0 = 2 ou b0010 en binaire. Si la touche haut et droite sont appuyées, r0 = 3 ou b0011 en binaire.

J'ai donc créé une opération jump_if_pressed, qui ne jump que si une certaine touche est appuyée. Voici un exemple, si la touche droite est appuyée, on incrémente r0 :

jmp_if_pressed key_right @right_pressed
jmp @right_not_pressed
@right_pressed
inc r0
@right_not_pressed
;; do stuff

Ce que j'aurai aimé ajouter

Avec plus de temps, j'aurai implémenter :

• Une stack, pour pouvoir créer des fonctions et faire des appels récursifs.
• Des array de taille fixe, pour stocker une suite de valeur.

Comment la compilation est orchestrée

En général on utilise le terme compilation pour parler du processus de transformer du code en langage machine, compréhensible par le CPU.

En réalité il y a plusieurs étapes, et la compilation est une de ces étapes.

Je me suis inspiré de ces étapes pour créer mon compilateur. L'idée est de décomposer le "compilateur" en plusieurs parties, chacune avec ses propres responsabilités.

Quelques termes à définir pour bien comprendre la suite :

• Click 4 Assembler (C4ASM) : les opérations incluses par défaut dans click 4.
• Extended Click 4 Assembler (EC4ASM) toutes les opérations et autres fonctionnalités que j'ai rajouté.
• Click 4 script (.cs4) : Un fichier écrit en EC4ASM.
• Mnemonic : le nom de l'opération, par exemple set.
• Opcode (code d'opération) : Le code qui doit être transmis au CPU pour qu'il exécute l'opération (pour set c'est 1).

Voilà comment fonctionne mon compilateur :

1. Preprocessor
   • Enlève les commentaires.
   • Remplace tout les #define avec la bonne valeur.
   • Réserve la mémoire pour la heap.
   • Transforme le script (une string) en une structure de donnée plus facile a utiliser pour les étapes suivante.
2. Compiler
   • Remplace toutes les opérations EC4ASM avec du C4ASM.
   • Enregistre les labels et les remplace avec les bonnes adresses.
   • Vérifie la validité de toutes les opérations C4ASM et de leurs arguments.
3. Assembler
   • Transforme tout le code en code machine (tout les mnemonics et keywords sont remplacés par leurs opcode).
4. Drawer
   • Dessine les opérations sur l'image.
   • Dessine les sprites sur l'image.
   • Dessine la heap sur l'image.

Et voilà le jeu final !

Je suis resté sur un jeu très simple, car même avec cet IDE, c'est très compliqué de créer un jeu. Le plus compliqué étant le déboggage, je ne pouvais me fier qu'à mes logs.

J'ai fait un clone du jeu Kaboom sur Atari 2600. Mais on y collecte des chats au lieu de bombes. J'ai choisi des chats car en dehors des notes de musique, la Click4 peut aussi jouer un son de miaulement.

Le jeu s'appelle "It's raining Cats", qui vient de l'expression, It's raining cats and dogs en anglais.

Vous pouvez voir le c4script sur mon github.

Actionnables

• Voici quelques chaînes Youtube en anglais pour en apprendre plus sur la programmation bas niveau, la stack, le heap et le fonctionnement d'un ordinateur en général.
  • Crash Course Computer Science
  • Low Level Javascript
• Faites un jeu pour la Click4 et envoyez le moi. Même en utilisant l'IDE ça reste un vrai challenge mais je suis sûr que certains d'entre vous pourront faire des trucs incroyables.
• Essayez de créer votre propre IDE et compilateur pour une autre fantasy console. Il y en a beaucoup d'autres, en voici une liste.
• Devenez membre de mon Patreon pour avoir accès à du contenu exclusif comme le code source de l'IDE, mon avancée au jour le jour au format vidéo avec pleins de détails intéressants, des jeux gratuits et pleins d'autres choses.

Resources

• Click4 IDE
• Click4 Fantasy Console

Remerciements

Merci à @josefnpat d'avoir créer ce jouet, mais aussi de m'avoir aider à comprendre son fonctionnement (il bosse sur un super jeu, allez voir!).

C'est grâce à ces personnes qui me supportent sur Patreon et Ko-fi que je peux partager ces expériences amusantes et mes connaissances. Un grand merci à : Moey Mei, Rascal, Staren, Kel Pat, Poupipnou, les Tartines, Dysphobia (aka la crapule de l'espace).