Overview

This document explains the architecture and internals of index.js, which powers a Tic-Tac-Toe visualizer that builds and renders the complete state space as a 3D directed graph (Three.js instancing + force layout) while also offering a 2D canvas for direct board interaction.

High-Level Architecture

• 2D UI (Canvas): Draws the 3x3 grid and glyphs; handles mouse input and status updates.
• Game Logic: Pure functions that encode/decode boards, validate states, enumerate moves, and compute winners/status.
• 3D Graph Engine (TTTGraph3D): Three.js scene that renders thousands of nodes (board states) and edges (transitions) with instanced meshes, plus a lightweight force simulation with spatial partitioning for scale.

Data Model

Board Encoding

• 3x3 array of chars: '-' | 'X' | 'O'
• Key: 9-char string in row-major order. Example: "XOX--O---"
• Helpers: newBoard(), boardToKey(), keyToBoard()

Node Payload

Each graph node stores compact metadata:

type NodeState = {
  board: string;        // 9-char key
  next_player: 'X'|'O'; // whose turn
  status: 'ongoing'|'X-wins'|'O-wins'|'draw';
};

Core Functions (Gameplay)

Representative Helpers

function boardToKey(...) {
 
  // Flatten row-major into a 9-char string
  let s = "";
  for (let r = 0; r < 3; r++) {
    for (let c = 0; c < 3; c++) {
      s += state[r][c];
    }
  }
  return s;
}
 
function keyToBoard(key) {
  const b = newBoard();
 
  for (let i = 0; i < 9; i++) {
    const r = Math.floor(i / 3);
    const c = i % 3;
    b[r][c] = key[i];
  }
  return b;
}
 
function lineWinner(a, b, c) {
  return a !== EMPTY && a === b && b === c ? a : null;
}
 
function getWinner(state) {
  // rows
  for (let r = 0; r < 3; r++) {
    const w = lineWinner(state[r][0], state[r][1], state[r][2]);
    if (w) return w;
  
  ...
}

function legalMoves(...) {
 
  if (statusOf(state) !== "ongoing") return [];
  const p = nextPlayer(state);
  if (!p) return [];
  const moves = [];
  for (let r = 0; r < 3; r++) {
    for (let c = 0; c < 3; c++) {
      if (state[r][c] == EMPTY) moves.push([r, c]);
    }
  }
  return moves;
}
 
function applyMove(state, row, col, move) {
  const nb = state.map((row) => row.slice());
  nb[row][col] = move;
  return nb;
 
  ...
}

State-Space Construction

The 3D graph is grown by traversing the game tree from the empty board. Both BFS and DFS are supported to control exploration order and graph “shape”.

buildStateSpace(...) {
    const start = newBoard();
    const startKey = boardToKey(start);
 
    console.log("Start:", start);
    console.log("Start key:", startKey);
    console.log("Using", useBFS ? "BFS" : "DFS", "traversal");
 
    this.addNode(startKey, 0xff00ff, {
      board: startKey,
      next_player: "X",
      status: "ongoing",
    
  ...
}

Traversal flow:

1. Seed with newBoard() → add root node (magenta).
2. While the stack/queue is non-empty and under maxNodes:
   • Pop (DFS) or shift (BFS) a key → decode with keyToBoard().
   • Compute next_player with statusOf() and nextPlayer(); update node metadata.
   • If status is 'ongoing', enumerate legalMoves(state).
   • For each move, applyMove() → child, check isReachable(child).
   • Get childKey; if unseen, addNode() with color by nextPlayer(child).
   • addEdge(parentKey, childKey, move, player) and enqueue child.

Correctness guards:

• countMarks() and nextPlayer() enforce alternation and rule out illegal positions.
• getWinner()/statusOf() stop expansion when a terminal state is reached.

3D Graph Engine — TTTGraph3D

Rendering Stack

• Scene/Camera/Renderer: THREE.Scene, THREE.PerspectiveCamera, THREE.WebGLRenderer(antialias).
• Instanced Nodes: THREE.InstancedMesh(SphereGeometry, MeshStandardMaterial, capacity)
• Instanced Edges: THREE.InstancedMesh(CylinderGeometry or custom line, material, capacity)
• Capacity Growth: growArray() doubles buffers to avoid reallocation storms.

Force Simulation

• Lightweight per-frame integration with damping and a central gravity term.
• Repulsion between nodes (inverse-square clamped by maxRepulsionDistance).
• Attraction along edges to keep neighbors coherent.
• Spatial partitioning via a uniform grid (spatialGrid) to cull far interactions.

Interaction & UX

• Orbit/track controls bound to the renderer’s canvas.
• Toggles: toggleNodeLabels(), resetCamera(), clearGraph().
• Selection + deletion hooks (deleteSelectedNode) where supported in the UI.
• Window resize handlers keep aspect ratio and pixel ratio in sync.

2D Canvas Layer

• drawGrid() and drawSymbol() render the tic-tac-toe board and glyphs.
• handleCanvasClick() maps mouse (x,y) to cell, applies moves if legal.
• updateGameStatus() reflects 'ongoing' | 'X-wins' | 'O-wins' | 'draw' in the DOM.
• resetGame() clears state; initGame() wires listeners and performs initial draw.

Performance Notes

• Instancing means a single draw call per node/edge batch, enabling 10k+ instances.
• Pre-allocated vectors and pooled Object3D “dummies” cut GC pressure.
• Spatial culling avoids O(N²) all-pairs — practical O(N · k) with small neighborhood k.
• frameCount/lastTime stats track FPS without extra devtools overhead.

Complexity (State Space)

• Max nodes in perfect play tree ≤ 5,478 unique positions (incl. symmetries, typical constraints).
• Each expansion enumerates up to 9 moves → branching factor drops quickly.
• Time to build to maxNodes: O(V + E) with V nodes, E edges produced.
• Memory: O(V) for nodes map + instancing buffers (positions, matrices).

Public API (Selected)

class TTTGraph3D {
  buildStateSpace(useBFS: boolean = false, maxNodes: number = 800): void
  addNode(key: string, color: number, meta: NodeState): boolean
  addEdge(from: string, to: string, move: [number, number], by: 'X'|'O'): boolean
  clearGraph(): void
  resetCamera(): void
  toggleNodeLabels(show?: boolean): void
  update(): void  // animation tick
}

Usage

1. Instantiate TTTGraph3D after the DOM is ready.
2. Call graph.buildStateSpace(true /* BFS */ , 2000 /* max */).
3. Interact with the 2D board or fly around the 3D graph; toggle labels as needed.

Edge Cases & Validation

• Enforce isReachable() before adding nodes to avoid illegal positions (e.g., extra Xs).
• Stop expansion when statusOf(state) !== 'ongoing'.
• If PLAYERS initialization uses a comma expression, prefer const PLAYERS = ['X','O'].

Future Improvements

• Memoize statusOf() and getWinner() on board keys to avoid recomputation.
• Add symmetry elimination (rotation/reflection) to reduce duplicate nodes.
• GPU spring forces via transform feedback or compute (WebGPU) for very large graphs.
• Inline attribute buffers for edge directions to compact memory further.

Appendix

Function Index

• checkWinner, isBoardFull, newBoard, boardToKey, keyToBoard, lineWinner, getWinner, isFull, statusOf, countMarks, nextPlayer, legalMoves, applyMove, isReachable, updateGameStatus, drawGrid, drawSymbol, resetGame, handleCanvasClick, initGame, addNode, addConnection, connectRandomNodes, clearGraph, resetCamera, toggleNodeLabels, deleteSelectedNode, growArray

Small Constants & Globals

• Canvas: 280x280 mini board for quick interaction.
• Colors: root (magenta), X-next (red), O-next (blue), terminals dimmed/locked.
• Physics knobs: forceStrength, repulsionForce, attractionForce, damping, centerForce.