The Magic of Tries and DFS: How I Made Glyphfall Lightning Fast

While building Glyphfall.com, I ran into a classic problem. The concept is simple: a grid full of letters where players need to find words, a bit like Boggle. But under the hood, "simple" quickly turned into a performance nightmare.

The Stumbling Block: The Brute-Force Wall ​

At first I thought: "How hard can it be?" You start at a letter, check the neighbors, and see if that sequence of letters exists in your word list.

But the math caught up with me. In a 4x4 or 5x5 grid, there are tens of thousands of possible paths. If you have to search through a flat list of 200,000 words for each path, your browser freezes faster than you can say "word score." I needed a way to not check after the fact whether a word existed, but to know during the search whether a path was a dead end.

The Discovery: The Trie (Prefix Tree) ​

The solution turned out to be a Trie. Instead of a flat array of words, I built a tree structure. If I have the words "cat", "can" and "car", I store them as branches from the letter 'c'.

Building the Trie ​

This is the structure I used to make my word list searchable at lightning speed:

class TrieNode {
  constructor() {
    this.children = {}; // Stores the next letters
    this.isWord = false; // Is this a complete word?
  }
}

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;
}

The Search: DFS with Pruning ​

With the Trie in hand, I could make my Depth-First Search (DFS) algorithm smart. Instead of wandering blindly, the DFS now walks hand in hand with the Trie through the grid.

The trick is pruning: if I follow the letters "C-Z" on my board and the Trie says no word starts with "CZ", the algorithm stops searching there immediately. This saves millions of unnecessary computations.

The Search Algorithm ​

Here's how the core of Glyphfall fishes words out of the grid:

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 if we've already visited this cell
    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: If the letter isn't in the Trie, this path is a dead end
    if (!nextNode) return;

    // 3. Mark as visited
    visited[r][c] = true;
    const currentWord = path + char;

    // 4. Word found?
    if (nextNode.isWord) {
      foundWords.add(currentWord);
    }

    // 5. Search recursively in all 8 directions
    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 for other paths
    visited[r][c] = false;
  }

  // Start the search from every letter in the 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);
}

Eliminating Jank with Web Workers ​

Even with this fast algorithm, I noticed a slight stutter (jank) in the UI when the board was being generated. The CPU was so busy searching that the animations would hiccup.

The final step was moving this logic to a Web Worker. This way the heavy computation runs in a separate thread and the game experience stays smooth.

The 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);
};

The Result ​

With this approach, I turned a process that took seconds (and froze the browser) into a task of just a few milliseconds.

Why this works: ​

Glyphfall now runs smoothly on every device. The lesson? Optimization isn't just about making code faster — it's about smartly eliminating what you don't need to do.