Labyrinthe — Génération multi-langage

Implémentation de l'algorithme de Kruskal randomisé pour générer des labyrinthes parfaits, portée en Go, Zig, Rust et TypeScript (Bun).

---

Table des matières

1. Qu'est-ce qu'un labyrinthe parfait ?
2. Représentation en mémoire
3. Union-Find — la structure clé
4. Algorithme de Kruskal randomisé
5. Algorithme de Prim randomisé
6. Optimisations mémoire
7. Implémentation Go
8. Implémentation Zig
9. Implémentation Rust
10. Implémentation TypeScript (Bun)
11. Benchmarks
12. Lancer le projet

---

1. Qu'est-ce qu'un labyrinthe parfait ?

Un labyrinthe parfait respecte deux règles :

• Connexe : il existe un chemin entre n'importe quelle paire de cellules.
• Sans cycle : ce chemin est unique — pas de boucle possible.

Autrement dit, un labyrinthe parfait est un arbre couvrant du graphe de la grille.

┌───┬───┬───┬───┬───┐
│           │       │
│   ───┐   ─┘   ─┐  │
│       │       │   │
│   ┌───┘   ┌───┘   │
│   │               │
└───┴───┴───┴───┴───┘

  ✓ Parfait : une seule solution entre chaque paire de points

---

2. Représentation en mémoire

La grille

Une grille m × n a :

• (m+1) × n murs horizontaux (murH) — les plafonds/planchers
• m × (n+1) murs verticaux (murV) — les côtés

     murH[0][0]  murH[0][1]  murH[0][2]
        ↓           ↓           ↓
  ┌─────┬─────┬─────┐
  │     │     │     │  ← murV[0][0..3]
  ├─────┼─────┼─────┤
  │     │     │     │  ← murV[1][0..3]
  ├─────┼─────┼─────┤
  │     │     │     │  ← murV[2][0..3]
  └─────┴─────┴─────┘
     murH[3][0]  ...

Convention : bit = 0 → mur fermé, bit = 1 → passage ouvert

Compression en bits

Au lieu de stocker true/false par booléen (1 octet), on pack 8 murs par octet :

index :  0  1  2  3  4  5  6  7    8  9 ...
         ┌──┬──┬──┬──┬──┬──┬──┬──┐ ┌──┬──
octet 0  │0 │1 │0 │1 │1 │0 │0 │1 │ │0 │1 ...
         └──┴──┴──┴──┴──┴──┴──┴──┘ └──┴──
            ↑ mur ouvert

ouvrirMur(arr, idx):
    arr[idx >> 3] |= 1 << (idx & 7)
    └── octet      └── bit dans l'octet

Gain : 8× moins de RAM → meilleure utilisation du cache CPU.

---

3. Union-Find — la structure clé

L'Union-Find (ou Disjoint Set Union) permet de savoir si deux cellules sont déjà connectées en temps quasi-constant.

Principe de base

Au départ, chaque cellule est son propre groupe :

Cellules :  0    1    2    3    4
parent   : [-1] [-1] [-1] [-1] [-1]
            ↑ racine (valeur négative = taille du groupe)

Union par taille

Quand on fusionne les groupes de 0 et 1 :

Avant :          Après :
  0    1            0
 [-1] [-1]         [-2]
                    |
                    1  (parent[1] = 0)
                   [-1→0]

Le groupe le plus petit est attaché sous le plus grand → l'arbre reste plat.

Path Halving (compression de chemin)

Lors d'un find(x), on fait sauter chaque nœud vers son grand-parent :

Avant find(4) :      Après find(4) :

    0                    0
    |                   /|\
    1                  1  3  4
    |
    2
    |
    3
    |
    4

Résultat : les appels suivants sont quasi O(1).

Encodage avec valeurs négatives

parent[x] < 0  →  x est une racine, |parent[x]| = taille du groupe
parent[x] >= 0 →  x pointe vers son parent

Cela évite un tableau rang[] séparé → moitié moins de mémoire.

// Go
func find(parent []int32, x int32) int32 {
    for parent[x] >= 0 {
        if parent[parent[x]] >= 0 {
            parent[x] = parent[parent[x]] // saute vers le grand-parent
        }
        x = parent[x]
    }
    return x
}

---

4. Algorithme de Kruskal randomisé

C'est l'adaptation de l'algorithme de Kruskal (arbre couvrant minimal) où les poids des arêtes sont aléatoires.

Étapes

1. Lister tous les murs intérieurs
2. Mélanger aléatoirement (Fisher-Yates)
3. Pour chaque mur :
   ├─ Les deux cellules sont dans le même groupe ? → ignorer (évite les cycles)
   └─ Sinon → ouvrir le mur + fusionner les groupes
4. Arrêter quand m×n−1 murs sont ouverts

Visualisation pas à pas (grille 3×3)

Départ : 9 cellules, toutes isolées

[0][1][2]        Murs mélangés (exemple) :
[3][4][5]   →   mur(1,2) → mur(3,4) → mur(0,1) → mur(4,5) → ...
[6][7][8]

Étape 1 : ouvrir mur entre 1 et 2
┌──┬──┬──┐    groupes : {0} {1,2} {3} {4} {5} {6} {7} {8}
│  │     │
├──┼──┼──┤
│  │  │  │
├──┼──┼──┤
│  │  │  │
└──┴──┴──┘

Étape 2 : ouvrir mur entre 3 et 4
┌──┬──┬──┐    groupes : {0} {1,2} {3,4} {5} {6} {7} {8}
│  │     │
├──┼──┼──┤
│     │  │
├──┼──┼──┤
│  │  │  │
└──┴──┴──┘

... après m×n−1 = 8 ouvertures :

┌──┬──┬──┐    Un seul groupe {0..8}
│        │    → labyrinthe parfait !
├──┐  ┌──┤
│  │  │  │
├──┴──┤  │
│        │
└──┴──┴──┘

Encodage compact des murs

Au lieu d'un struct {i1, j1, i2, j2} (32 octets), on encode en 1 entier 32 bits :

code = (i * n + j) * 2 + direction

direction 0 → mur à droite  : sépare (i,j) et (i, j+1)
direction 1 → mur en bas    : sépare (i,j) et (i+1, j)

Décodage :
  dir  = code & 1
  cell = code >> 1
  i1   = cell / n
  j1   = cell % n
  i2   = (dir==1) ? i1+1 : i1
  j2   = (dir==0) ? j1+1 : j1

Gain : 8× moins de RAM pour la liste des murs.

---

5. Algorithme de Prim randomisé

Alternative à Kruskal, orientée frontière plutôt que liste globale.

Différence clé

	Kruskal	Prim
Liste initiale	Tous les murs (O(m×n))	Vide
Mémoire	O(m×n)	O(périmètre région visitée)
Croissance	Globale	Locale depuis une cellule

Étapes

1. Marquer la cellule (0,0) comme visitée
2. Ajouter ses 4 murs dans la frontière
3. Tant que la frontière n'est pas vide :
   ├─ Tirer un mur au hasard (swap avec le dernier → O(1))
   ├─ Les deux cellules visitées ? → ignorer
   └─ Sinon → ouvrir le mur, marquer la nouvelle cellule,
              ajouter ses murs à la frontière

Visualisation

Étape 1 :          Étape 2 :          Étape 3 :
┌──┬──┬──┐         ┌──┬──┬──┐         ┌──┬──┬──┐
│▓ │  │  │         │▓    │  │         │▓    │  │
├──┼──┼──┤    →    ├──┼──┼──┤    →    ├──┬──┼──┤
│  │  │  │         │  │  │  │         │▓ │  │  │
├──┼──┼──┤         ├──┼──┼──┤         ├──┼──┼──┤
│  │  │  │         │  │  │  │         │  │  │  │
└──┴──┴──┘         └──┴──┴──┘         └──┴──┴──┘
▓ = visité         frontière = {→, ↓}  frontière grandit

---

6. Optimisations mémoire

Vue d'ensemble des structures de données

                    Go (optimisé)    Zig          Rust         TypeScript
─────────────────────────────────────────────────────────────────────────
murs (walls)        []int32          []u32        Vec<i32>     Int32Array
                    4B/mur           4B/mur       4B/mur       4B/mur

parent (UF)         []int32          []i32        Vec<i32>     —
                    4B/cellule       4B/cellule   4B/cellule

murH/murV           []uint8 (bits)   []u8 (bits)  Vec<u8>      Uint8Array
                    1 bit/mur        1 bit/mur    1 bit/mur    1 bit/mur

Pour une grille 10 000 × 10 000

Cellules    : 100 000 000
Murs int.   : ~200 000 000

parent[]    :  100 000 000 × 4B  =  381 MB
murs[]      :  200 000 000 × 4B  =  762 MB  (temporaire)
murH+murV   :  ~200 000 000 bits =   24 MB

Total approx: ~1.2 GB RAM

---

7. Implémentation Go

Points notables

Compression de bits :

func ouvrirMur(arr []uint8, idx int) {
    arr[idx>>3] |= 1 << uint(idx&7)
}
//      ↑ octet       ↑ bit dans l'octet

Union-Find avec valeurs négatives (pas de tableau rang séparé) :

func find(parent []int32, x int32) int32 {
    for parent[x] >= 0 {           // >= 0 → pas une racine
        if parent[parent[x]] >= 0 {
            parent[x] = parent[parent[x]] // path halving
        }
        x = parent[x]
    }
    return x
}

func union(parent []int32, x, y int32) bool {
    rx, ry := find(parent, x), find(parent, y)
    if rx == ry { return false }
    if parent[rx] > parent[ry] { rx, ry = ry, rx } // plus négatif = plus grand
    parent[rx] += parent[ry]  // absorber la taille
    parent[ry] = rx           // relier
    return true
}

Encodage compact :

murs = append(murs, (i*n+j)*2)    // mur à droite
murs = append(murs, (i*n+j)*2+1)  // mur en bas

Shuffle Fisher-Yates via math/rand/v2 :

rand.Shuffle(len(murs), func(a, b int) {
    murs[a], murs[b] = murs[b], murs[a]
})

---

8. Implémentation Zig

Points notables

Pas de GC, allocateur explicite :

const parent = try allocator.alloc(i32, g.m * g.n);
defer allocator.free(parent);

ArrayList en mode unmanaged (0.16+) — l'allocateur est passé à chaque opération :

var murs = try std.ArrayList(u32).initCapacity(allocator, 2 * g.m * g.n);
defer murs.deinit(allocator);
try murs.append(allocator, code);

Shuffle :

rng.shuffleWithIndex(u32, murs.items, usize);

Temps via std.c.clock_gettime (std.time simplifié en 0.16) :

fn nowMs() i64 {
    var ts: std.c.timespec = undefined;
    _ = std.c.clock_gettime(std.c.CLOCK.MONOTONIC, &ts);
    return @as(i64, ts.sec) * 1000 + @divTrunc(ts.nsec, 1_000_000);
}

Compilation optimisée :

zig build-exe -O ReleaseFast main.zig

---

9. Implémentation Rust

Points notables

Pas de dépendance externe — RNG xorshift intégré :

struct Rng(u64);
impl Rng {
    fn next(&mut self) -> u64 {
        self.0 ^= self.0 << 13;
        self.0 ^= self.0 >> 7;
        self.0 ^= self.0 << 17;
        self.0
    }
}

Ownership sans GC — Rust garantit l'absence de fuite mémoire à la compilation :

let mut parent = vec![-1i32; taille]; // libéré automatiquement en fin de scope
let mut murs: Vec<i32> = Vec::with_capacity(2 * taille);

Compilation optimisée :

rustc -O -o main_rs main.rs

L'option -O active les optimisations LLVM (équivalent à -O2).

---

10. Implémentation TypeScript (Bun)

Points notables

Typed Arrays = pas de GC sur les données critiques :

const parent = new Int32Array(taille).fill(-1);  // mémoire contiguë, pas de GC
const murs   = new Int32Array(2 * taille);        // idem
const murH   = new Uint8Array(...);               // bits compressés

Les TypedArray sont alloués en dehors du tas JS → le GC ne les scanne pas → performance proche du natif.

Shuffle Fisher-Yates inline :

function shuffle(arr: Int32Array): void {
    for (let i = arr.length - 1; i > 0; i--) {
        const j = Math.floor(Math.random() * (i + 1));
        const t = arr[i]; arr[i] = arr[j]; arr[j] = t;
    }
}

Timing avec performance.now() :

const debut = performance.now();
// ...
const duree = performance.now() - debut; // en millisecondes (flottant)

Exécution :

bun run main.ts

Bun compile TypeScript à la volée sans tsc — zéro configuration.

---

11. Benchmarks

Grille 10 000 × 10 000 (100 millions de cellules) sur Apple Silicon M-series.

┌──────────────────────┬──────────┬──────────────────────────────────┐
│ Langage              │  Temps   │ Notes                            │
├──────────────────────┼──────────┼──────────────────────────────────┤
│ 🥇 Rust              │   9.63s  │ LLVM -O2, RNG xorshift           │
│ 🥈 Zig               │  12.04s  │ ReleaseFast, backend LLVM        │
│ 🥉 Bun (TypeScript)  │  14.71s  │ JSC JIT + TypedArray             │
│ 4  Go                │  16.75s  │ math/rand/v2, GC minimal         │
└──────────────────────┴──────────┴──────────────────────────────────┘

Pourquoi Rust gagne ?

• Même backend LLVM que Zig, mais auto-vectorisation plus agressive sur ce workload.
• Ownership garantit qu'il n'y a pas d'aliasing → le compilateur peut optimiser plus librement.

Pourquoi Bun bat Go ?

• Les TypedArray JS sont hors du tas GC → aucune pause de collecte.
• Le JIT de JavaScriptCore (moteur de Bun) reconnaît les patterns sur Int32Array et génère du code natif efficace.

---

12. Lancer le projet

Prérequis

Outil	Installation
Go	https://go.dev/dl
Zig	brew install zig
Rust	curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh
Bun	brew install bun

Commandes

make all    # lance les 4 langages
make go     # Go seulement
make zig    # Zig seulement
make rust   # Rust seulement
make ts     # Bun/TypeScript seulement
make clean  # supprime les binaires compilés

Changer la taille de la grille

Modifier la constante en haut de chaque fichier :

Fichier	Constante
main.go	lignes = 10000 / colonnes = 10000
main.zig	lignes: usize = 10000 / colonnes: usize = 10000
main.rs	LIGNES: usize = 10_000 / COLONNES: usize = 10_000
main.ts	LIGNES = 10_000 / COLONNES = 10_000