Suport technique et veille technologique

LinuxFr.org : les journaux  -  Nouvelles du jeu Harmonist : refonte de l'interface grâce à Gruid

 -  Février 2021 - 

Sommaire

• Harmonist v0.4.0
• Gruid
  • Architecture à la Elm
  • Le type Effect
  • Le type Grid
  • Recherche de chemins
  • Performances
  • Extensibilité
• La suite

Bonjour Nal,

Je t'écris pour te parler d'une nouvelle version du jeu roguelike d'infiltration Harmonist et de Gruid, une bibliothèque en Go que j'ai écrite pour refaire l'interface d'Harmonist. J'en ai parlé ici il y a un peu plus d'un an déjà, Harmonist est un jeu à propos d'un petit singe, nommé Syu, qui doit sauver son amie Shaedra, emprisonnée par le clan Dayoriah des Souterrains !

Harmonist v0.4.0

Cette nouvelle version d'Harmonist apporte une refonte complète de l'interface. Parmi les changements visibles, il y a :

• Une interface plus interactive : des informations sont affichées à la volée en fonction du contexte ou du mouvement de la souris, à des emplacements adéquats.
• Pour la version native avec tuiles, Tk a été abandonné au profit de SDL. SDL est plus rapide pour dessiner les tuiles et offre aussi la possibilité de faire du zoom.
• L'interaction entre l'utilisation du clavier et la souris est plus harmonieuse. Par exemple, utiliser la souris pour examiner ne passe plus le clavier en mode examination.
• Les animations maintenant s'interrompent si on envoie de nouvelles commandes avec le clavier ou la souris.
• La fonctionnalité de replay permet maintenant de naviguer plus facilement en avant et en arrière.

Les changements au niveau du gameplay sont peu nombreux, essentiellement des détails et corrections de bugs mineures, à un point important près : un nouvel algorithme de vision est utilisé. Cet algorithme est une combinaison (intersection) de deux algorithmes.

• L'algorithme précédent, qui offrait une visibilité et passabilité non binaires : par exemple les arbustes réduisent le champ de vision, mais ne le bloquent pas totalement, contrairement aux murs. Par contre, ce premier algorithme permettait de voir un peu trop bien au niveau des coins avec des murs.
• L'algorithme nommé symmetric shadow casting, qui offre des ombres expansives, tout en restant symétrique (si on voit une case depuis une autre l'inverse est aussi vrai). L'intersection de deux algorithmes symétriques étant symétrique, on obtient un nouvel algorithme qui combine les propriétés souhaitées !

Gruid

Gruid est la bibliothèque Go que j'ai écrite en vue de cette refonte de l'interface dans Harmonist. Je vais te raconter un peu comment ça marche et mon expérience avec.

C'est une bibliothèque qui reprend des idées de sources diverses :

• Une architecture inspirée de l'architecture du langage fonctionnel Elm, mais adaptée au concept de grille (plutôt que d'HTML) et à Go (moins fonctionnel, plus performant).
• Utilisation d'une grille, un peu comme les bibliothèques type curses, mais avec trois méthodes de rendu différentes : terminal, SDL2 ou navigateur (WebAssembly). Les méthodes de rendu graphique peuvent ainsi utiliser des tuiles. Dans tous les cas, on utilise la méthode classique qui consiste à redessiner uniquement les cases qui ont changé. Ça permet d'avoir de très bonnes performances, même sans accélération graphique, comme pour le terminal (même avec des tuiles).
• Une structure de données pour représenter les grilles inspirée des slices (des portions de tableaux) de Go et de la bibliothèque d'images de la bibliothèque standard.

En plus d'un package pour le rendu fondé sur les idées ci-dessus, Gruid offre des fonctionnalités typiquement utilisées pour les jeux à base de grille : des algorithmes de recherche de chemins (dont JPS), des algorithmes de génération de cartes (marches aléatoires et automates cellulaires), manipulation de pièces préfabriquées, des algorithmes de vision et une liste de priorité pour évènements.

Architecture à la Elm

Le langage utilise une boucle principale inspirée de Elm. Une application doit définir :

• Une fonction qui actualise un modèle (l'état du programme/jeu) en réponse à des messages (le plus souvent des entrées utilisateur, clavier ou souris, mais pas que).
• Une fonction qui renvoie un rendu de l'état du modèle.

Ça ressemble assez aux typiques Update/Draw qu'on retrouve dans beaucoup de frameworks de jeux, mais il y a des différences importantes :

• Update est appelée après réception de messages particuliers et non à des intervalles réguliers (le typique 60 FPS).
• Update renvoie éventuellement une commande : une fonction exécutée de façon concurrente et qui renvoie un message qui sera reçu dans un appel futur d'Update. Une telle commande peut être utilisée par exemple pour un timer (envoyer un message au bout d'un certain temps), écouter sur un socket, ou effectuer des entrées-sorties de façon concurrente en général. Ça offre une façon bien pratique et intégrée de gérer la concurrence dans l'interface utilisateur.
• Draw (appelé View dans Elm) renvoie un résultat qui est ensuite envoyé au système de rendu. Dans Elm, ça renvoie de l'HTML. Dans Gruid, ça renvoie une grille (éventuellement un sous-rectangle). D'autres possibilités existent. Par exemple une autre framework similaire et inspiré d'Elm (bubbletea), qui lui cible les applications en ligne de commande uniquement, a choisi de renvoyer des chaînes de caractères.

Dans Go, l'interface que doit satisfaire un modèle de programme est la suivante :

type Model interface {
    Update(Msg) Effect
    Draw() Grid
}

Grid est le type pour représenter les grilles et Effect est le type pour représenter les commandes. Enfin, Msg est le type des messages, qui peuvent être de toutes sortes.

Le type Effect

Pourquoi « Effect » ? Parce qu'il y a en fait deux types de fonctions qui renvoient des messages. Elles sont appelées managed effects dans Elm.

Il y a d'une part les commandes déjà mentionnées, exécutées de façon concurrente. Elles s'exécutent puis renvoient un message. Leur type est le suivant :

type Cmd func() Msg

D'autre part, on a les souscriptions : exécutées de façon concurrente également, elles envoient un nombre arbitraire de messages sur un canal.

type Sub func(ctx context.Context, chan<- Msg) Msg

Le contexte fourni sert à notifier la souscription d'arrêter son exécution, par exemple lors de la fermeture. Les souscriptions s'utilisent moins que les commandes, mais sont utiles pour les fonctions qui s'exécutent sur une longue durée et doivent notifier leur progrès, ou pour des fonctions qui s'exécutent sur toute la durée du programme : par exemple, écouter la présence de signaux (comme SIGINT ou SIGTERM), puis notifier avec un message l'Update de l'application pour lui permettre de réagir.

Elm traite les souscriptions de façon un peu différente par rapport aux commandes, mais l'idée reste similaire.

Le type Effect de gruid est représenté par une interface. Cette interface est satisfaite exactement par les deux types Cmd et Sub (la méthode n'est pas exportée). Elle joue le même rôle qu'un type somme pour les commandes et souscriptions.

Le type Grid

J'ai mine de rien mis pas mal de temps à finaliser l'API de ce type !

La représentation utilisée ressemble, à certains détails près, fortement à celle qu'on peut retrouver dans certaines bibliothèques numériques. Essentiellement, c'est un struct représentant un couple (pointeur, range):

• Le pointeur pointe vers une grille sous-jacente, représentée par un simple tableau compact (slice de Go).
• La composante range délimite le sous-rectangle avec lequel on travaille (par exemple dans le cas d'un widget).

La possibilité de travailler sur des sous-rectangles est très pratique à l'heure de programmer des widgets. La façon de créer des sous-rectangles, ainsi que le code de certaines fonctions, sont fortement inspirés de la bibliothèque image de la bibliothèque standard qui permet de facilement manipuler des rectangles et des points. Certaines optimisations sont inspirées de la bibliothèque d'images, par exemple pour remplir efficacement une sous-grille en faisant des appels astucieux à la fonction copy de Go (qui est implémentée en assembleur sous le tapis) après avoir rempli une première ligne manuellement.

L'API de la grille en soi est par contre plus proche de celle des slices en Go : on trouvera par exemple une fonction Copy qui copie une grille dans une autre (éventuellement des sous-grilles de la même grille) dont le résultat ne dépend pas de l'intersection éventuelle entre les deux grilles.

L'API a aussi quelques particularités adaptées à sa vocation de dessin : dessiner par inadvertance en dehors de la grille ne fait rien. Parce que oui, un jeu ne doit pas crasher parce qu'un widget aurait été mal placé ou dimensionné !

Par ailleurs, étant plutôt content avec ce type Grid, j'ai finalement adopté une API quasiment identique (avec des trucs en plus) pour la représentation interne des cartes. Les algorithmes de génération de cartes peuvent ainsi être configurés pour modifier uniquement un sous-rectangle de la carte au besoin.

Recherche de chemins

Gruid offre plusieurs algorithmes de recherche de chemins : A*, Dijkstra, JPS (une optimisation d'A* pour les grilles) et calculs de composantes connexes, ainsi qu'un algorithme efficace de simple parcours en largeur.

Harmonist utilise A* et JPS pour calculer des chemins, par exemple pour le joueur ou les monstres. A* est plus lent que JPS (qui est surprenamment rapide), mais plus flexible et permet de privilégier certains chemins par rapport à d'autres et donc de faire de l'IA (par exemple un monstre essaiera de contourner d'autres monstres pour attaquer le joueur). Suivant les cas, l'un ou l'autre est utilisé.

L'algorithme de Dijkstra est utilisé dans Harmonist par exemple pour la propagation du bruit. Le simple parcours en largeur est utilisé pour l'exploration automatique (il s'agit de trouver un chemin vers la zone inconnue la plus proche).

Performances

Un certain effort a été fait dans la bibliothèque pour rendre ses algorithmes efficaces. En particulier, les allocations mémoire sont réduites grâce à des caches sous le tapis quand j'ai estimé que ça valait la peine.

Par exemple, une recherche de chemins sur une carte 80x24 spécialement conçue pour être difficile donne les résultats suivants pour A* et JPS :

BenchmarkJPSPassable1-2                    44414             27329 ns/op
BenchmarkJPSPassable1NoDiags-2             43028             27867 ns/op
BenchmarkAstarPassable1-2                   2940            402059 ns/op
BenchmarkAstarPassable1NoDiags-2            4210            285463 ns/op

Une bonne partie de l'effort de calcul dans l'algorithme A* se trouve au niveau de la gestion d'une file de priorité (le plus souvent implémentée par un tas). Cette file de priorité permet de connaître la case suivante à explorer en priorité. Une mauvaise gestion pourrait conduire à des chemins qui ne seraient pas les plus courts !

Le secret de l'algorithme JPS est de tenir compte de la structure très particulière d'une grille et de faire des « sauts » orthogonaux et diagonaux astucieux et éviter ainsi d'ajouter certaines cases dans cette file de priorité. L'algorithme est particulièrement bien vulgarisé sur ce site.

Dans les cas simples, comme des chemins courts avec peu d'obstacles ou de petits obstacles (assez courant en pratique), les performances des deux algorithmes sont beaucoup plus similaires et dépassent rarement les 20μs.

Dans le benchmark ci-dessus, la carte utilisée était la suivante (pour le cas BenchmarkJPSPassable1 avec diagonales autorisées) :

Les murs sont les #. Il s'agissait de trouver un chemin d'en bas à gauche (O) vers en bas à droite (G), ce qui nécessitait de faire de gros zigzags. Les o correspondent aux points du chemin trouvé et les X correspondent aux points décisifs à partir desquels un saut a été effectué : ce sont les seuls points qui sont ajoutés à une liste de priorité de recherche. En comparaison, A* aurait rempli presque toute la carte avec des X.

Dans Harmonist, l'ensemble des calculs d'un tour (en incluant également les algorithmes de vision), se fait normalement toujours en dessous de 1ms. La génération des cartes et initialisation complète d'un niveau se font en environ 5ms (ça dépend du type de carte).

Tous ces résultats sont sur une machine plutôt vieille qui n'était déjà pas très puissante à l'époque (un Intel Celeron avec deux cœurs d'il y a quelque chose comme sept ans).

Pour les versions natives (terminal et SDL), l'intérêt des optimisations est limité : entre rapide et très rapide l'utilisateur ne verra que rarement la différence sur une machine moderne. Ça permet par contre au programmeur utilisant la bibliothèque de moins s'inquiéter des performances et ne pas être tenté de faire des optimisations prématurées. Par ailleurs, ça a permis de rendre rapide la version navigateur également ! Et puis, je me suis bien amusé :-)

Extensibilité

Gruid permet d'écrire de nouveau drivers pour des moteurs de rendu différents. Par exemple, il serait possible d'écrire un moteur de rendu qui fonctionne en mode serveur, ou un moteur de rendu qui utilise une bibliothèque graphique différente que SDL, ou une bibliothèque terminal autre que tcell. Il suffit d'implémenter l'interface Driver pour cela.

La suite

Pour la suite, j'espère utiliser gruid dans de nouveaux projets de roguelikes. J'ai quelques idées en cours, mais rien de très concret encore. La phase de design du gameplay restera sans doute toujours la plus difficile… mais intéressante !

Autrement, j'espère que ce journal encouragera certains à tenter d'écrire un roguelike ! En tout cas, j'ai perso appris beaucoup de choses en programmant des roguelikes, c'est une expérience assez variée tout en étant réalisable par une seule personne. Et puis, je trouve ça plutôt rigolo :-)

D'ailleurs, ça me fait penser : bientôt il y a le challenge 7DRL, ça peut intéresser ceux qui aiment les petites compétitions. Il s'agit, comme tous les ans, d'écrire un mini roguelike en 7 jours ! Perso, j'ai jamais participé, je trouve les deadlines un peu stressantes, mais je regarde toujours après coup ce qu'ont fait les autres : on y trouve souvent des perles (pas toujours libres, par contre).

Commentaires : voir le flux Atom ouvrir dans le navigateur

par anaseto