Three.js Pathfinding Visualizer (A*, Dijkstra, Greedy, BFS)

Compare A*, Dijkstra, greedy best-first and breadth-first search on a 3D grid in Three.js, animating the open set, explored cells coloured by cost and the final path over random walls, recursive mazes or weighted terrain, with click-to-edit walls.

Key topics: a star pathfinding, dijkstra visualization, pathfinding algorithms, three.js grid, bfs, greedy best first search

What this code does

- A*: expands the node with the lowest f = g + h; with an admissible heuristic (Manhattan or octile) it finds optimal paths while exploring far less than Dijkstra.
- Dijkstra: priority is g alone, so the search grows in cost contours and is optimal on weighted terrain.
- Greedy Best-First: priority is h alone, so it is fast and goal-directed but often not optimal.
- Breadth-First: a FIFO queue that ignores weights, optimal only when every step costs the same.
- Visual Key: purple is the frontier, blue to teal are explored cells by distance, yellow is the path; weighted cells are brown and cost up to 5×.
- Controls: algorithm, map, wall density, diagonal moves (no corner cutting), speed, rerun and new map; click to toggle walls.

Continue Learning

JavaScript Implementation

ES6+
// A*: always expand the open node with the smallest f = g (cost so far) + h (heuristic to goal)

function aStar (start, goal, neighbours, h) {
  const g = new Map([[start, 0]])
  const parent = new Map()
  const open = new MinHeap()
  open.push(start, h(start))
  while (open.size) {
    const cur = open.pop()
    if (cur === goal) break
    for (const [n, cost] of neighbours(cur)) {
      const ng = g.get(cur) + cost
      if (ng < (g.get(n) ?? Infinity)) {
        g.set(n, ng)
        parent.set(n, cur)
        open.push(n, ng + h(n))   // Dijkstra: priority = ng · Greedy: priority = h(n)
      }
    }
  }
  return parent // walk back from goal to reconstruct the path
}