← Blog
AlgorithmVisualizationTypeScriptGraph

Visualizing Pathfinding Algorithms — Watching A*, BFS, and DFS Solve a Maze

11 min read

Go deeper on this topic

Browser Game Development

Game loop design, collision detection, pathfinding, and tooling for browser games

Article 4 of 7 in this series.

View topic page

Next reads

Collision Detection Fundamentals — Circles, Rectangles, and Impulse-Based Response

A deep dive into circle-circle and circle-rectangle collision detection algorithms, restitution-based bounce control, and the math behind impulse-based collision response, explained through the physics.ts implementation.

Designing a Type-Safe Game Loop in TypeScript — State Management for Snake and Tetris

Game state management and frame rate control using TypeScript's type system, explored through Snake, Tetris, and Breakout implementations.

Pinball Physics Simulation — Implementing Flippers, Bumpers, and Gravity with Canvas API

Implementing pinball physics with Canvas API. Covers flipper rotational motion, bumper restitution, gravity, and ball behavior.

Use the topic hub as a map, then continue to the next article in the series. New here? Start at the home hub →

Why Visualize

The fastest way to understand pathfinding algorithms is to "watch them in action." BFS expanding in concentric circles, DFS charging down a single path, A* efficiently searching toward the destination — these differences are hard to grasp from textbook pseudocode alone.

Grid Representation

MazeRunner's grid is a 2D array where each cell is either a wall (1) or a path (0). TypeScript types make the states explicit:

type CellState = 'wall' | 'path' | 'visited' | 'frontier' | 'solution'

type Grid = CellState[][]

function createMaze(cols: number, rows: number): Grid {
  const grid: Grid = Array.from({ length: rows }, () =>
    Array.from({ length: cols }, () => 'wall')
  )

  // DFS-based maze generation
  function carve(x: number, y: number) {
    grid[y][x] = 'path'
    const dirs = shuffle([[0, -2], [0, 2], [-2, 0], [2, 0]])

    for (const [dx, dy] of dirs) {
      const nx = x + dx
      const ny = y + dy
      if (nx >= 0 && nx < cols && ny >= 0 && ny < rows && grid[ny][nx] === 'wall') {
        grid[y + dy / 2][x + dx / 2] = 'path'
        carve(nx, ny)
      }
    }
  }

  carve(1, 1)
  return grid
}

The Recursive Backtracker (wall carving method) generates a perfect maze. A solution always exists, and every corridor is connected by a unique path.

Uses a queue to explore cells at equal distance from the start:

async function bfs(grid: Grid, start: [number, number], end: [number, number]) {
  const queue: [number, number][] = [start]
  const parent = new Map<string, string>()
  const key = (x: number, y: number) => `\${x},\${y}`
  parent.set(key(...start), '')

  while (queue.length > 0) {
    const [x, y] = queue.shift()!
    grid[y][x] = 'visited'

    if (x === end[0] && y === end[1]) {
      return reconstructPath(parent, start, end)
    }

    for (const [dx, dy] of [[0, 1], [0, -1], [1, 0], [-1, 0]]) {
      const nx = x + dx
      const ny = y + dy
      const nk = key(nx, ny)
      if (isValid(grid, nx, ny) && !parent.has(nk)) {
        parent.set(nk, key(x, y))
        queue.push([nx, ny])
        grid[ny][nx] = 'frontier'
      }
    }

    // Wait for rendering at each step for visualization
    await sleep(10)
  }

  return null
}

BFS guarantees the shortest path (for unweighted graphs). The beautiful sight of explored cells expanding in concentric circles.

Uses a stack to dig deep along a single path:

async function dfs(grid: Grid, start: [number, number], end: [number, number]) {
  const stack: [number, number][] = [start]
  const parent = new Map<string, string>()
  const key = (x: number, y: number) => `\${x},\${y}`
  parent.set(key(...start), '')

  while (stack.length > 0) {
    const [x, y] = stack.pop()!

    if (grid[y][x] === 'visited') continue
    grid[y][x] = 'visited'

    if (x === end[0] && y === end[1]) {
      return reconstructPath(parent, start, end)
    }

    for (const [dx, dy] of [[0, 1], [0, -1], [1, 0], [-1, 0]]) {
      const nx = x + dx
      const ny = y + dy
      const nk = key(nx, ny)
      if (isValid(grid, nx, ny) && !parent.has(nk)) {
        parent.set(nk, key(x, y))
        stack.push([nx, ny])
      }
    }

    await sleep(10)
  }

  return null
}

DFS doesn't guarantee the shortest path, but uses less memory. In mazes, you can see it charging forward until hitting a dead end, then backtracking.

A* (A-Star)

BFS with a heuristic (estimated remaining distance) added:

function heuristic(a: [number, number], b: [number, number]): number {
  return Math.abs(a[0] - b[0]) + Math.abs(a[1] - b[1]) // Manhattan distance
}

async function aStar(grid: Grid, start: [number, number], end: [number, number]) {
  const openSet: { pos: [number, number]; f: number }[] = [
    { pos: start, f: heuristic(start, end) },
  ]
  const gScore = new Map<string, number>()
  const parent = new Map<string, string>()
  const key = (x: number, y: number) => `\${x},\${y}`

  gScore.set(key(...start), 0)

  while (openSet.length > 0) {
    openSet.sort((a, b) => a.f - b.f)
    const current = openSet.shift()!
    const [x, y] = current.pos
    grid[y][x] = 'visited'

    if (x === end[0] && y === end[1]) {
      return reconstructPath(parent, start, end)
    }

    for (const [dx, dy] of [[0, 1], [0, -1], [1, 0], [-1, 0]]) {
      const nx = x + dx
      const ny = y + dy
      if (!isValid(grid, nx, ny)) continue

      const nk = key(nx, ny)
      const tentativeG = (gScore.get(key(x, y)) ?? Infinity) + 1

      if (tentativeG < (gScore.get(nk) ?? Infinity)) {
        parent.set(nk, key(x, y))
        gScore.set(nk, tentativeG)
        const f = tentativeG + heuristic([nx, ny], end)
        openSet.push({ pos: [nx, ny], f })
        grid[ny][nx] = 'frontier'
      }
    }

    await sleep(10)
  }

  return null
}

Manhattan distance is used as the heuristic because there's no diagonal movement on the grid. As long as the heuristic never overestimates the actual cost (admissible), A* guarantees the shortest path.

Canvas API Visualization Techniques

To "show" the search process, await sleep(10) is inserted at each step to update the rendering. Colors change based on cell state:

const CELL_COLORS: Record<CellState, string> = {
  wall: '#1a1a2e',
  path: '#16213e',
  visited: '#0f3460',
  frontier: '#e94560',
  solution: '#53d769',
}

Coloring frontier (pending exploration) red, visited (explored) blue, and solution (final path) green makes the algorithm's "thought process" intuitively visible.

Relation to TopologicalSort

TopologicalSort is DAG (directed acyclic graph) traversal that uses DFS post-order. The problem setup differs from MazeRunner, but both share graph traversal as their common foundation.

Summary: Techniques and Tools for Pathfinding Algorithms

For deepening understanding of pathfinding algorithms, the books on the tool shelf are ideal. Rich illustrations and implementation examples also serve as inspiration for visualization approaches.

Follow @sakimyto