Same Game in Vanilla JS — Flood Fill, Gravity, and Column Compression

#javascript #gamedev #puzzle #algorithms

Same Game in Vanilla JS — Flood Fill, Gravity, and Column Compression

Same Game is deceptively simple: click groups of 2+ adjacent same-color blocks to remove them. The score per removal is (count - 2)², so a group of 10 scores 64 while two groups of 5 score 18. Planning large groups is the entire game. The implementation is three algorithms working together: flood-fill to find the group, gravity to drop remaining blocks, and column compression to collapse empty columns left.

I had an old Same Game implementation sitting around from years ago. Porting it into the portfolio series was a chance to revisit the mechanics and clean up the pure-function boundaries.

🔗 Live demo: https://sen.ltd/portfolio/same-game/
📦 GitHub: https://github.com/sen-ltd/same-game

Features:

3 difficulties (10×10/3 colors, 15×12/4 colors, 20×15/5 colors)
Hover to preview group (desktop), double-tap to confirm (mobile)
Undo last move
Best score per difficulty (localStorage)
Clear-board bonus (+1000)
Japanese / English UI
Zero dependencies, 53 tests

The scoring formula

(count - 2)² per removal. Why squared? Because exponential scoring creates a strategic game: clearing blocks one pair at a time gives you 0 per move (2² - 4 = 0... actually (2-2)² = 0, yes). A group of 3 scores 1, 4 scores 4, 5 scores 9, 10 scores 64, 20 scores 324. Chaining large groups matters far more than clearing fast.

A skilled player doesn't remove every group as soon as it appears. They save colors, build up large clusters, then take them in one huge move. The squared formula incentivizes patience.

Flood fill for groups

export function match(board, row, col) {
  const target = board[row]?.[col];
  if (target == null) return null;

  const points = [[row, col]];
  const visited = new Set([`${row},${col}`]);
  const stack = [[row, col]];

  while (stack.length > 0) {
    const [r, c] = stack.pop();
    for (const [dr, dc] of [[-1,0],[1,0],[0,-1],[0,1]]) {
      const nr = r + dr, nc = c + dc;
      const key = `${nr},${nc}`;
      if (visited.has(key)) continue;
      if (board[nr]?.[nc] !== target) continue;
      visited.add(key);
      points.push([nr, nc]);
      stack.push([nr, nc]);
    }
  }

  return points.length >= 2 ? points : null;
}

DFS with a visited Set. Returns null if the clicked cell has no orthogonal same-color neighbor — you can't remove a single block by itself.

Gravity: blocks fall down

After removing the matched group, blocks above must drop to fill gaps:

function applyGravity(board) {
  const rows = board.length;
  const cols = board[0].length;
  const result = Array.from({ length: rows }, () => Array(cols).fill(null));

  for (let col = 0; col < cols; col++) {
    // Extract this column from bottom to top, skipping nulls
    const stack = [];
    for (let row = rows - 1; row >= 0; row--) {
      if (board[row][col] !== null) stack.push(board[row][col]);
    }
    // Place them back at the bottom of the new column
    for (let i = 0; i < stack.length; i++) {
      result[rows - 1 - i][col] = stack[i];
    }
  }
  return result;
}

Each column is processed independently. Non-null values stay; they just settle downward.

Column compression: empty columns collapse left

A subtler detail: if an entire column becomes empty, it's removed and the columns to its right shift left. This prevents fragmented boards.

function compressColumns(board) {
  const cols = board[0].length;
  const keep = [];
  for (let col = 0; col < cols; col++) {
    if (board.some(row => row[col] !== null)) keep.push(col);
  }
  return board.map(row => {
    const newRow = Array(cols).fill(null);
    keep.forEach((origCol, newIdx) => {
      newRow[newIdx] = row[origCol];
    });
    return newRow;
  });
}

The keep array records which columns have any non-null cell. The new board maps those columns to the leftmost positions. Right-side columns become null-filled.

Game over detection

After every move, check if any matching groups still exist:

export function getHasNext(board) {
  const rows = board.length;
  const cols = board[0].length;
  for (let row = 0; row < rows; row++) {
    for (let col = 0; col < cols; col++) {
      const v = board[row][col];
      if (v == null) continue;
      // Check right and down only (avoids duplicate checks)
      if (board[row]?.[col + 1] === v) return true;
      if (board[row + 1]?.[col] === v) return true;
    }
  }
  return false;
}

Only checking right and down avoids redundant checks — if (row, col) and (row, col+1) match, we find it from (row, col). O(rows × cols) with 2 constant-time lookups per cell.

Undo

Each play() call pushes the previous state onto a history stack:

export function play(state, row, col) {
  const points = match(state.board, row, col);
  if (!points) return state;
  const newBoard = fill(state.board, points);
  return {
    ...state,
    board: newBoard,
    score: state.score + getScore(points),
    hasNext: getHasNext(newBoard),
    history: [...state.history, { board: state.board, score: state.score }],
  };
}

export function undo(state) {
  if (state.history.length === 0) return state;
  const last = state.history[state.history.length - 1];
  return {
    ...state,
    board: last.board,
    score: last.score,
    hasNext: getHasNext(last.board),
    history: state.history.slice(0, -1),
  };
}