ChunkGo : tester MyGo en recréant les seeds de Minecraft

Le point de départ, c'est MyGo : un framework tout neuf (v0.2) pour faire des apps desktop en Go avec une interface web. Je voulais le tester sur autre chose qu'un « hello world », avec un projet qui le pousse un peu : du calcul lourd côté Go, beaucoup de dessin côté page, et un gros volume de données entre les deux.

Comme sujet, j'ai pris un truc qui m'intrigue depuis longtemps : les seeds de Minecraft. On tape un mot ou un nombre à la création du monde, et ce seul nombre suffit à tout redonner : le relief, les océans, les biomes, chaque arbre. Le jeu ne stocke rien d'avance, il recalcule le terrain à partir de la seed au fur et à mesure qu'on avance, et deux joueurs qui tapent la même seed se baladent dans le même monde.

ChunkGo met ça en scène. On tape une seed, Go calcule le terrain sur tous les cœurs et l'envoie chunk par chunk à la page, qui le dessine en vue isométrique. L'article suit le chemin des données : du bruit de Perlin au relief, du relief au monde infini, du monde à l'écran. La dernière partie, c'est mon avis sur MyGo, avec deux bugs que j'ai corrigés dans le framework en passant.

CAPTURE_01 — UN MASSIF EN (318, −212), EXPORTÉ PAR L'APP

#L'app en deux mots

CAPTURE_02 — CHUNKGO

On choisit une seed (un nombre ou n'importe quel texte), on règle le bruit, et le monde se recalcule. On se déplace en glissant ou au clavier : les chunks qui entrent dans la vue sont générés à la volée, ceux qui sortent sont oubliés, et le monde n'a pas de bord. Trois vues (blocs, biomes, hauteur), un export PNG, et un bouton qui compare trois façons de faire passer les chunks de Go à la page. Ce dernier m'a appris plus sur MyGo que tout le reste.

Côté code, tout tient en quatre fichiers :

• noise.go : le bruit de Perlin, les octaves, le bruit « ridged », le hash des seeds ;
• world.go : hauteurs, biomes, arbres, chunks, cache, et World.Stream ;
• src/render.ts : le rendu isométrique d'un chunk ;
• src/main.ts : caméra, chargement des chunks, réglages.

#Pourquoi pas le hasard pur ?

Premier réflexe pour générer un terrain : tirer une hauteur au hasard pour chaque colonne. Le résultat est inutilisable. Deux colonnes voisines n'ont rien en commun, on obtient un champ de pics. Ce qu'il faut, c'est un hasard continu : imprévisible à grande échelle, mais lisse de près.

La première idée est le bruit de valeur : on ne tire des valeurs qu'aux points d'une grille, et on interpole entre eux. C'est mieux, mais la grille se devine, car tous les sommets et tous les creux tombent pile dessus.

En 1983, après avoir travaillé sur les effets de Tron, Ken Perlin a eu une meilleure idée : ne pas tirer une hauteur à chaque point de la grille, mais une pente. Ce travail lui vaudra un Oscar technique en 1997.

#Le bruit de Perlin, pas à pas

En deux dimensions, le principe reste le même. Chaque coin de la grille porte un vecteur gradient, une direction. Pour connaître la valeur du bruit en un point P :

1. on repère la cellule qui contient P, et ses 4 coins ;
2. pour chaque coin, on calcule le vecteur qui va du coin à P ;
3. on fait le produit scalaire entre ce vecteur et le gradient du coin : positif si P est « devant » le gradient, négatif s'il est derrière ;
4. on mélange les 4 valeurs, d'abord en x puis en y, avec une interpolation adoucie.

Le plus simple, c'est de le faire bouger :

En Go, c'est une vingtaine de lignes :

func (p *Perlin) Noise2(x, y float64) float64 {
	fx, fy := math.Floor(x), math.Floor(y)
	xi, yi := int(fx)&255, int(fy)&255
	x, y = x-fx, y-fy // position dans la cellule, entre 0 et 1
	u, v := fade(x), fade(y)

	// Le gradient de chaque coin vient de la table de permutation.
	aa := p.perm[int(p.perm[xi])+yi]
	ab := p.perm[int(p.perm[xi])+yi+1]
	ba := p.perm[int(p.perm[xi+1])+yi]
	bb := p.perm[int(p.perm[xi+1])+yi+1]

	return lerp(
		lerp(grad(aa, x, y), grad(ba, x-1, y), u),
		lerp(grad(ab, x, y-1), grad(bb, x-1, y-1), u),
		v,
	)
}

Trois détails comptent.

La courbe fade. Une interpolation linéaire laisse des cassures visibles aux bords des cellules. Perlin utilise d'abord 3t² − 2t³, puis, dans sa version « améliorée » de 2002, 6t⁵ − 15t⁴ + 10t³. Cette courbe a une dérivée première et une dérivée seconde nulles en 0 et en 1 : les cellules se raccordent sans pli, même dans l'éclairage, qui dépend des pentes.

La table de permutation. Pas de vrai hasard au moment du calcul : un tableau des nombres de 0 à 255, mélangé une fois, sert à associer un gradient à chaque coin. C'est là qu'intervient la seed : elle pilote ce mélange, et deux seeds donnent deux mondes différents mais tout aussi lisses.

Des gradients fixes. La version de 2002 remplace les vecteurs aléatoires par un petit jeu de directions fixes : 12 en 3D, et 8 dans ma version 2D (les axes et les diagonales). Ça suffit visuellement, et ça évite des calculs de racines. Minecraft utilise d'ailleurs une classe qui s'appelle tout simplement ImprovedNoise.

#Superposer des octaves

Un seul bruit de Perlin donne de grosses bosses régulières, toutes de la même taille : une colline, une cuvette, une colline. Un vrai paysage a des détails à toutes les échelles : des continents, des collines, des rochers. L'astuce s'appelle fBm (fractional Brownian motion). On additionne plusieurs couches de bruit, appelées octaves, chacune plus fine et moins haute que la précédente :

func (p *Perlin) FBM(x, y float64, octaves int, persistence, lacunarity float64) float64 {
	sum, amp, freq, norm := 0.0, 1.0, 1.0, 0.0
	for range octaves {
		sum += amp * p.Noise2(x*freq, y*freq)
		norm += amp
		amp *= persistence  // chaque couche pèse moins…
		freq *= lacunarity  // …et elle est plus fine
	}
	return sum / norm
}

• La lacunarité multiplie la fréquence d'une octave à l'autre, souvent par 2.
• La persistance multiplie le poids d'une octave à l'autre, souvent par 0,5.

CAPTURE_03 — UNE OCTAVE CONTRE CINQ, MÊME SEED

1 octave : des bosses molles

5 octaves et le bruit ridged : un relief crédible

#Du bruit au relief

Le bruit donne un nombre entre −1 et 1, et il faut encore en faire une hauteur de colonne. Trois étapes, toutes dans groundHeight :

1. Les continents. Le fBm est mélangé à un bruit quatre fois plus lent, qui soulève ou enfonce des régions entières. Un léger biais (+0,08) donne un peu plus de terre que de mer. Sous 0, c'est l'océan, et sa profondeur suit le bruit.

2. La redistribution. Au-dessus de 0, la hauteur est élevée à une puissance, un exposant de 1,4 par défaut. Comme la valeur est entre 0 et 1, la puissance écrase les basses terres et laisse les hauts presque intacts : des plaines larges et des collines plus marquées. Un piège m'a coûté un moment ici. Mon preset « Montagnes », avec un exposant fort, donnait le terrain le plus plat de tous : une valeur de 0,5 élevée à la puissance 2,2 ne vaut plus que 0,22. Il a fallu étirer le bruit avant de lui appliquer la puissance.

3. Les montagnes. Le fBm fait de bonnes collines, mais jamais de chaînes de montagnes : il est trop rond. La technique classique est le bruit ridged, qui somme 1 − |bruit| au lieu du bruit. Les lignes où le bruit passe par zéro deviennent des crêtes pointues :

func (p *Perlin) Ridged(x, y float64, octaves int, persistence, lacunarity float64) float64 {
	sum, amp, freq, norm := 0.0, 1.0, 1.0, 0.0
	for range octaves {
		r := 1 - math.Abs(p.Noise2(x*freq, y*freq)) // 0 devient un sommet
		sum += amp * r * r                          // au carré : crêtes plus fines
		norm += amp
		amp *= persistence
		freq *= lacunarity
	}
	return math.Max(0, (sum/norm-0.45)/0.55)
}

Appliqué partout, ça donnerait un monde entièrement montagneux. Un troisième bruit, très lent, sert donc de masque : les chaînes n'apparaissent que là où il dépasse un seuil, et seulement à l'intérieur des terres.

CAPTURE_04 — LES MONTAGNES ET LA JUNGLE

Bruit ridged sous un masque : crêtes, neige, vallées

Jungle, plage et savane en (48, −302)

#Les biomes

Le climat vient de deux autres bruits, très lents (cinq fois l'échelle du relief) : une température et une humidité. Une colonne chaude et sèche donne un désert, chaude et humide une jungle, froide et humide une taïga, et ainsi de suite. La hauteur l'emporte sur le climat : au-dessus d'un certain seuil, c'est de la roche, puis de la neige.

Ce système produisait des frontières de biomes trop parfaites, de longues courbes lisses, parce que le bruit lent est très régulier de près. La correction : un bruit rapide et faible, ajouté à la température et retiré de l'humidité, qui effiloche les bordures sans les déplacer. L'outil TestDumpMap du projet exporte 1024 × 1024 blocs vus de dessus. C'est avec lui que j'ai réglé tout ça, bien plus vite qu'en me promenant dans l'app :

CAPTURE_05 — 1024 × 1024 BLOCS VUS DE DESSUS

#Un monde infini, chunk par chunk

Tout repose sur une propriété : la hauteur d'une colonne ne dépend que de la seed et de ses coordonnées. Pas de l'ordre dans lequel on explore, pas de ce qui a été généré avant. C'est pour ça que deux joueurs avec la même seed voient le même monde. On peut donc découper le monde en chunks de 16 × 16 colonnes, comme Minecraft, et calculer n'importe lequel à n'importe quel moment, de façon indépendante :

• on n'a besoin de garder en mémoire que les chunks autour du joueur ;
• un chunk oublié puis redemandé revient identique, au bloc près ;
• les chunks se calculent en parallèle, sans se coordonner.

Le seul point délicat, ce sont les arbres. Un arbre a une couronne de 5 × 5 blocs : planté au bord d'un chunk, ses feuilles débordent sur le voisin. Si chaque chunk décidait de ses arbres tout seul, on obtiendrait des arbres coupés net à la frontière. La solution est une grille jitterée. Le monde est découpé en cellules de 5 × 5, et chaque cellule a au plus un arbre, placé à un endroit tiré de son hash. Pour se dessiner, un chunk examine les cellules qui le touchent, débordement compris, et retrouve exactement les mêmes arbres que ses voisins, sans jamais les consulter. Un test le vérifie : des feuilles doivent apparaître sur les bordures de chunks.

#Générer sur tous les cœurs

Puisque les chunks sont indépendants, Go peut les répartir sur tous les cœurs. World.Stream lance un worker par cœur, et envoie chaque chunk à la page dès qu'il est prêt, en commençant par le centre de la vue. Il passe pour cela par un Channel MyGo, le mécanisme de streaming du framework :

// Stream génère les (2·radius)² chunks autour de (cx, cz) sur tous les
// cœurs et envoie chacun dès qu'il est prêt, du centre vers l'extérieur.
func (w *World) Stream(ctx context.Context, p Params, cx, cz, radius int,
	skip []string, out *mygo.Channel[Chunk]) (StreamStats, error) {
	// … un worker par cœur, qui lit les coordonnées dans `jobs` …
	for c := range results {
		if err := out.Send(c); err != nil {
			return stats, err // la page a fermé le canal : ctx est annulé
		}
	}
	// …
}

Côté page, le client TypeScript est généré par MyGo à partir de cette signature. Je n'ai écrit que la boucle de réception :

const ch = new Channel<Chunk>();
ch.onmessage = (c) => addChunk(c.x, c.z, base64ToBytes(c.data));
const stats = await World.stream(params, cx, cz, radius, [...chunks.keys()], ch);

Quand le joueur repart avant la fin, la page ferme le canal. Côté Go, Send échoue et le contexte est annulé, ce qui arrête les workers : aucun chunk inutile n'est calculé.

#Infini… ou presque

Le bruit de Perlin classique n'est pas infini. Sa table de permutation fait 256 entrées, donc le bruit se répète toutes les 256 unités. Avec une échelle de 96 blocs par unité, le relief de base revient à l'identique tous les 24 576 blocs. La couche « continents », quatre fois plus lente, ne revient qu'au bout de 98 304 blocs. Je suis allé vérifier :

CAPTURE_06 — LE MÊME ENDROIT, À 98 304 BLOCS DE DISTANCE

(8, 8), vue hauteur

(98 312, 8), vue hauteur : même colline

(98 312, 8), vue blocs : désert et cactus

C'est ma limite préférée du projet. Les couches de bruit à des échelles différentes ont des périodes qui ne coïncident pas, si bien que le monde complet met bien plus longtemps à se répéter que chacune de ses couches. Minecraft règle le problème autrement : chaque octave y reçoit son propre décalage aléatoire. Et la vraie limite de son monde infini est venue d'ailleurs, de la précision des nombres à virgule. Avant la Beta 1.8, au-delà de 12 550 821 blocs, les calculs du bruit débordaient et le terrain se transformait en murs déchiquetés : les fameuses Far Lands.

#Le rendu isométrique

La page reçoit des octets : 8 par colonne (hauteur, bloc du dessus, biome, puis deux « étages » optionnels pour les troncs, cactus et feuillages). Elle doit en faire une image. En isométrie, chaque colonne se dessine avec trois formes : un losange pour le dessus, et deux parallélogrammes pour les faces tournées vers nous.

Il n'y a ni 3D ni tampon de profondeur, juste l'algorithme du peintre : on dessine du fond vers l'avant, et ce qui est peint après recouvre ce qui est peint avant.

Deux optimisations rendent le tout rapide :

• Un sprite par chunk. Chaque chunk est dessiné une seule fois dans son propre canvas. La vue ne fait ensuite que coller ces images dans le bon ordre, une rangée de chunks après l'autre. En se déplaçant, seuls les chunks qui entrent dans la vue sont dessinés, et jamais plus de 8 ms par image : s'il en reste, ils attendent l'image suivante.
• Des faces coupées au plus court. La face d'une colonne ne descend que jusqu'à la hauteur du voisin de devant ; le reste serait caché. Seules les colonnes du bord d'un chunk descendent jusqu'en bas. Elles forment les flancs du diorama, en couches d'herbe, de terre et de pierre, et le chunk suivant les recouvre quand il existe.

#Et MyGo, alors ?

C'était le vrai sujet du test. MyGo est un framework jeune (v0.2) qui veut être un Electron en Go : la fenêtre et le système en Go, l'interface dans la webview du système (WebView2 sous Windows), et entre les deux, des appels typés.

#Ce qui est excellent

Les bindings. On écrit une méthode Go, mygo dev génère la fonction TypeScript correspondante, avec ses types et sa documentation. Une struct Go Params devient une interface TS, un *mygo.Channel[Chunk] devient un Channel<Chunk>. Changer un paramètre côté Go casse la compilation côté front, ce qui est exactement ce qu'on veut.

La boucle de développement. Une modification Go déclenche une recompilation, la régénération des bindings et une relance de l'app, le tout en 1 à 1,5 s. Pour un générateur procédural, qu'on règle à coups de dizaines d'essais, c'est ce qui rend le travail agréable.

Le résultat. Un exécutable de 8,6 Mo et un installeur de 2,9 Mo, produits en 7 secondes une fois le cache de compilation chaud. Sur mon test précédent, une app MyGo affichait sa fenêtre en un dixième de seconde et ne consommait rien au repos.

#Les trois façons de faire passer un chunk

MyGo propose deux chemins pour envoyer des données à la page : les Channels (des messages JSON) et les protocoles personnalisés (un http.Handler Go que la page interroge avec fetch, en binaire). Sur le papier, le binaire devrait gagner haut la main. J'ai mesuré :

Le Channel gagne largement contre une requête par chunk, et le lot binaire est le plus rapide une fois le cache chaud. Ce que j'en retiens : Channel pour les flux de petits messages, protocole pour les gros blobs, et surtout pas une requête par petit objet.

#Le piège du CORS

Le premier essai du protocole chunk:// s'est soldé par un laconique « Failed to fetch ». Sous Windows, WebView2 sert les protocoles personnalisés sur http://chunk.localhost, une origine différente de la page, qui vit sur http://mygo.localhost (ou sur le serveur Vite en développement). Sans en-tête Access-Control-Allow-Origin, le navigateur refuse la réponse. La doc présente pourtant fetch sur ces protocoles comme allant de soi. Sous Linux, MyGo déclare ses protocoles « CORS-enabled » et le problème n'existe pas ; sous Windows, il faut ajouter l'en-tête soi-même. J'ai vérifié que c'était bien la cause avec un build sans en-tête, qui échoue aussi en production.

#Contribuer en chemin

En testant MyGo sur des projets précédents, j'étais tombé sur deux défauts de son backend Windows, que j'ai corrigés directement dans le framework. Chaque fois avec la même méthode : un test automatique qui reproduit le bug, qui échoue avant le correctif, qui passe après, et toute la suite de tests Windows au vert.

• Le plein écran gardait la barre de menu : PR #29, fusionnée le jour même et publiée dans la v0.2.3, celle qu'utilise ChunkGo.
• Les menus restaient clairs dans une app sombre : PR #30, en revue. Le test lit la vraie couleur des pixels de la barre de menu pendant qu'on bascule le thème.

Le piège du CORS ferait un bon troisième candidat : MyGo pourrait autoriser automatiquement l'origine de l'app sur ses propres protocoles, comme il le fait déjà sous Linux.