De magie van Tries en DFS: Hoe ik Glyphfall razendsnel maakte

Tijdens het bouwen van Glyphfall.com liep ik tegen een klassiek probleem aan. Het concept is simpel: een raster vol letters waarin spelers woorden moeten vinden, een beetje zoals Boggle. Maar onder de motorkap bleek "simpel" al snel een performance-nachtmerrie.

Het struikelblok: De brute-force muur ​

In het begin dacht ik: "Hoe moeilijk kan het zijn?" Je start bij een letter, checkt de buren, en kijkt of die reeks letters in je woordenlijst staat.

Maar de wiskunde haalde me in. In een raster van 4x4 of 5x5 zijn er tienduizenden mogelijke paden. Als je voor elk pad moet gaan zoeken in een platte lijst van 200.000 woorden, bevriest je browser sneller dan je "woordwaarde" kunt zeggen. Ik had een manier nodig om niet achteraf te checken of een woord bestond, maar om tijdens het zoeken al te weten of een pad doodliep.

De ontdekking: De Trie (Prefix Tree) ​

De oplossing bleek een Trie te zijn. In plaats van een platte array met woorden, bouwde ik een boomstructuur. Als ik de woorden "kat", "kan" en "kar" heb, sla ik ze op als vertakkingen van de letter 'k'.

De Trie Bouwen ​

Dit is de structuur die ik gebruikte om mijn woordenlijst razendsnel doorzoekbaar te maken:

class TrieNode {
  constructor() {
    this.children = {}; // Slaat de volgende letters op
    this.isWord = false; // Is dit een voltooid woord?
  }
}

function buildTrie(dictionary) {
  const root = new TrieNode();

  for (const word of dictionary) {
    let node = root;
    for (const char of word) {
      if (!node.children[char]) {
        node.children[char] = new TrieNode();
      }
      node = node.children[char];
    }
    node.isWord = true;
  }
  return root;
}

De zoektocht: DFS met "Pruning" ​

Met de Trie in de hand kon ik mijn Depth-First Search (DFS) algoritme slim maken. In plaats van blind rond te dwalen, loopt de DFS nu hand in hand met de Trie door het raster.

De truc is pruning (snoeien): als ik op mijn bord de letters "K-O" volg en de Trie zegt dat er geen enkel woord begint met "KO", dan stopt het algoritme daar direct met zoeken. Dit bespaart miljoenen overbodige berekeningen.

Het zoek-algoritme ​

Hier is hoe de kern van Glyphfall de woorden uit het raster vist:

function findWords(board, trie) {
  const foundWords = new Set();
  const rows = board.length;
  const cols = board[0].length;

  function dfs(r, c, node, path, visited) {
    // 1. Boundary checks & check of we deze cel al hebben gehad
    if (r < 0 || c < 0 || r >= rows || c >= cols || visited[r][c]) return;

    const char = board[r][c];
    const nextNode = node.children[char];

    // 2. PRUNING: Als de letter niet in de Trie zit, loopt dit pad dood
    if (!nextNode) return;

    // 3. Markeer als bezocht
    visited[r][c] = true;
    const currentWord = path + char;

    // 4. Woord gevonden?
    if (nextNode.isWord) {
      foundWords.add(currentWord);
    }

    // 5. Zoek recursief in alle 8 richtingen
    for (let dr = -1; dr <= 1; dr++) {
      for (let dc = -1; dc <= 1; dc++) {
        if (dr !== 0 || dc !== 0) {
          dfs(r + dr, c + dc, nextNode, currentWord, visited);
        }
      }
    }

    // 6. Backtracking: reset visited voor andere paden
    visited[r][c] = false;
  }

  // Start de zoektocht vanaf elke letter in het grid
  const visited = Array.from({ length: rows }, () => Array(cols).fill(false));
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      dfs(r, c, trie, "", visited);
    }
  }

  return Array.from(foundWords);
}

De "Jank" elimineren met Web Workers ​

Zelfs met dit snelle algoritme merkte ik een kleine hapering (jank) in de UI wanneer het bord werd gegenereerd. De CPU was zo druk met zoeken dat de animaties even stotterden.

De laatste stap was het verplaatsen van deze logica naar een Web Worker. Hierdoor draait het zware rekenwerk in een aparte thread en blijft de game-ervaring vloeiend.

De Worker (worker.js) ​

import { buildTrie, findWords } from './logic.js';

self.onmessage = (e) => {
  const { board, dictionary } = e.data;
  const trie = buildTrie(dictionary);
  const results = findWords(board, trie);

  self.postMessage(results);
};

Het Resultaat ​

Door deze aanpak veranderde ik een proces dat seconden duurde (en de browser liet vastlopen) in een taak van slechts een paar milliseconden.

Waarom dit werkt: ​

Inmiddels draait Glyphfall soepel op elk device. De les? Optimalisatie gaat niet alleen over code sneller maken, maar vooral over slim wegstrepen wat je niet hoeft te doen.