CasioCraft... le retour
Posté le 27/12/2024 18:59
Mon project
Bonjour à tous ! Cela fait litéralement 10 ans que je n'ai pas ouvert ce site ! C'est un plaisir de revenir !
La dernière fois j'étais au lycée et participais au concours des 10 ans du site avec CasioCraft, un petit terraria like.
Je suis passionné par la programmation sur systèmes à ressources limités et récemment je me suis repris d'intérêt pour ma Casio 35+ et je compte reprendre CasioCraft, toujours en basic vanilla, pas d'overclocking.
Dans la liste de ce que j'aimerai faire :
- affichage dense : 32x12 cases, 3x3 pixels par bloc avec 1 pixel d'écart entre les bloc
- au moins 16 blocs distincts
- toute combinaison de 3x3 pixels affichable pour un bloc
- "texture pack" modifiable
- système de visibilité : les cases qui n'ont aucun coté en contact avec de l'air sont cachées
- chargement d'écran "rapide" : si possible en moins de 10s (mon premier CasioCraft pouvait prendre entre 20 et 30s)
- système d'inventaire "avancé" : barre active, inventaire, craft, coffre, loot...
- monde "vaste" : je vise un minimum de 128x64 ou un système dynamique par chunk qui permettrait des mondes de forme arbitraire
- génération "intéressante" : j'aimerai expérimenté avec des bruits à plusieurs octaves, probablement avec une base de perlin modifié, mais il faut alors s'attendre à une génération initiale de la map de plusieurs minutes
Précision pour l'affichage, une fois un écran chargé, seul le joueur et les blocs cassés/posés seront mis à jour pour un rendu intéractif. Mais le joueur pourra recentrer l'écran sur lui à volonté et c'est ce chargement qui devrait durer une dizaine de secondes.
Je m'excuse par avance, cet article va être long et technique ! Il nécessite de bonne connaissance en binaire et en multiplication matricielle. J'espère qu'il sera intéressant à lire et potentiellement inspirant.
Pour le moment je me concentre sur le stockage et l'affichage. Pour stocker de vaste monde sans exploser la capacité limité de mémoire de la 35+ il parait évident que je vais devoir compresser la donnée. Pour afficher un écran rapidement et "jouer" dedans il est fort probable que j'utilise une autre représentation décompressée. Pour avoir un temps de chargement limité la transformation entre les 2 représentations doit être très efficace. Si vous avez des idées géniales je suis preneur !
Stockage
De mon côté j'explore la piste du "binary packing". Tous les nombres (entiers ou floatants non imaginaires) de la 35+ sont représentés sur 12 octets (96 bits). Je n'ai pas fait de recherche sur la représentation interne de ces nombres, mais empiriquement les entiers de 0 à ~2^33 (0b100100010000001011111000111111111 pour être exacte) sont considérés "non floatants" et supportent donc les opérations "strictement entières" comme MOD. Malgré cela, les entiers se comportent comme attendu jusqu'à 2^43 environ, passé ce point, les additions et soustractions perdent en précision et les derniers bits peuvent être tronqués. Etonnemment, d'autres opérations marchent correctement jusqu'à 2^47 environ. J'imagine que c'est un format propriaitaire avec 48 bits de mantisse et des bits de metadata pour des optimisations spécifiques à la casio. En tout cas ce n'est pas IEEE 754.
Malheureusement la 35+ n'a pas d'opérations binaires (and/or/xor/shift) sur les nombres, pour extraire le Nième bit d'un nombre X il faut donc utiliser des opérations algébriques :
- MOD(X int÷ 2^N, 2) : fonctionne jusqu'à 2^33 environ
- int(2 frac(X÷2^(N+1)) : fonctionne jusqu'à 2^47 environ
Si vous connaissez une méthode encore plus efficace pour packer et extraire des bits, je suis preneur ! 47 bits sur 96 ce n'est pas un très bon ratio.
Je pense qu'un bloc peut être représenté par 5 bits : 4 pour le type (16 bloc différents) et 1 pour la visibilité (pour éviter de revisiter ses voisins à chaque chargement). Une première approche serait de packer 6 ou 9 blocs dans un seul entier utilisant 30 ou 45 bits (compatible avec la première ou deuxième méthode de décodage respectivement).
Je peux ensuite stocker ses nombres dans une matrice (compressant les lignes ou les colonnes), ou dans une liste en utilisant la deuxième méthode : 128x64/9 ≈ 911 < 999. De façon consécutive ou désordonné par chunk (avec une autre table de metadata pour les retrouver). Une compression RLE (Run Length Encoding) pourrait grandement diviser la mémoire nécessaire, au prix d'une décompression beaucoup plus longue.
Decompression
J'avoue que cette partie me parait particulièrement complexe.
Pour ce qui suit, considérons que le blocs sont "simplement packés" et stockés dans une matrice compressée par ligne. Si un entier stock 6 blocs, 7 entiers doivent être récupérés pour former une ligne de 32 blocs (6x7 = 42, 10 blocs sont inutilement décodés). De même pour :
- 9 blocs par entier : 5 entiers à récupérer, 13 blocs décodés inutilement
- 8 blocs par entier : 5 entiers à récupérer, 8 blocs décodés inutilement
Ce n'est pas optimal pour le stockage, mais 8 blocs par entier semble un bon compromis. J'utiliserai donc cette valeur à partir de maintenant, mais rapelez vous que rien n'est définitif sur la façon dont la donnée est compressée et stockée.
Je ne me rapelé pas que le basic casio était aussi lent, simplement itérer sur chaque bloc d'un écran prend 7s !
For 1→J To 12 // Y
For 1→I To 5 // X
Mat[I, J]→C // entier compressé
For 1→K To 8 // sub X
Int(32Frac(C÷32^K))→D // bloc décompressé
Next
Next
C'est bien entendu sans compter le temps de traitement de chaque bloc, qui consiste certainement à :
- stocker sa valeur dans une matrice décompressée (ou un format optimisé pour l'affichage)
- tester/séparer sa visibilité de son type
- afficher le bloc en fonction de sa visibilité et de son type
Une méthode
potentiellement plus efficace (plus rapide, mais peut être plus dur à utiliser ensuite) consiste à utiliser les capacités vectorielles de la casio. Voici le code (une explication suit) :
Seq(1÷32^N,N,1,8,1)→List 1
Trn List→Mat(1)→Mat B
{60,8}→Dim Mat C // matrice décompressée, chaque cellule représente un bloc, au lieu d'être 12x32, elle contient les blocs inutiles 12x40 = 12x5x8 = 60x8
60→Dim List 1 // liste de tous les entiers compressés d'un écran
For 1→J To 12 // Y
For 1→I To 5 // X
Mat A[I, J]→List 1[12I+J-12]
Next
Next
// Décompression vectorielle !
Int(32Frac List→Mat(1)Mat B)→Mat C
Ce code prend seulement 2s ! Mais le résultat est plus difficilement exploitable, c'est une matrice de 60x8, pratique pour tester les collisions, casser/placer des blocs (avec un simple changement d'index 32x12→60x8), mais je ne vois pas de façon efficace pour faire l'affichage.
Rapide explication de cet algo avec une version simplifiée du problème, considérons que List 1 contiennent 3 nombres (A, B et C) et que l'on veut obtenir leur représentation binaire sur 3 bits. La matrice B contient l'inverse des puissances de 2 de 1 à 3 (chaque entier de List 1 contient 3 "groupes" de 1 bit).
List 1 = {A, B, C}
List→Mat(1)Mat B =
┌ ┐ ┌ ┐
│A│ │A/8, A/4, A/2│
│B│[1/8, 1/4, 1/2] = │B/8, B/4, B/2│
│C│ │C/8, C/4, C/2│
└ ┘ └ ┘
Il ne reste plus qu'à appliquer la formule Int(2Frac(X)) à chaque élément, ce que la casio permet de faire "d'un coup" :
List 1 = {1, 3, 6}
┌ ┐
│0, 0, 1│
Int(2Frac(List→Mat(1)Mat B)) = │0, 1, 1│
│1, 0, 1│
└ ┘
Dans l'algo de décompression List 1 contient tous les blocs à décompresser, Mat B les puissance de 32 de 1 à 8 (entier contient 8 groupes de 5 bits).
Affichage
Mon premier CasioCraft utilisait une commande Text pour chaque bloc, ce qui n'est pas efficace du tout. Une deuxième version (non publiée) utilisait un Text par ligne (en utilisant les String), ce qui est beaucoup plus efficace du moment que l'on peut construire les Strings rapidement (ce qui n'est pas chose facile suivant l'algo de décompression utilisé). Un désavantage de cette technique est que les blocs affichables sont restreints aux caractères affichable par Text. La palette est toute fois relativement étoffée mais loin de pouvoir représenter toutes les combinaisons de 3x3 pixels.
Une deuxième approche est le DrawStat. Encore faut-il trouver une façon efficace de dessiner 32x12 cases de 3x3 pixels où chaque case peut avoir un paterne différent. Je pense avoir trouvé une façon intéressante, mais difficile à exploiter. Elle utilise 5 listes :
- List 1 : coordonnées X des points "actifs"
- List 2 : coordonnées Y des points "actifs"
- List 3 : coordonnées complexes X+iY de tous les blocs visibles (non air et non cachés)
- List 4 : liste des "bitmap" de chaque bloc visible (un entier de 0 à 2^9-1)
- List 5 : liste temporaire
Voici un code pour initialiser les listes avec des paternes aléatoire, juste pour tester :
// je remplis seulement 10x12 blocs, il est peu probable que les 32x12 blocs soient tous visibles en même temps
0→K
For 0→J To 12
For 0→I To 10
K+1→K
4I+4Ji→List 3[K] // coordonnées X+Yi
RanInt#(0,511)→List 4[K] // random bitmap
Next
Next
Et le code pour dessiner :
S-Grph1 DrawOn,Scatter,List 1,List 2,Dot
BG-Pict 1
0→K
// itère les 3x3 pixels de chaque bloc
For 0→J To 2
For 0→I To 2
K+1→K
// extrait le Kième bit de chaque bitmap (0 ou 1) et multiplie leur position
Int(2Frac(List 4÷2^K))List 3→List 5
ReP List 5→List 1 // coordonnées X
ImP List 5→List 2 // coordonnées Y
ViewWindow -I,126-I,1,-J,62-J,1 // 127x63 pixels, origine décallée par I et J
DrawStat
StoPict 1
Next
Next
Ce code dessine une liste de blocs en 9 DrawStat en suivant une liste de bitmap. Pour toute itération (I, J) List 5 contient une liste de cooronnées :
- 0+0i si le bloc correspondant n'a pas de pixel dans sa bitmap à la position [I, J]
- X+Yi si non, où X et Y sont les coordonnées du bloc correspondant
Chaque DrawStat dessine donc tous les pixels [I, J] de tous les blocs qui ont ce pixel dans leur bitmap, et un pixel en (0, 0) pour tous les blocs qui n'ont pas le pixel [I, J] dans leur bitmap.
Cette méthode prend 10s pour afficher 120 blocs (et grandit linéairement avec le nombre de blocs à afficher). Ce qui n'est pas trop mal. Encore faudrait-il avoir un moyen efficace de décompresser le format de stockage dans ce format spécifique.
A noter que le format compressé proposé est suffisamment simple pour permettre les accessions nécessaires pour les tests de collisions et casser/poser des blocs. Décompressé "un écran" dans un format "à plat" n'est pas strictement nécessaire. La seule décompression nécessaire est vers un format optimisé pour l'affichage.
J'ai fait quelques tests avec le super DrawStat/Graph(X,Y) mais aucun résultats conluants.
Conclusion
En résumé beaucoup d'ambition, des techniques intéressantes (je trouve), mais pas énormément de résultats. L'utilisation des capacités vectorielles de la casio me semble essentielle pour parvenir à des temps de chargement raisonable. Encore désolé pour le pavé ! Si vous avez des pistes, des informations sur le format binaire, des idées pour le stockage/decompression/dessin, ou des remarques je serais très content de les lire !
Citer : Posté le 05/01/2025 21:41 | # |
Fichier joint
Voilà un g1m avec 3 programmes :
- T-GEN2 : remplit Mat A 32x32 avec un pattern qui ressemble à un monde et permet de tester différentes palettes
- T-STR : fait le rendu du monde stocké dans Mat A avec Text+Str (31x12)
- T-STAT : fait le rendu de 10x12 bitmaps 3x3 aléatoires avec DrawStat
T-GEN2 doit être lancé au moins une fois avant d'utiliser T-STR.
Si vous avez des remarques ou recommandations, je suis très intéressé, je reprends juste le Basic Casio et je suis un peu rouillé.
Citer : Posté le 06/01/2025 11:33 | #
I love the use of the little 4's for the leaves
lvl 2 is soo much faster
should be 4, not 5
as 4 * 8 = 32
will speed it up
You can remove the closing brackets without much problem
and if you go [SHIFT]+[4] (CATLOG)
goto ALL and near the bottom (just press up to go to the bottom) there is List1 to List6
they are one character smaller and saves 1byte
compared to List 1 to List 20
(List 1[5] * 8) + 2 -> X
can become
2 + 8List1[5 -> X
and you can use List Ans
just be careful as C.Basic reuses List Ans with Mat Ans
place '#CBCPLX at the top of the program to enable complex numbers in C.Basic
make sure to set S-Gph2 DrawOff and S-Gph3 DrawOff
mine were already on and gave me Complex Number In List Error
prob could combine G = 5,6,7 into one line with StrMid()
Citer : Posté le 06/01/2025 12:25 | #
La boucle de 1 à 5 est intentionelle. Dans le cas où le viewport est décallé en X par un nombre non multiple de 8, 4 chunks ne sont pas suffisant pour couvrir une ligne de 31 blocs. Par exemple pour un décallage de 3, les colonnes 3 à 34 sont visibles, mais 4 chunks couvrent les colonnes 1 à 32. De façon général, pour N colonnes par écran, et M blocs par chunk, il faut décoder ceil(N/M)+1 chunks. Sinon j'imagine que je pourrais forcer le décallage X sur le multiple de 8 le plus proche, ça devrait être une limitation acceptable pour le joueur. Je vais assez rapidement ajouter un joueur pour tester l'interaction avec le monde et le feeling de recentrer l'écran.
Oui le niveau 2 est extrémement rapide, ça évite le décodage de 8 blocs complétement. Pour l'instant j'ai configurer une palette pour l'air, les feuilles et les blocs cachés, ça devrait grandement accélérer l'affichage du "ciel", des forêts et des sous-terrains. Je peux encore ajouter une palette, mais je ne pense pas qu'elle sera suffisamment utilisée. Oui je vais passer à un StrMid pour le niveau 2, et les Str du niveau 1 et 2 seront générées à partir de Str3 (palette 0), ça permettra de centraliser les textures.
Que penses tu du niveau 1 ? Je suis partagé entre la complexité de la formule, les contraintes que ça impose sur les blocs id et le gain de perf minime.
Je ne connaissais pas List1 à List6, je vais les utiliser, merci.
Hate d'ajouter un joueur est commencer l'edition du monde. J'espère que get/set le monde compressé sera assez rapide. De même pour la partie graphique, j'espère que dessiner/effacer et révéler les blocs cachés sera assez fluide.
Citer : Posté le 09/01/2025 00:22 | #
C'est un peu décevant, mais de tous les tests que j'ai fait il ressort que :
- avoir une représentation décompressée d'un écran accélère les get/set pour le gameplay, mais implique une décompression et recompression
- utiliser une mutliplication de matrice n'accélère pas la décompression car on perd trop de temp à extraire la matrice intermédiaire
- construire les listes nécessaires à drawstat est lent
- drawstat et graph(X,Y) sont lents pour afficher beaucoup de points (ils sont plus optimisés pour dessiner des lignes)
- utiliser des palettes arbitraires accélère modestement l'affichage mais rend le test de visibilité d'un bloc lent
- utiliser la version compressé du monde est trop lent si lest de visibilité d'un bloc est lent
Je pense que je vais un peu abandonner l'idée d'avoir un chargement d'écran "rapide" (passer la barre de 10s à 20s) et de chercher des techniques farfelues pour y parvenir. Il semble que ce qui impacte vraiment positivement le temps de chargement soit :
- un algo simple : éviter un maximum les conditions/instructions dans les boucles
- décompresser peu de chunks par ligne
- décoder les chunks de façon vectorielle (avec une multiplication de liste)
- utiliser Text+Str, éviter drawstat à tout prix
- utiliser des palettes de 1 bloc (si suffisamment de metadata par chunk)
- utiliser des palettes de 4+ blocs (si elles n'empêchent pas de tester la visibilité d'un bloc facilement)
J'aimerais passer au gameplay rapidement. Il ne reste plus que l'encodage à choisir. Je vois 3 possibilités :
- base 32 : utilisée jusqu'à maintenant, offre des chunks de 8 blocs avec 1 bit de metadata
- base 100 : chunks de 7 blocs, 10 valeurs de metadata possibles (mais étrangement instable), opérations avec puissances de 10 plus rapides, mais palettes multibloc impossibles
- base 25 : chunks de 10 blocs, 3 valeurs de metadata possibles (semble stable), base peu commune mais plus efficace que la base 32 (représentée en base 10)
Niveau utilisation du stockage, la base 25 est un peu juste (je pense avoir besoin d'au moins 23 blocs), 32 est confortable, 100 est beaucoup trop grand, les 2/3 des ids ne seront pas assignés, ce qui fait que je peux stocker 3 blocs de moins par chunk comparé à la base 25. Un bloc pèse 1.2 bytes en base 25, 1.5 bytes en base 32 et ~1.7 bytes en base 100.
Niveau compacité de l'information, 10 nombres en base 25 stockent ~46.4 bits d'information (10ln(25)/ln(2)), 8 nombres en base 32 stockent 40 bits et 7 nombres en base 100 stockent ~46.5 bits. En comptant les metadata, un chunk en base 25 stock ~48 bits, un chunk en base 32 stock 41 bits et un chunk en base 100 stock ~50 bits (correpondant au maximum d'information stockable par les 15 nombres en base 10 de la mantisse).
Je pense que je vais coder un rapide proto avec affichage, edition collision des blocs en base 25 et continuer la dessus si tout marche bien.
Par rapport à la "stabilité" des metadata en base 100, j'ai l'impression que la calculatrice tronque les entiers si il y a 13 0 entre 2 chiffres significatifs :
- Frac (400000000000002÷100) renvoie 0
- Frac (400000000000012÷100) renvoie 0.12
Si cet état (qui tronque) est accessible depuis le jeu ça fera beaucoup penser aux bugs qui permettent de détruire la bedrock sur Minecraft.
Citer : Posté le 10/01/2025 23:58 | # |
Fichier joint
Nouveau g1m avec 3 programmes (à éxecuter dans cet ordre) :
- T-GEN25 : initialise un monde ultra simple au nouveau format base 25
- T-STR25 : nouvel afficheur simpliste
- T-PLY25 : permet de "jouer" dans un monde
L'afficheur est lent (16 secondes pour un écran) et sans palettes, j'y reviendrais surement plus tard.
Le "jeu" implémente les collisions (pour une hitbox de 1x1 pas encore 1x2 comme l'originel), ainsi que le minage de bloc.
Casser un bloc est lent, mais la fonctionnalité est "complète" :
- "world bounds" et "screen bounds" checks
- efface le bloc à l'écran
- supprime le bloc de la map compressée
- affiche les blocs cachés adjacents
- modifie le bit de visibilité des blocs adjacents
Pour éviter la frustration de se demander si on a bien appuyé sur la touche parce que rien ne se passe à l'écran, une barre s'affiche sous le joueur dès que le minage commence. Casser un bloc prend entre 1.3 et 2.3 secondes, si ça vous parle, c'est en gros le temps qu'il faut dans Minecraft pour casser une buche avec une hache en bois (1.5s) ou à la main (3s).
Pour l'affichage du joueur, j'expérimente avec Text et DrawStat (vous pouvez switch en assignant 0 ou 1 à θ). Je pense que DrawStat est plus intéressant, la vitesse est similaire à Text (pour une dizaine de points), j'ai l'impression que ça "flicker" moins et il permet plus de détails, notamment d'orienter le joueur dans la direction de déplacement. Attention je test les "world bounds" mais pas les "screen bounds", donc en mode Text ça péte !
Pour l'instant je suis content du passage à la base 25, je peux stocker des maps 25% plus grande dans le même espace, je n'ai pas rencontré de problème de précision, et la décomposition en facteurs premiers de 25 joue particulièrement bien avec un système de palette (donnant 2 palettes de 5 blocs).
Merci Lephe pour la technique d'utiliser RclPict pour la transparence ! Ca ma permis de régler mon problème d'effacer un espace de 4x4 pixels avec un Text de 4x5.
Si vous y jouez j'aimerai particulièrement votre retour sur le "feeling" du jeu :
- vitesse de déplacement du joueur
- changement de direction (droite/gauche) du joueur (en mode DrawStat)
- minage des blocs (temps d'attente, visuels...)
- affichage des blocs cachés
Prochaines étapes :
- collisions 1x2
- gravité et saut
- poser des blocs
- recentrer la camera
Malheuresement, je ne pense pas que poser un bloc "cachera" les blocs adjacents. Casser un bloc génère 4 checks pour révéler les blocs cachés adjacents (et c'est déjà long), poser un bloc générerait 12 checks pour cacher les blocs adjacents...
Citer : Posté le 12/01/2025 09:14 | #
Movement is fast
xD I like the hidden sprite
my calc seems to be like 5-10% faster
display was 14.5sec
if you want to speed up movement
I would recommend to tighten the loop around it
I normally have 2 loops
one small one for movement; with an exit condition for non-movement
and the larger main-game loop that goes around it
I think I like the player changing directions without moving
it would make more sense if you had a single button that mines the block in the direction of the player
maybe change the order of clearing blocks?
clear the blocks above and below the player first before clearing the player (and the left/right blocks)
I like the random small dashes and long dashes
tho its not 100% evident that they are hidden blocks
at first it almost looked like sand to me
maybe more random textures?
there are different height dashes
a lot of work goes into mining a block
it already seems fast enough
and even slightly more with Cls
the line was a good idea
you can use Cls with BG-Pict instead of RclPict in some places
it's faster because they don't update the display contents (only VRAM)
will help remove the flicker as well
Text 4Y - 3, 4X + 3, Str 3
StoPict 2
Cls
Text 4Y - 2, 4X + 3, Str 3
RclPict 2
There is also StrLeft() and StrRight() for when StrMid() is overkill
make sure to set [SHIFT]+[MENU] ⇒ (S-Win) ⇒ S-WinMan
otherwise DrawStat will go everywhere
and clear the background BG-None
you can use Horizontal and Vertical instead of fullscreen F-Line's
Isz X is faster than X + 1 and Dsz X, X - 1
be careful as if X = 0, then the next instruction is **NOT** run
just make sure the next instruction isn't needed if Isz is run
should put LpWhile T≠47 at the end
so [EXIT] exits the program
maybe you want to have a look at https://en.wikipedia.org/wiki/De_Bruijn_sequence
instead of numbers, it can be with strings
have a small palette string that contains all possible 2 char combinations in the shortest sequence possible
eg AABBA contains all 2 char combinations AA, AB, BB and BA
Citer : Posté le 12/01/2025 20:54 | #
Thanks a lot for the review and great suggestions! (haha you found it
I will try to implement all this.
But I'm not sure I can really change the order of clearing blocks. The current order is (with your "Cls instead of RclPict 1" suggestion):
- Cls (removes player)
- delete center blocks + right and left (if needed) with Text, this also deletes the top pixels of the line below (because Text is 5 pixels tall and blocks are 4 pixels appart)
- StoPict 2
- Cls (removes Text, so reveals center block + right and left)
- delete center block + right and left (if needed), but this time delete the bottom pixels of the line above
- RclPict 2, this restores the bottom pixels
- delete the block above and below (if needed), since I know the center block is empty, the Text is offset so that it deletes pixels from this block
- DrawStat the revealed blocks
If I delete the top and bottom block before the player, then clear screen would reveal the top and bottom bloc again. And if I StoPict 1 before Cls, then the player would become part of the background. Or did you meant something else entirely?
Ha and the random dashes are a mistake, I used long hyphens to debug iron ores. I intend all hidden blocks to use the short one (in fact I would really like to use a single centered pixel, but I cannot find a character that renders like that). In T-Str25 palette 0 holds all the textures of the 25 block ids. Blocks 0 to 17 are "revealed" (9 and 17 are unassigned), 18 to 24 are hidden version of the range 3 to 9.
I will work on a MVP when I have time next week.