- City In A Bottle est une démo JavaScript qui condense un moteur de raycasting et un générateur de ville dans 256 octets de HTML
- L’exécution démarre avec seulement un
<canvas> et onclick=setInterval(...), et redessine la scène à chaque frame sur un canvas large de 99 pixels
- Le rendu est effectué sans fonctions trigonométriques, uniquement avec de l’algèbre de base et des opérations bit à bit, en traçant pour chaque pixel un rayon caméra et un rayon dans la direction de la lumière afin de produire des ombres
- La forme de la ville est répartie entre hauteur des bâtiments, routes et espaces vides à partir des coordonnées
X, Y, Z et de conditions comme X/9^Z/8, X%99, Z>32
- La luminosité finale mélange brouillard de distance, ombres et texture
(X&Y&Z)%3/Z dans la largeur de fillRect, ce qui permet de restituer ville, perspective et texture avec un code extrêmement compact
Structure complète dans 256 octets de HTML
- La démo ne fonctionne pas comme un simple fragment JavaScript, mais comme un programme HTML valide à part entière
<canvas style=width:99% id=c onclick=setInterval('for(c.width=w=99,++t,i=6e3;i--;c.getContext`2d`.fillRect(i%w,i/w|0,1-d*Z/w+s,1))for(a=i%w/50-1,s=b=1-i/4e3,X=t,Y=Z=d=1;++Z<w&(Y<6-(32<Z&27<X%w&&X/9^Z/8)* 8%46||d|(s=(X&Y&Z)%3/Z,a=b=1,d=Z/w));Y-=b)X+=a',t=9)>
- L’ensemble se divise en code HTML, boucle de rafraîchissement par frame, système de rendu, moteur de raycasting et logique de génération de ville
- Au lieu d’utiliser de la trigonométrie ou des maths avancées, il n’emploie que de l’algèbre de base et des opérations bit à bit
- Après sa publication initiale, il est resté pendant environ deux ans l’un des posts les plus populaires de la timeline Twitter de son auteur
HTML et boucle d’exécution
- Le HTML se compose uniquement d’un canvas et d’un événement au clic
<canvas style=width:99% id=c onclick=setInterval('',t=9)>
- L’
id du canvas est défini à c pour y accéder plus brièvement en JavaScript
style=width:99% n’est pas indispensable et le programme fonctionne aussi sans- Dans
onclick, un appel à setInterval démarre la boucle de mise à jour
- l’intervalle est fixé à
9 millisecondes
- la variable de temps
t est également initialisée à 9 ici pour économiser de la place
- Il existe un petit bug : cliquer plusieurs fois sur le canvas lance plusieurs intervalles, ce qui ralentit l’exécution
Version JavaScript développée pour être lisible
- La charge utile JavaScript exécutée après le clic fait 199 octets
for(c.width=w=99,++t,i=6e3;i--;c.getContext`2d`.fillRect(i%w,i/w|0,1-d*Z/w+s,1))for(a=i%w/50-1,s=b=1-i/4e3,X=t,Y=Z=d=1;++Z<w&(Y<6-(32<Z&27<X%w&&X/9^Z/8)* 8%46||d|(s=(X&Y&Z)%3/Z,a=b=1,d=Z/w));Y-=b)X+=a
- En ajoutant des espaces et des retours à la ligne, on peut le lire ainsi
c.width = w = 99
++t
for (i = 6e3; i--;)
{
a = i%w/50 - 1
s = b = 1 - i/4e3
X = t
Y = Z = d = 1
for(; ++Z<w &
(Y < 6 - (32<Z & 27<X%w && X/9^Z/8)*8%46 ||
d | (s = (X&Y&Z)%3/Z, a = b = 1, d = Z/w));)
{
X += a
Y -= b
}
c.getContext`2d`.fillRect(i%w, i/w|0, 1 - d*Z/w + s, 1)
}
c.width = w = 99 efface le canvas, règle sa largeur à 99 pixels et stocke la même valeur dans w pour la réutiliser- La hauteur par défaut du canvas est 150, et la zone inférieure reste vide
++t incrémente la valeur de temps à chaque frame, ce qui anime la scènefor (i = 6e3; i--;) est la boucle externe qui détermine la luminosité pixel par pixel
Calcul des rayons caméra
- Chaque pixel est traité comme un rayon émis depuis la caméra
- La composante horizontale est stockée dans
a
a = i % w / 50 - 1
i % w donne la position horizontale du pixel courant, puis la division par 50 et la soustraction de 1 la normalisent approximativement entre -1 et 1- La composante verticale est stockée dans
b, et la même valeur est aussi mise dans s pour le fondu de fond
b = s = 1 - i / 4e3
- Au lieu de calculer un ratio vertical exact, le code simplifie avec
i / 4e3 afin de réduire la taille du programme
- Cette simplification introduit une inclinaison presque imperceptible, mais économise des octets
4e3 a été choisi pour placer l’horizon plus bas que le centre- La position initiale de la caméra utilise la valeur du temps, ce qui crée une scène se déplaçant vers la droite
X = t
Y = Z = d = 1
Y, Z et d, utilisé pour le brouillard de distance, sont tous initialisés à 1
Génération de la ville et détection de collision
- La boucle interne est le cœur du système de raycasting : elle fait progresser
Z vers l’avant jusqu’à toucher quelque chose
for(; ++Z<w &
Z augmente tant qu’il reste inférieur à w, c’est-à-dire 99- Les bâtiments, ruelles et espaces vides côté mer de la ville sont produits par la condition suivante
Y < 6 - (32<Z & 27<X%w && X/9^Z/8)*8%46
- Elle vérifie si le rayon est plus bas que la hauteur à cette position afin de déterminer une collision
6 - abaisse le résultat de hauteur sous le centre et inverse l’orientation pour placer le sol vers le bas- Les conditions entre parenthèses déterminent la forme de la ville
32<Z laisse un espace entre la caméra et la première rangée de bâtiments27<X%w crée des vides périodiques qui séparent les blocs urbains comme des routes- pour les valeurs négatives, l’expression est toujours fausse, ce qui crée une zone vide semblable à une mer
X/9^Z/8 emploie un XOR bit à bit pour produire une répartition pseudo-aléatoire des hauteurs de bâtiments- les divisions par
9 et 8 contrôlent la largeur et la profondeur des bâtiments
X/9 s’aligne avec les valeurs liées à la largeur des routes en restant divisible par 9, ce qui évite l’apparition de bâtiments extrêmement fins sur les bords
- Le résultat entre parenthèses est multiplié par
8, puis réduit modulo 46 pour fixer la hauteur maximale
8 et 46 ont été choisis empiriquement pour produire une bonne variété de hauteurs de bâtiments
Ombres, texture et brouillard de distance
- Quand une collision se produit, la même boucle interne prend un second rôle et effectue le test dans la direction de la lumière
d | (s = (X&Y&Z)%3/Z, a = b = 1, d = Z/w)
d | sert à distinguer si le rayon courant est un rayon partant de la caméra ou un rayon vérifiant les ombres dans la direction de la lumière- Au départ,
d = 1, donc il fonctionne comme rayon caméra
- Après collision,
d = Z/w devient une valeur inférieure à 1, le résultat de l’évaluation bit à bit OR change, la boucle s’exécute à nouveau et le test d’ombre commence
- Si une nouvelle collision survient pendant ce test d’ombre, la boucle s’arrête et le pixel est dessiné comme une ombre
- La valeur de texture
s est générée par la formule suivante
s = (X&Y&Z)%3/Z
- En appliquant un ET bit à bit à
X, Y et Z, puis un modulo 3, on obtient une texture grise ressemblant à des fenêtres
- La division finale par
Z atténue la texture à mesure qu’elle s’éloigne
a et b sont tous deux fixés à 1 pour envoyer le rayon dans la direction d’une lumière directionnelle de type soleild = Z/w représente le brouillard de distance et sert à éclaircir les bâtiments lointains
Dessin des pixels et expression de la luminosité
- Chaque pixel est dessiné avec
fillRect
c.getContext`2d`.fillRect(i%w, i/w|0, 1 - d*Z/w + s, 1)
i%w produit la coordonnée x et i/w|0 la coordonnée y- La luminosité est exprimée en réduisant la largeur du pixel, une astuce essentielle pour produire une image en niveaux de gris avec très peu de code
1 correspond à un pixel noir ; l’expression finale soustrait donc une valeur à 1 pour obtenir la luminosité de l’imaged * Z/w combine les effets d’ombre et de distance
- hors ombre, le rayon parcourt la distance maximale
w, donc Z/w vaut 1
- dans l’ombre,
Z reste inférieur à w, ce qui assombrit davantage l’image
- plus l’objet bloquant la lumière est proche, plus l’ombre est sombre, ce qui produit un effet proche de l’ambient occlusion
- Enfin,
s est ajouté pour mêler la texture des bâtiments à la luminosité finale
Démonstrations ultérieures et outils d’expérimentation
- Le projet a été présenté à la Revision 2022 demo party et peut être consulté sur Pouet
- À l’époque, il avait été soumis dans la mauvaise catégorie, ce qui l’a empêché d’atteindre un classement élevé
- Par la suite, Xor et d’autres codeurs ont recréé la version JavaScript sous forme de shader 256 octets sur Shadertoy
- Daniel Darabos a créé un outil Observable permettant de manipuler en temps réel plusieurs éléments du programme
- Le code peut être remixé sur Dwitter et expérimenté aussi dans CapJS
1 commentaires
Avis sur Hacker News
Génération procédurale dans le jeu 8 bits des débuts Elite : https://procedural-generation.tumblr.com/post/112509130817/e...
Article général sur la génération procédurale : https://en.wikipedia.org/wiki/Procedural_generation
Un concept un peu lié existe aussi dans les langages de programmation fonctionnelle : l’évaluation paresseuse : https://en.wikipedia.org/wiki/Lazy_evaluation
Si un algorithme de lancer de rayons n’évalue que les points visibles lorsqu’il produit une image 2D à partir de données 3D, cela ressemble au concept d’évaluation paresseuse, qui consiste à « retarder l’évaluation d’une expression jusqu’à ce que sa valeur soit nécessaire » : https://en.wikipedia.org/wiki/Ray_tracing_(graphics)
En allant plus loin, on a même l’impression que cela se rattache vaguement à l’idée que « l’observation fait s’effondrer la fonction d’onde » : https://en.wikipedia.org/wiki/Wave_function_collapse
Cela dit, cette œuvre est plus impressionnante parce qu’elle a été faite en JavaScript. JavaScript a en général une densité de code souvent moins bonne que le code machine x86 16 bits
Le code source est également inclus
http://www.youtube.com/watch?v=36BPql6Nl_U
Son nom vient de la fractale éponge de Menger sur laquelle il est basé : https://en.wikipedia.org/wiki/Menger_sponge
Le gros avantage de JavaScript ici, c’est que la bibliothèque dweet standard fournit des fonctions comme sin/cos/fill/line. À l’inverse, le BIOS x86 ne fait guère plus que le « changement de mode », après quoi il faut simplement manipuler directement le tableau de pixels
Du coup, je me dis que les grands modèles de langage ne sont peut-être pas la meilleure façon de modéliser le monde
Personnellement, je serais déjà satisfait si j’arrivais à faire ça en environ 256 lignes, et en réalité il me faudrait probablement beaucoup plus
Les choses visuelles, qu’elles soient artificielles ou naturelles, suivent souvent des motifs. Sinon, on aurait du mal à les reconnaître au départ. Il y a donc beaucoup de choses exploitables mathématiquement. Pour les textures de hauteur, on peut utiliser différents types de bruit ou de motifs ; les fractales peuvent aussi être exploitées de façon intéressante ; pour la végétation et les arbres, on peut utiliser Fibonacci/le nombre d’or ; entre les éléments squelettiques et les os, des rapports de taille, etc. Pour cela, pas besoin d’une machine à deviner magique
Ce sont des programmes de la taille d’un tweet pour la console virtuelle Pico-8