GBGD for CT
Grid-Based Games
Timelines

Timelines

Grid-based games like Tic Tac Toe can include a timeline of board states for undo, redo, branching, and replay. After each move, call .clone() and append the snapshot to a timeline, yielding a replayable sequence of states.

This works with both aggregate and layered strategies: timelines record how state evolves, independent of where it’s stored.

This chapter teaches

  • How to clone and store grid states to build a timeline
  • How to render the current state using a time index
  • How to implement replay, undo/redo, and branching
  • How timelines complement aggregate and layered boards

Timeline Tic-Tac-Toe

A timeline is a log of snapshots. Each move appends a clone of the current grid to timeline; navigating time is just changing a numeric index. If a new move is made from a past position, the future is truncated and a new branch begins.


code
let patterns1 = [];
let patterns2 = [];
let game;
let winner;
let resetButton;
let undoButton;
let redoButton;
let timeline = [];
let timelineIndex = 0;
const x = 'X', o = 'O';

function setup() {
  // Create canvas and buttons
  createCanvas(300, 300);
  textAlign(CENTER, CENTER);
  resetButton = createButton('reset game');
  resetButton.position(10, height + 10);
  resetButton.mousePressed(resetGame);
  undoButton = createButton('undo');
  undoButton.position(100, height + 10);
  undoButton.mousePressed(undoMove);
  redoButton = createButton('redo');
  redoButton.position(160, height + 10);
  redoButton.mousePressed(redoMove);
  // Initialize board and win patterns
  resetGame();
  // Create win patterns for Player 1 (x)
  const diag1 = createQuadrille([
    [x],
    [null, x],
    [null, null, x]
  ]); // createQuadrille builds a grid from a jagged array
  const horiz1 = createQuadrille([x, x, x]);
  patterns1.push(
    diag1,
    diag1.clone().reflect(),
    horiz1,
    horiz1.clone().transpose()
  );
  // Create win patterns for Player 2 (o) by replacing x with o
  const horiz2 = horiz1.clone().replace(x, o); // replace modifies matching values
  const diag2 = diag1.clone().replace(x, o);
  patterns2.push(
    diag2,
    diag2.clone().reflect(),
    horiz2,
    horiz2.clone().transpose()
  );
}

function draw() {
  background('DarkSeaGreen');
  drawQuadrille(timeline[timelineIndex], { origin: CORNER });
  // Display winner message if game is over
  if (winner) {
    undoButton.elt.disabled = true;
    redoButton.elt.disabled = true;
    textSize(32);
    fill('black');
    text(`${winner} wins!`, width / 2, height / 2);
    noLoop();
  }
  // Enable or disable undo/redo buttons based on timeline position
  undoButton.elt.disabled = timelineIndex === 0;
  redoButton.elt.disabled = timelineIndex === timeline.length - 1;
}

function mousePressed() {
  // Skip input if game is over
  if (winner) return;
  const row = game.mouseRow;
  const col = game.mouseCol;
  // Place marker if cell is valid and empty
  if (game.isValid(row, col) && game.isEmpty(row, col)) {
    const current = game.order % 2 === 0 ? x : o;
    // Truncate timeline if branching from a past state
    timeline.length = timelineIndex + 1;
    game.fill(row, col, current);              // fill writes to the board
    timeline.push(game.clone());               // clone stores a snapshot of the current state
    timelineIndex++;
    // Check for win or reset if board is full
    winner = checkWinner();
    if (!winner && game.order === 9) resetGame();
    undoButton.elt.disabled = false;
    redoButton.elt.disabled = true;
  }
}

// Start new game and timeline
function resetGame() {
  game = createQuadrille(3, 3);      // createQuadrille initializes empty grid
  timeline = [game.clone()];         // clone captures initial state
  timelineIndex = 0;
  winner = undefined;
  undoButton.elt.disabled = false;
  redoButton.elt.disabled = true;
  loop();
}

// Step backward in timeline
function undoMove() {
  if (timelineIndex > 0 && !winner) {
    timelineIndex--;
    game = timeline[timelineIndex].clone(); // restore previous state
    loop();
  }
}

// Step forward in timeline
function redoMove() {
  if (timelineIndex < timeline.length - 1 && !winner) {
    timelineIndex++;
    game = timeline[timelineIndex].clone(); // restore next state
    loop();
  }
}

// Check for win condition using search
function checkWinner() {
  return patterns1.some(p => game.search(p, true).length > 0) && 'Player 1' ||
         patterns2.some(p => game.search(p, true).length > 0) && 'Player 2';
  // search returns matching locations of a pattern in the board
}

Timeline-Based Interaction

Each move updates the live grid and then appends a clone to timeline. Players can step back with undo, forward with redo, or create alternate futures by playing from a past index, truncating the timeline and starting a new branch.

mousePressed
function mousePressed() {
  if (winner) return;
  const row = game.mouseRow;
  const col = game.mouseCol;
  if (game.isValid(row, col) && game.isEmpty(row, col)) {
    const current = game.order % 2 === 0 ? x : o;
    timeline.length = timelineIndex + 1; // truncate timeline
    game.fill(row, col, current);        // place move
    timeline.push(game.clone());         // save snapshot
    timelineIndex++;
    winner = checkWinner();              // check win
    if (!winner && game.order === 9) resetGame(); // restart on draw
  }
}

Undo and Redo

Undo and redo navigate the timeline and restore the chosen snapshot into game. Undo is disabled at the first snapshot; redo is disabled at the latest. After a win, time travel is read-only.

undo and redo
function undoMove() {
  if (timelineIndex > 0 && !winner) {
    timelineIndex--;
    game = timeline[timelineIndex].clone();
  }
}

function redoMove() {
  if (timelineIndex < timeline.length - 1 && !winner) {
    timelineIndex++;
    game = timeline[timelineIndex].clone();
  }
}

Try this

  • Add a Replay button that auto-advances timelineIndex with a slider-controlled speed.
  • Implement bookmarks: store named indices (e.g., "opening", "fork", "endgame") and jump by name.

Initializing the Timeline

Start by cloning the empty board. Every reset seeds the history with this initial snapshot.

resetGame
function resetGame() {
  game = createQuadrille(3, 3);
  timeline = [game.clone()];
  timelineIndex = 0;
  winner = undefined;
  loop();
}

Displaying the Current State

Always draw timeline[timelineIndex]. Moving back and forth in time is simply an index change.

function draw() {
  background('DarkSeaGreen');
  drawQuadrille(timeline[timelineIndex], { origin: CORNER });
  if (winner) {
    textSize(32);
    fill('black');
    text(`${winner} wins!`, width / 2, height / 2);
    noLoop();
  }
}

Try this

  • Show a thumbnail strip of all snapshots (small drawQuadrille calls) and make them clickable.
  • Highlight the current index and preview the next and previous states.

Pattern Matching and Game Over

As in the aggregate strategy, win detection uses predefined patterns for each player and matches them with search on the current snapshot. If a player wins, the result is displayed, the draw loop stops, and timeline navigation becomes read-only.

checkWinner
function checkWinner() {
  return patterns1.some(p => game.search(p, true).length > 0) && 'Player 1' ||
         patterns2.some(p => game.search(p, true).length > 0) && 'Player 2';
}

Try this

  • Persist the timeline by exporting it with saveJSON so history can be saved or shared.
  • Or encode it into the URL query string (e.g. https://mygame.net/play?timeline=...) so others can load the same history directly from the link.
  • Combine with Layered Boards: store clones of both layers at each step and allow synchronized time travel across them — or experiment with navigating each layer independently.

References

Further Reading

Layered BoardsAlgebra