Implémentation d’un raycaster en Bash

 (github.com/izabera)
2 points par GN⁺ 2024-12-22 | 1 commentaires | Partager sur WhatsApp
  • Raycaster implémenté en Bash : une démo pseudo-3D dans le terminal où l’on tourne et se déplace avec les touches fléchées, et où l’on quitte avec q
  • L’implémentation est en grande partie un port du tutoriel de raycasting de Lode Vandevenne, et toutes les opérations mathématiques sont effectuées en entiers avec un facteur d’échelle de 64K, sans virgule flottante
  • La plus grande contrainte est la performance de Bash : si l’on exécute une commande pour chaque pixel, ou si l’on conserve l’état de l’écran dans des tableaux ou des chaînes, il devient difficile d’afficher dans le temps imparti pour chaque frame
  • Pour l’affichage dans le terminal, le projet utilise le caractère Unicode half block ainsi que des couleurs 24 bits en premier plan et arrière-plan, ce qui double en pratique la résolution verticale, mais impose de connaître également la couleur des pixels adjacents
  • Dans la feuille de route actuelle, fluid movement, decent framerate, parallel rendering, kitty keyboard protocol et un prototype initial de sound sont terminés, tandis que textures, sprites, enemies, particles, multiplayer et d’autres éléments ne sont pas encore achevés

Raycaster de terminal créé en Bash

  • Ce projet est un raycaster qui fonctionne en Bash et rend une vue pseudo-3D dans le terminal
  • Les commandes permettent de tourner et de se déplacer avec les touches fléchées, et de quitter avec q
  • Davantage de captures d’écran et de vidéos sont disponibles dans l’album Imgur
  • L’implémentation est en grande partie un port du tutoriel de raycasting de Lode Vandevenne

Contraintes qui ont rendu l’implémentation difficile

  • Le principal problème est que Bash est lent
    • L’auteur indique qu’il est difficile d’obtenir un frame rate acceptable même s’il ne faut exécuter qu’une seule commande par pixel
    • Même en conservant l’état de l’écran dans un tableau de couleurs, l’accès arbitraire à un élément du tableau est en temps linéaire, ce qui pose problème
    • Même en stockant l’état de l’écran dans une seule longue chaîne, l’accès au n-ième caractère reste en temps linéaire, y compris avec LANG=C, si bien que la simple lecture nécessaire pour l’afficher peut prendre plus de temps qu’une frame entière
  • Bash ne prend pas en charge les nombres à virgule flottante ni l’accès à une bibliothèque de fonctions mathématiques
    • Tous les calculs sont effectués en entiers
    • Les valeurs entières sont calculées avec un facteur d’échelle de 64K
  • Dans un terminal, utiliser un caractère comme s’il s’agissait d’un pixel ne donne pas un rendu très satisfaisant, d’où l’usage du caractère Unicode half block
    • En définissant différemment la couleur de premier plan et la couleur d’arrière-plan, la résolution verticale est en pratique doublée
    • Il n’existe aucun moyen de ne mettre à jour qu’une seule des deux couleurs dans une cellule
    • Il n’existe pas non plus de moyen d’interroger la couleur actuelle d’une cellule, et dans Bash ce type d’interrogation serait de toute façon beaucoup trop lent
    • Il faut donc connaître la couleur des pixels adjacents à chaque écriture d’un pixel

Problèmes de terminal et d’entrées/sorties

  • Avec un langage lent comme Bash, rafraîchir tout le terminal en une seule fois n’est pas simple
  • La plupart des terminaux ne sont pas conçus pour les jeux vidéo et ne permettent donc pas de tester l’état exact des touches actuellement enfoncées
    • En général, on ne peut récupérer que l’entrée d’une seule touche maintenue
    • La répétition des entrées est lente, soumise à du debounce, et la limite d’entrée continue est faible, ce qui peut aboutir à seulement 5 à 6 caractères par seconde
    • Il est aussi difficile de récupérer plusieurs touches simultanées hors modificateurs
    • L’auteur indique que le kitty keyboard protocol résout ce problème
  • Remplir le terminal de couleurs nécessite beaucoup de données
    • Avec la taille de police habituelle de l’auteur, cela représente environ 10 Mo/s d’E/S
  • Bash n’utilise pas un seul syscall pour afficher une chaîne contenant plusieurs retours à la ligne
    • Ce projet n’affiche donc pas \n et déplace le curseur autrement

FAQ et conditions d’exécution

  • Si le redimensionnement de la fenêtre casse l’affichage, si le scintillement est important, ou si le rendu est mauvais dans certains terminaux, l’auteur demande d’ouvrir une issue
  • Si le CPU chauffe fortement ou si un vieil ordinateur ralentit, il est conseillé de réduire la résolution ou de définir la variable d’environnement FPS à une valeur inférieure à 30
    • Il est indiqué que Microsoft Defender dégrade fortement les performances, et il est suggéré de le désactiver
  • Il est précisé que cela ne fonctionne pas avec Bash antérieur à 5.2
  • Le code n’est pas entièrement en Bash pur
    • Au démarrage, stty est appelé une fois pour désactiver l’echo
    • À la sortie, stty est appelé une fois pour réactiver l’echo
    • Après la fin de l’exécution, certaines statistiques sont collectées avec d’autres outils

État de la feuille de route

  • Éléments terminés

    • semi-accurate pseudo 3d

      • fluid movement
      • decent framerate
      • parallel rendering
      • 24 bit colours
      • kitty keyboard protocol
      • framerate-independent speed
      • sound, mais il ne s’agit encore que d’un prototype très précoce
      • dynamic wall colours
      • dynamic map, qui n’est pour l’instant pas modifiée par des événements mais est techniquement dynamique
      • basic animations effects for walls
      • basic on-screen minimap
      • Éléments non terminés

    • mouse support

      • textures
      • sprites
      • objects/enemies
      • particles
      • better perf
      • multiplayer

À lire aussi

1 commentaires

 
GN⁺ 2024-12-22
Commentaires Hacker News
  • C’est vraiment excellent. Je me demandais comment le dessin était fait sans appeler echo une fois par pixel, et la méthode est très astucieuse.
    Comme le jeu n’est pas de la « vraie » 3D, il suffit de lancer le ray tracing une seule fois par colonne, puis de dessiner seulement quelques lignes correspondant au ciel, à l’herbe et aux objets réels.
    En gros, le script envoie au terminal, via répétition de chaîne, une chaîne du type « dessiner ce pixel puis descendre d’une case », autant de fois que nécessaire.
    Ce n’est pas pour Bash, mais j’envisageais de créer un moteur de rendu voxel dans un autre environnement aux ressources de calcul limitées ; je suis sûr de pouvoir y trouver quelque chose d’utile.
  • Si vous vous demandiez s’il existe un ray caster écrit en MS Batch, il y a aussi ceci : https://github.com/nTh0rn/batch-raycaster
  • Dommage que stty nécessite un fork. Le prochain projet consistera peut-être à appeler l’ioctl nécessaire avec Bash et rowhammer, sans fork.
  • Je ne pensais pas qu’une telle chose était possible en Bash. Il m’est déjà arrivé de penser que je maîtrisais Bash à un niveau assez avancé, mais là, c’est vraiment impressionnant.
    Je n’ai pas le niveau en maths pour comprendre l’implémentation, mais rien que la regarder est un plaisir.
  • Mes scripts Bash font 300 lignes rien que pour parser toutes sortes d’options de ligne de commande, alors qu’en fait ils auraient pu afficher un jeu comme celui-ci à la place :-P
  • Je n’arrive toujours pas à comprendre pourquoi on reste coincés avec des shells aussi absurdement lents. C’est de la pure folie.
    Je comprends que certaines applis aient besoin de toutes sortes de comportements étranges de vt100, mais probablement 90 % des applis ne font qu’écrire sur la sortie standard et l’erreur standard.
    On devrait pouvoir afficher du texte à l’écran plus rapidement et mettre les 10 % restants dans un mode de compatibilité, non ?
    • Les shells sont lents, surtout Bash, mais je ne vois pas très bien comment la suite de l’argument s’enchaîne. Le shell n’intervient absolument pas dans l’interprétation des séquences d’échappement du terminal, et les terminaux modernes sont plutôt rapides.
      Même dans un terminal de 350 colonnes, on peut rendre une animation, et compte tenu des contraintes, le résultat est très fluide.
      De plus, le post part justement du principe que Bash n’est pas un langage adapté au ray casting. C’est un peu comme implémenter un tri à bulles en CSS.
      Rien n’empêche de « mettre les 10 % restants en mode de compatibilité ». Il suffit de vérifier que la chaîne ne contient que des caractères normaux et d’emprunter le chemin rapide.
      Le problème, c’est qu’en rendu logiciel de texte, il n’existe pas vraiment de chemin rapide. Il faut quand même gérer des choses comme les ligatures.
  • « bash est lent. »
    C’est l’une des raisons pour lesquelles je n’utilise pas Bash pour le scripting. Je ne l’utilise pas non plus en interactif.
    Certaines distributions Linux populaires évitent même Bash comme shell de scripting.
  • Ce serait bien de combiner ça avec l’implémentation de ps sans fork de l’auteur pour obtenir quasiment une implémentation de psDoom sans fork.
    Blague à part, c’est vraiment superbe.
  • Bien sûr, il faut aussi mentionner honorablement le ray caster en awk d’il y a 9 ans : https://github.com/TheMozg/awk-raycaster/tree/master