path: root/js/wordsearch.js

// @ts-check
/**
 * @typedef {object} GridPoint
 * @property {number} row
 * @property {number} col
 */

/**
 * @typedef {object} Cell
 * @property {number} row
 * @property {number} col
 * @property {string} letter
 */

/**
 * @typedef {object} GameSettings
 * @property {Direction[]} directions - The allowed word placement directions (e.g., 'RIGHT', 'DOWN', 'DIAG_RIGHT', 'DIAG_LEFT').
 * @property {number} gridSize - The size of the game grid (e.g., 15 for a 15x15 grid).
 * @property {number} cellSize - The size of each cell in pixels.
 * @property {number} minCanvasWidth - The minimum width of the canvas in pixels.
 * @property {number} canvasViewportGutter - The minimum distance in pixels between the canvas and the viewport edge.
 * @property {string[]} words - The list of words to be placed in the grid.
 * @property {number} fontWeight - The font weight for the letters (e.g., 600).
 * @property {number} fontSize - The font size for the letters in pixels.
 * @property {string} fontFamily - The font family for the letters (e.g., 'system-ui, -apple-system, sans-serif').
 * @property {object} colors - An object defining the color scheme for the game.
 * @property {string} colors.cell - The background color of unselected cells.
 * @property {string} colors.selectedCell - The background color of currently selected cells.
 * @property {string} colors.foundCell - The background color of cells that are part of found words.
 * @property {string} colors.stroke - The color of the grid lines.
 * @property {string} colors.focusStroke - The color of the focus indicator around the current cursor cell when the canvas is focused.
 * @property {string} colors.text - The color of the letters in the cells.
 * @property {boolean} debug - If true, empty cells will be rendered as blank instead of filled with random letters, which can help with debugging word placement.
 */

const DIRECTIONS = {
  RIGHT: [0, 1],
  DOWN: [1, 0],
  DIAG_RIGHT: [1, 1],
  DIAG_LEFT: [1, -1],
};

/**
 * @typedef {keyof typeof DIRECTIONS} Direction
 */

class Linguist {
  /**
   * Normalizes a word for grid placement.
   *
   * The normalization process includes:
   * 1. Unicode normalization (NFKD) to decompose characters into their base forms.
   * 2. Removal of diacritical marks (accents).
   * 3. Removal of whitespace characters.
   * 4. Conversion to uppercase.
   *
   * @param {string} word
   * @returns {string}
   */
  static normalize(word) {
    return word
      .normalize('NFKD')
      .replace(/[\u0300-\u036f]/g, '')
      .replace(/\s+/g, '')
      .toUpperCase();
  }

  /**
   * Detects the Unicode range for different languages.
   *
   * @param {string} firstLetter
   * @returns {[number, number]} A tuple containing the lower and upper bounds of the Unicode range for the detected language.
   */
  static detectLanguageRange(firstLetter) {
    if (!firstLetter) {
      return [65, 90];
    }

    const code = firstLetter.charCodeAt(0);

    // Latin
    // See: https://www.unicode.org/charts/PDF/U0000.pdf
    // See: https://www.unicode.org/charts/PDF/U0080.pdf
    if (code >= 0x0000 && code <= 0x00ff) {
      return [65, 90];
    }

    // Cyrillic
    // See: https://www.unicode.org/charts/PDF/U0400.pdf
    if (code >= 0x0400 && code <= 0x04ff) {
      return [1040, 1071];
    }

    // Hebrew
    // See: https://unicode.org/charts/PDF/U0590.pdf
    if (code >= 0x0590 && code <= 0x05ff) {
      return [1488, 1514];
    }

    // Arabic
    // See: https://www.unicode.org/charts/PDF/U0600.pdf
    if (code >= 0x0600 && code <= 0x06ff) {
      return [1569, 1610];
    }

    // Hiragana
    // See: https://www.unicode.org/charts/PDF/U3040.pdf
    if (code >= 0x3040 && code <= 0x309f) {
      return [12353, 12438];
    }

    // Katakana
    // See: https://www.unicode.org/charts/PDF/U30A0.pdf
    if (code >= 0x30a0 && code <= 0x30ff) {
      return [12449, 12538];
    }

    // CJK Unified Ideographs
    // See: https://www.unicode.org/charts/PDF/U4E00.pdf
    if (code >= 0x4e00 && code <= 0x9fff) {
      return [19968, 40959];
    }

    // Latin
    return [65, 90];
  }
}

class Random {
  /**
   * @param {number} min
   * @param {number} max
   * @returns {number} A random integer in [min, max].
   */
  static integer(min, max) {
    return Math.floor(Math.random() * (max - min + 1)) + min;
  }
}

class State {
  /**
   * The game grid represented as a 2D array of cells.
   *
   * @type {Cell[][]}
   */
  grid = [];

  /**
   * The currently selected cells during an active selection.
   *
   * @type {GridPoint[]}
   */
  selection = [];

  /**
    * A set of numeric cell keys (`row * gridSize + col`) that are part of found words.
   *
    * @type {Set<number>}
   */
  founds = new Set();

  /**
   * A set of normalized words that have been found by the player.
   *
   * @type {Set<string>}
   */
  solvedWords = new Set();

  /**
   * The starting point of the current selection, or `null` if no selection is active.
   *
   * @type {GridPoint|null}
   */
  anchor = null;

  /**
   * The current position of the cursor.
   *
   * @type {GridPoint}
   */
  cursor = { row: 0, col: 0 };

  /**
   * Whether the user is currently dragging to select cells.
   *
   * @type {boolean}
   */
  dragging = false;

  /**
   * Whether the canvas currently has focus, which affects keyboard navigation and selection.
   *
   * @type {boolean}
   */
  canvasHasFocus = false;
}

class Canvas {
  #mount;
  #settings;
  #logicalBoardSize;

  /**
   * The canvas element.
   *
   * @type {HTMLCanvasElement}
   */
  #canvas = document.createElement('canvas');

  /**
   * The 2D rendering context for the canvas.
   *
   * @type {CanvasRenderingContext2D|null}
   */
  #ctx = this.#canvas.getContext('2d');

  /**
   * Initializes the canvas for the word search game.
   *
   * @param {Element} element - The DOM element to mount the canvas into.
   * @param {GameSettings} settings - The game settings, including grid size, cell size, and colors.
   */
  constructor(element, settings) {
    this.#mount = element;
    this.#settings = settings;
    this.#logicalBoardSize = settings.gridSize * settings.cellSize;
    this.#configureCanvas();
  }

  #configureCanvas() {
    this.#canvas.setAttribute('aria-label', 'Word search game board');
    this.#canvas.setAttribute('role', 'img');
    this.#canvas.tabIndex = 0;
    this.#styleCanvas();

    this.#mount.innerHTML = '';
    this.#mount.appendChild(this.#canvas);

    this.#resize();
  }

  #styleCanvas() {
    this.#canvas.style.cursor = 'crosshair';
    this.#canvas.style.display = 'block';
    this.#canvas.style.touchAction = 'none';
    this.#canvas.style.boxShadow = `0 0 0 1px ${this.#settings.colors.stroke}`;
  }

  #resize() {
    const dpr = window.devicePixelRatio || 1;
    const maxWidth = Math.min(
      this.#logicalBoardSize,
      Math.max(this.#settings.minCanvasWidth, window.innerWidth - this.#settings.canvasViewportGutter)
    );

    this.#canvas.style.width  = `${maxWidth}px`;
    this.#canvas.style.height = `${maxWidth}px`;
    this.#canvas.width  = Math.floor(this.#logicalBoardSize * dpr);
    this.#canvas.height = Math.floor(this.#logicalBoardSize * dpr);

    if (!this.#ctx) {
      throw new Error('Failed to get 2D context from canvas.');
    }

    this.#ctx.setTransform(dpr, 0, 0, dpr, 0, 0);
  }

  resize() {
    this.#resize();
  }

  /**
   * Resolve the grid cell coordinates from the given client (mouse/touch) coordinates.
   *
   * @param {number} clientX
   * @param {number} clientY
   * @returns {GridPoint|null}
   */
  toGridCell(clientX, clientY) {
    const { gridSize } = this.#settings;
    const rect = this.#canvas.getBoundingClientRect();
    const x = clientX - rect.left;
    const y = clientY - rect.top;

    if (x < 0 || y < 0 || x > rect.width || y > rect.height) {
      return null;
    }

    const col = Math.floor((x / rect.width) * gridSize);
    const row = Math.floor((y / rect.height) * gridSize);

    if (row < 0 || col < 0 || row >= gridSize || col >= gridSize) {
      return null;
    }

    return { row, col };
  }

  /**
   * Render the current state of the game onto the canvas.
   *
   * @param {State} state - The current state of the game, including the grid, selection, and found words.
   */
  render(state) {
    if (!this.#ctx) {
      return;
    }

    const {
      cellSize,
      gridSize,
      colors,
      fontWeight,
      fontSize,
      fontFamily,
    } = this.#settings;
    const boardSize = this.#logicalBoardSize;
    const ctx = this.#ctx;

    ctx.clearRect(0, 0, boardSize, boardSize);
    ctx.fillStyle = colors.cell;
    ctx.fillRect(0, 0, boardSize, boardSize);

    ctx.font = `${fontWeight} ${fontSize}px ${fontFamily}`;
    ctx.textAlign = 'center';
    ctx.textBaseline = 'middle';

    const selection = new Set(state.selection.map(c => c.row * gridSize + c.col));

    for (let row = 0; row < gridSize; row++) {
      for (let col = 0; col < gridSize; col++) {
        const x = col * cellSize;
        const y = row * cellSize;
        const key = row * gridSize + col;

        ctx.fillStyle =
          state.founds.has(key) ? colors.foundCell :
          selection.has(key) ? colors.selectedCell : colors.cell;

        ctx.fillRect(x, y, cellSize, cellSize);

        ctx.strokeStyle = colors.stroke;
        ctx.strokeRect(x + 0.5, y + 0.5, cellSize - 1, cellSize - 1);

        ctx.fillStyle = colors.text;
        ctx.fillText(state.grid[row][col].letter, x + cellSize / 2, y + cellSize / 2);
      }
    }

    // If the canvas has focus, draw a focus indicator around the current cursor cell.
    if (state.canvasHasFocus) {
      const { row, col } = state.cursor;
      ctx.strokeStyle = colors.focusStroke;
      ctx.lineWidth = 2;
      ctx.strokeRect(col * cellSize + 2, row * cellSize + 2, cellSize - 4, cellSize - 4);
      ctx.lineWidth = 1;
    }
  }

  get canvas() {
    return this.#canvas;
  }
}

class Handler {
  #canvas;
  #gridSize;
  #state;
  #callbacks;
  #render;

  /**
   * @param {Canvas} canvas
   * @param {number} gridSize
   * @param {State} state
   * @param {() => void} render - A function to call to re-render the canvas after state changes.
   * @param {object} [callbacks]
   * @param {() => void} [callbacks.onCanvasFocus]
   * @param {() => void} [callbacks.onCanvasBlur]
   * @param {() => void} [callbacks.onKeyboardStart]
   * @param {() => void} [callbacks.onKeyboardCancel]
   * @param {(selection: GridPoint[]) => void} [callbacks.onSelection]
   */
  constructor(canvas, gridSize, state, render, callbacks = {}) {
    this.#canvas = canvas;
    this.#gridSize = gridSize;
    this.#state = state;
    this.#render = render;
    this.#callbacks = callbacks;
    this.#registerEvents();
  }

  #registerEvents() {
    const canvas = this.#canvas.canvas;

    canvas.addEventListener('pointerdown', this.#onPointerDown);
    canvas.addEventListener('keydown', this.#onKeyDown);
    canvas.addEventListener('focus', this.#onFocus);
    canvas.addEventListener('blur', this.#onBlur);
    window.addEventListener('pointermove', this.#onPointerMove);
    window.addEventListener('pointerup', this.#onPointerUp);
    window.addEventListener('pointercancel', this.#onPointerCancel);
    window.addEventListener('resize', this.#onResize);
  }

  #onFocus = () => {
    this.#state.canvasHasFocus = true;
    this.#callbacks.onCanvasFocus?.();
    this.#render();
  };

  #onBlur = () => {
    this.#state.canvasHasFocus = false;
    this.#callbacks.onCanvasBlur?.();
    this.#render();
  };

  /**
   * @param {KeyboardEvent} event
   */
  #onKeyDown = (event) => {
    let { row, col } = this.#state.cursor;
    let handled = true;

    switch (event.key) {
      case 'ArrowUp':
      case 'k':
        row = Math.max(0, row - 1);
        break;
      case 'ArrowDown':
      case 'j':
        row = Math.min(this.#gridSize - 1, row + 1);
        break;
      case 'ArrowLeft':
      case 'h':
        col = Math.max(0, col - 1);
        break;
      case 'ArrowRight':
      case 'l':
        col = Math.min(this.#gridSize - 1, col + 1);
        break;
      case ' ':
      case 'Spacebar':
        this.#startKeyboardSelection();
        break;
      case 'Enter':
        this.#finishKeyboardSelection();
        break;
      case 'Escape':
        this.#state.anchor = null;
        this.#state.selection = [];
        this.#callbacks.onKeyboardCancel?.();
        break;
      default:
        handled = false;
        break;
    }

    this.#state.cursor = { row, col };

    if (this.#state.anchor) {
      this.#state.selection = this.#getSelectionCells(this.#state.anchor, this.#state.cursor);
    }

    if (handled) {
      this.#render();
      event.preventDefault();
    }
  };

  #startKeyboardSelection() {
    this.#state.anchor = { ...this.#state.cursor };
    this.#callbacks.onKeyboardStart?.();
  }

  #finishKeyboardSelection() {
    if (!this.#state.anchor) {
      this.#startKeyboardSelection();
      return;
    }
    this.#callbacks.onSelection?.(this.#state.selection);
    this.#state.anchor = null;
    this.#state.selection = [];
  }

  /**
   * @param {PointerEvent} event
   */
  #onPointerDown = (event) => {
    const start = this.#canvas.toGridCell(event.clientX, event.clientY);
    if (!start) {
      return;
    }

    this.#canvas.canvas.focus({ preventScroll: true });
    this.#state.dragging = true;
    this.#state.anchor = start;
    this.#state.cursor = { ...start };
    this.#state.selection = [];

    this.#canvas.canvas.setPointerCapture(event.pointerId);
    this.#render();
  };

  /**
   * @param {PointerEvent} event
   */
  #onPointerMove = (event) => {
    if (!this.#state.dragging || !this.#state.anchor) {
      return;
    }

    const current = this.#canvas.toGridCell(event.clientX, event.clientY);
    if (!current) {
      return;
    }

    this.#state.cursor = current;
    this.#state.selection = this.#getSelectionCells(this.#state.anchor, this.#state.cursor);
    this.#render();
  };

  /**
   * @param {PointerEvent} event
   */
  #onPointerUp = (event) => {
    if (!this.#state.dragging) {
      return;
    }

    this.#state.dragging = false;

    if (this.#canvas.canvas.hasPointerCapture(event.pointerId)) {
      this.#canvas.canvas.releasePointerCapture(event.pointerId);
    }

    if (this.#state.selection.length > 0) {
      this.#callbacks.onSelection?.(this.#state.selection);
    }

    this.#state.anchor = null;
    this.#state.selection = [];
    this.#render();
  };

  #onPointerCancel = () => {
    this.#state.dragging = false;
    this.#state.anchor = null;
    this.#state.selection = [];
    this.#render();
  };

  #onResize = () => {
    this.#canvas.resize();
    this.#render();
  };

  /**
   * Returns all grid points along the straight line from `from` to `to`,
   * inclusive of both endpoints. Returns an empty array if the path is not
   * horizontal, vertical, or diagonal.
   *
  * @param {GridPoint} from - The starting grid position.
  * @param {GridPoint} to - The ending grid position.
  * @returns {GridPoint[]} The points along the path, or `[]` if not a straight line.
   */
  #getSelectionCells(from, to) {
    const items = [];
    const isDiag = Math.abs(to.row - from.row) === Math.abs(to.col - from.col);

    if (from.row === to.row || from.col === to.col || isDiag) {
      const shiftY = from.row === to.row ? 0 : to.row > from.row ? 1 : -1;
      const shiftX = from.col === to.col ? 0 : to.col > from.col ? 1 : -1;

      let row = from.row;
      let col = from.col;

      items.push({ row, col });

      while (row !== to.row || col !== to.col) {
        row += shiftY;
        col += shiftX;
        items.push({ row, col });
      }
    }

    return items;
  }
}

class WordSearch {
  static #directions = DIRECTIONS;

  /**
   * @type {GameSettings}
   */
  static #defaultSettings = {
    directions: ['RIGHT', 'DOWN', 'DIAG_RIGHT', 'DIAG_LEFT'],
    gridSize: 15,
    cellSize: 36,
    minCanvasWidth: 260,
    canvasViewportGutter: 32,
    words: [],
    fontWeight: 600,
    fontSize: 18,
    fontFamily: 'system-ui, -apple-system, sans-serif',
    colors: {
      cell: 'oklch(98.5% 0.001 106.423)',
      selectedCell: 'oklch(95.6% 0.045 203.388)',
      foundCell: 'oklch(96.2% 0.059 95.617)',
      stroke: 'oklch(92.3% 0.003 48.717)',
      focusStroke: 'oklch(78.9% 0.154 211.53)',
      text: 'oklch(26.8% 0.007 34.298)',
    },
    debug: false,
  };

  #container;
  #settings;
  #normalizedWords;
  #state = new State();

  /**
   * @type {Canvas|null}
   */
  #canvas = null;

  /**
   * @param {Partial<GameSettings> & { container?: string | Element }} [options]
   */
  constructor(options = {}) {
    const { container, ...settings } = options;

    if (typeof container === 'string') {
      const el = document.getElementById(container);
      if (!el) throw new Error(`No element found with id "${container}".`);
      this.#container = el;
    } else if (container instanceof Element) {
      this.#container = container;
    } else {
      throw new Error('`container` must be an element id string or an HTMLElement.');
    }

    this.#settings = {
      ...WordSearch.#defaultSettings,
      ...settings,
      colors: {
        ...WordSearch.#defaultSettings.colors,
        ...(settings.colors && typeof settings.colors === 'object' ? settings.colors : {}),
      },
    };

    this.#settings.words = this.#settings.words
      .map(word => String(word || '').trim())
      .filter(word => word.length > 0);

    this.#normalizedWords = this.#settings.words.map(Linguist.normalize);

    if (!this.#validateWords()) return;

    this.#setupBoardState();
    this.#initializeCanvas();
    queueMicrotask(() => this.#updateStatus('game-started'));
  }

  #validateWords() {
    for (let i = 0; i < this.#normalizedWords.length; i++) {
      if (this.#normalizedWords[i].length > this.#settings.gridSize) {
        const error = `The length of word "${this.#normalizedWords[i]}" exceeds gridSize.`;
        alert(error);
        console.error(error);
        return false;
      }
    }
    return true;
  }

  #setupBoardState() {
    let placed = false;
    for (let attempts = 0; !placed && attempts < 300; attempts++) {
      this.#initializeGrid();
      placed = this.#placeAllWords();
    }

    if (!placed) {
      throw new Error('Unable to place all words in the grid after multiple attempts.');
    }

    if (!this.#settings.debug) {
      this.#fillBlankCells();
    }
  }

  #initializeGrid() {
    this.#state.grid = Array.from({ length: this.#settings.gridSize }, (_, row) =>
      Array.from({ length: this.#settings.gridSize }, (__, col) => ({
        row,
        col,
        letter: '',
      }))
    );
  }

  #placeAllWords() {
    for (const word of this.#normalizedWords) {
      let placed = false;
      for (let tries = 0; tries < 150 && !placed; tries++) {
        const direction = this.#settings.directions[
          Random.integer(0, this.#settings.directions.length - 1)
        ];
        placed = this.#placeWord(word, direction);
      }
      if (!placed) {
        return false;
      }
    }
    return true;
  }

  /**
   * @param {string} word
   * @param {Direction} direction
   * @returns {boolean}
   */
  #placeWord(word, direction) {
    const step = WordSearch.#directions[direction];
    if (!step) {
      return false;
    }

    const [startRow, startCol] = this.#randomStart(word, direction);

    for (let i = 0; i < word.length; i++) {
      const r = startRow + i * step[0];
      const c = startCol + i * step[1];
      const l = this.#state.grid[r][c].letter;
      if (l !== '' && l !== word[i]) {
        return false;
      }
    }

    for (let i = 0; i < word.length; i++) {
      const r = startRow + i * step[0];
      const c = startCol + i * step[1];
      this.#state.grid[r][c].letter = word[i];
    }

    return true;
  }

  /**
   * @param {string} word
   * @param {Direction} direction
   * @returns {[number, number]}
   */
  #randomStart(word, direction) {
    const max = this.#settings.gridSize;
    const len = word.length;

    switch (direction) {
      case 'RIGHT':
        return [Random.integer(0, max - 1),  Random.integer(0, max - len)];
      case 'DOWN':
        return [Random.integer(0, max - len), Random.integer(0, max - 1)];
      case 'DIAG_RIGHT':
        return [Random.integer(0, max - len), Random.integer(0, max - len)];
      default:
        return [Random.integer(0, max - len), Random.integer(len - 1, max - 1)];
    }
  }

  #fillBlankCells() {
    const first = this.#normalizedWords[0]?.[0] ?? 'A';
    const [lo, hi] = Linguist.detectLanguageRange(first);

    for (const row of this.#state.grid) {
      for (const cell of row) {
        if (cell.letter === '') {
          cell.letter = String.fromCharCode(Random.integer(lo, hi));
        }
      }
    }
  }

  #initializeCanvas() {
    this.#canvas = new Canvas(this.#container, this.#settings);

    new Handler(this.#canvas, this.#settings.gridSize, this.#state, () => this.#render(), {
      onCanvasFocus: () => this.#updateStatus('board-focused'),
      onKeyboardStart: () => this.#updateStatus('keyboard-started'),
      onKeyboardCancel: () => this.#updateStatus('keyboard-cancelled'),
      onSelection: (selection) => this.#lookupSelection(selection),
    });

    this.#render();
  }

  #render() {
    if (this.#canvas) {
      this.#canvas.render(this.#state);
    }
  }

  /**
   * @param {GridPoint[]} selection
   * @returns {void}
   */
  #lookupSelection(selection) {
    const cells = selection.map(({ row, col }) => this.#state.grid[row][col]);

    if (this.#settings.debug && cells.some(cell => cell.letter === '')) {
      return;
    }

    const letters = cells.map(c => c.letter).join('');
    const reversed = [...letters].reverse().join('');

    const foundWord =
      this.#normalizedWords.includes(letters) ? letters :
      this.#normalizedWords.includes(reversed) ? reversed : null;

    if (!foundWord || this.#state.solvedWords.has(foundWord)) {
      return;
    }

    this.#state.solvedWords.add(foundWord);

    for (const cell of cells) {
      this.#state.founds.add(cell.row * this.#settings.gridSize + cell.col);
    }

    const index = this.#normalizedWords.indexOf(foundWord);
    const displayWord = index === -1 ? foundWord : this.#settings.words[index];

    this.#updateStatus('word-found', {
      normalizedWord: foundWord,
      displayWord,
      solvedCount: this.#state.solvedWords.size,
      totalWords: this.#normalizedWords.length,
    });

    if (this.#state.solvedWords.size === this.#normalizedWords.length) {
      this.#completeGame();
    }
  }

  /**
   * @param {string} name
   * @param {object} data
   */
  #updateStatus(name, data = {}) {
    this.#container.dispatchEvent(
      new CustomEvent('wordsearch:status', { bubbles: true, detail: { name, ...data } })
    );
  }

  #completeGame() {
    this.#updateStatus('game-completed');
  }

  get container() {
    return this.#container;
  }

  get words() {
    return this.#settings.words.slice();
  }

  get normalizedWords() {
    return this.#normalizedWords.slice();
  }
}

export { WordSearch };