Pathfinding Visualiser
A search spreads across a grid of walls from the green start, cell by cell, until it reaches the pink goal, and then the shortest path is drawn back along the way. A* leans towards the goal and searches only what it needs; Dijkstra floods out evenly in every direction. Both take a turn on the same walls before new walls go up. Tap or click any cell to move the goal there.
How to use it
- Paste the snippet just before
</head>. - Add
data-pathfinding-visualiserto a box with a height and a dark background.
Options
Add any of these attributes to the same element.
data-algorithm | astar, dijkstra or greedy (greedy best-first), or a comma-separated list to take turns. Default astar,dijkstra. |
data-cell | Cell size in px. Default scaled to the box, 10 to 18. |
data-walls | How much of the grid is wall, 0 to 0.45. Default 0.3. |
data-speed | Cells searched per second. Default fills the whole grid in about five seconds. |
data-diagonal | Allow diagonal steps. |
data-loop="false" | Stop after one search instead of moving on. |
Searched cells are coloured by how far they are from the start. The walls are always checked to leave a way through. It’s paused when off screen, and with reduced motion it shows the finished search and path.
<script src="https://cdn.jsdelivr.net/npm/[email protected]/dist/bundles/anime.umd.min.js"></script>
<script>
(function () {
// Pathfinding Visualiser: a search spreads out across a grid of walls from
// the green start, cell by cell, until it reaches the pink goal. Then the
// shortest path it found is drawn back along the way. A* heads straight for
// the goal; Dijkstra floods out evenly in all directions; greedy best-first
// rushes in but can be fooled. Each runs on the same walls, so you can
// compare how much of the grid they had to search.
// Tap or click a cell to move the goal there.
// Usage: <div data-pathfinding-visualiser style="height:360px;background:#120a24"></div>
// Optional: data-algorithm (astar, dijkstra or greedy, or a comma-separated
// list to take turns on each set of walls; default "astar,dijkstra"),
// data-cell (cell size in px, default scaled to the box, 10 to 18),
// data-walls (how much of the grid is wall, 0 to 0.45, default 0.3),
// data-speed (cells searched per second, default fills the grid in about
// five seconds), data-diagonal (allow diagonal steps), data-loop="false"
// (stop after one search instead of moving on to new walls).
var DEFAULTS = { algorithm: 'astar,dijkstra', walls: 0.3 };
var NAMES = { astar: 'A*', dijkstra: 'Dijkstra', greedy: 'Greedy best-first' };
var css =
'[data-pathfinding-visualiser]{position:relative;isolation:isolate;overflow:hidden;cursor:pointer;touch-action:manipulation}' +
'.pfv-canvas{position:absolute;inset:0;width:100%;height:100%;z-index:-1}';
var style = document.createElement('style');
style.textContent = css;
document.head.appendChild(style);
function reduced() { return window.matchMedia('(prefers-reduced-motion: reduce)').matches; }
// Search colours, from cells near the start to cells far from it.
var RAMP = [[99, 102, 241], [168, 85, 247], [236, 72, 153]];
function ramp(t) {
var f = Math.max(0, Math.min(1, t)) * (RAMP.length - 1), i = Math.min(RAMP.length - 2, Math.floor(f)), k = f - i;
var a = RAMP[i], b = RAMP[i + 1];
return [a[0] + (b[0] - a[0]) * k, a[1] + (b[1] - a[1]) * k, a[2] + (b[2] - a[2]) * k];
}
function build(el) {
var d = el.dataset;
var canvas = document.createElement('canvas');
canvas.className = 'pfv-canvas';
canvas.setAttribute('aria-hidden', 'true');
el.insertBefore(canvas, el.firstChild);
var ctx = canvas.getContext('2d');
var algos = (d.algorithm || DEFAULTS.algorithm).split(',').map(function (s) { return s.trim(); }).filter(function (s) { return NAMES[s]; });
if (!algos.length) algos = ['astar'];
var density = d.walls !== undefined ? Math.max(0, Math.min(0.45, +d.walls)) : DEFAULTS.walls;
var diagonal = d.diagonal !== undefined && d.diagonal !== 'false';
var loop = d.loop !== 'false';
var w = 0, h = 0, dpr = 1, cell = 14, cols = 0, rows = 0, ox = 0, oy = 0, top = 0, speed = 100;
var walls = [], start = 0, goal = 0, algoIdx = 0;
var order = [], dist = [], seenAt = [], path = [], maxDist = 1;
var phase = 'search', phaseT = 0, shown = 0, acc = 0, clock = 0, fadeOut = 1;
function idx(x, y) { return y * cols + x; }
function neighbours(i) {
var x = i % cols, y = (i / cols) | 0, out = [];
var steps = diagonal ? [[1, 0], [-1, 0], [0, 1], [0, -1], [1, 1], [1, -1], [-1, 1], [-1, -1]] : [[1, 0], [-1, 0], [0, 1], [0, -1]];
for (var k = 0; k < steps.length; k++) {
var nx = x + steps[k][0], ny = y + steps[k][1];
if (nx < 0 || ny < 0 || nx >= cols || ny >= rows) continue;
var j = idx(nx, ny);
if (walls[j]) continue;
// No cutting corners between two walls.
if (k >= 4 && (walls[idx(nx, y)] || walls[idx(x, ny)])) continue;
out.push([j, k >= 4 ? Math.SQRT2 : 1]);
}
return out;
}
function guess(i) {
var dx = Math.abs(i % cols - goal % cols), dy = Math.abs(((i / cols) | 0) - ((goal / cols) | 0));
return diagonal ? Math.max(dx, dy) + (Math.SQRT2 - 1) * Math.min(dx, dy) : dx + dy;
}
// Run the search in one go, remembering the order cells were reached so it can be replayed.
function search(kind) {
var n = cols * rows, g = [], parent = [], closed = [], open = [start];
for (var i = 0; i < n; i++) { g.push(Infinity); parent.push(-1); closed.push(false); }
g[start] = 0;
order = []; dist = [];
while (open.length) {
var best = 0, bestScore = Infinity, bestH = Infinity;
for (var o = 0; o < open.length; o++) {
var c = open[o], hh = kind === 'dijkstra' ? 0 : guess(c);
var score = kind === 'greedy' ? hh : g[c] + hh;
if (score < bestScore - 1e-9 || (Math.abs(score - bestScore) < 1e-9 && hh < bestH)) { best = o; bestScore = score; bestH = hh; }
}
var cur = open.splice(best, 1)[0];
if (closed[cur]) continue;
closed[cur] = true;
order.push(cur);
dist.push(g[cur]);
if (cur === goal) break;
var nb = neighbours(cur);
for (var k = 0; k < nb.length; k++) {
var j = nb[k][0], ng = g[cur] + nb[k][1];
if (!closed[j] && ng < g[j]) { g[j] = ng; parent[j] = cur; open.push(j); }
}
}
path = [];
if (closed[goal]) for (var p = goal; p !== -1; p = parent[p]) path.unshift(p);
maxDist = 1;
for (var q = 0; q < dist.length; q++) maxDist = Math.max(maxDist, dist[q]);
seenAt = [];
for (q = 0; q < n; q++) seenAt.push(-1);
}
function reachable() {
var seen = [], queue = [start];
seen[start] = true;
while (queue.length) {
var c = queue.shift();
if (c === goal) return true;
neighbours(c).forEach(function (nb) { if (!seen[nb[0]]) { seen[nb[0]] = true; queue.push(nb[0]); } });
}
return false;
}
// Walls in short straight runs, which read as a maze better than scattered blocks.
function newWalls() {
for (var tries = 0; tries < 30; tries++) {
walls = [];
for (var i = 0; i < cols * rows; i++) walls.push(false);
var target = cols * rows * density * (1 - tries / 40), placed = 0, guard = 0;
while (placed < target && guard++ < 5000) {
var x = Math.floor(Math.random() * cols), y = Math.floor(Math.random() * rows);
var horiz = Math.random() < 0.5, len = 2 + Math.floor(Math.random() * 6);
for (var k = 0; k < len; k++) {
var xx = horiz ? x + k : x, yy = horiz ? y : y + k;
if (xx >= cols || yy >= rows) break;
var j = idx(xx, yy);
if (!walls[j]) { walls[j] = true; placed++; }
}
}
var sx = Math.floor(Math.random() * Math.max(1, cols * 0.15)), sy = Math.floor(Math.random() * rows);
var gx = cols - 1 - Math.floor(Math.random() * Math.max(1, cols * 0.15)), gy = Math.floor(Math.random() * rows);
start = idx(sx, sy); goal = idx(gx, gy);
walls[start] = walls[goal] = false;
if (reachable()) return;
}
}
function run() {
search(algos[algoIdx % algos.length]);
phase = 'search'; phaseT = 0; shown = 0; acc = 0; fadeOut = 1;
}
function resize() {
var nw = el.clientWidth, nh = el.clientHeight;
if (nw === w && nh === h) return false;
w = nw; h = nh;
dpr = Math.min(2, window.devicePixelRatio || 1);
canvas.width = Math.round(w * dpr);
canvas.height = Math.round(h * dpr);
ctx.setTransform(dpr, 0, 0, dpr, 0, 0);
top = h < 260 ? 26 : 34;
cell = +d.cell || Math.max(10, Math.min(18, Math.round(Math.min(w, h - top) / 20)));
cols = Math.max(4, Math.floor((w - 16) / cell));
rows = Math.max(4, Math.floor((h - top - 10) / cell));
ox = Math.round((w - cols * cell) / 2);
oy = Math.round(top + (h - top - 10 - rows * cell) / 2);
speed = +d.speed || Math.max(40, cols * rows / 5);
newWalls();
run();
return true;
}
function rect(x, y, s, r) {
ctx.beginPath();
if (ctx.roundRect) ctx.roundRect(x, y, s, s, r);
else ctx.rect(x, y, s, s);
ctx.fill();
}
function draw() {
ctx.clearRect(0, 0, w, h);
var gap = cell > 12 ? 2 : 1, s = cell - gap, i, x, y;
for (i = 0; i < cols * rows; i++) {
x = ox + (i % cols) * cell; y = oy + ((i / cols) | 0) * cell;
ctx.fillStyle = walls[i] ? '#7d72a3' : 'rgba(255,255,255,.045)';
rect(x, y, s, 2);
}
// Searched cells pop in, coloured by how far they are from the start.
for (var k = 0; k < shown; k++) {
var c = order[k], age = Math.min(1, (clock - seenAt[c]) / 300);
var rgb = ramp(dist[k] / maxDist), sc = 0.35 + 0.65 * (1 - Math.pow(1 - age, 3));
var lift = (1 - age) * 0.7;
ctx.globalAlpha = fadeOut * (0.62 + lift * 0.38);
ctx.fillStyle = 'rgb(' + Math.round(rgb[0] + (255 - rgb[0]) * lift) + ',' + Math.round(rgb[1] + (255 - rgb[1]) * lift) + ',' + Math.round(rgb[2] + (255 - rgb[2]) * lift) + ')';
var ss = s * sc;
x = ox + (c % cols) * cell + (s - ss) / 2; y = oy + ((c / cols) | 0) * cell + (s - ss) / 2;
rect(x, y, ss, 2);
}
ctx.globalAlpha = 1;
// The path, drawn from the start to the goal.
if ((phase === 'path' || phase === 'hold' || phase === 'fade') && path.length > 1) {
var upto = phase === 'path' ? phaseT * (path.length - 1) : path.length - 1;
ctx.save();
ctx.globalAlpha = fadeOut;
ctx.strokeStyle = '#facc15';
ctx.shadowColor = '#facc15';
ctx.shadowBlur = 10;
ctx.lineWidth = Math.max(3, cell * 0.32);
ctx.lineCap = ctx.lineJoin = 'round';
ctx.beginPath();
for (var p = 0; p <= Math.floor(upto); p++) {
x = ox + (path[p] % cols) * cell + s / 2; y = oy + ((path[p] / cols) | 0) * cell + s / 2;
if (p) ctx.lineTo(x, y); else ctx.moveTo(x, y);
}
var f = upto - Math.floor(upto), nxt = path[Math.min(path.length - 1, Math.floor(upto) + 1)];
if (f > 0) {
ctx.lineTo(x + (ox + (nxt % cols) * cell + s / 2 - x) * f, y + (oy + ((nxt / cols) | 0) * cell + s / 2 - y) * f);
}
ctx.stroke();
ctx.restore();
}
// Start and goal.
[[start, '#34d399'], [goal, '#f472b6']].forEach(function (m) {
x = ox + (m[0] % cols) * cell + s / 2; y = oy + ((m[0] / cols) | 0) * cell + s / 2;
ctx.fillStyle = m[1];
ctx.shadowColor = m[1];
ctx.shadowBlur = 12;
ctx.beginPath();
ctx.arc(x, y, Math.max(4, cell * 0.48), 0, Math.PI * 2);
ctx.fill();
ctx.shadowBlur = 0;
ctx.fillStyle = '#fff';
ctx.beginPath();
ctx.arc(x, y, Math.max(1.5, cell * 0.17), 0, Math.PI * 2);
ctx.fill();
});
// Label.
var fs = h < 260 ? 11 : 13;
ctx.font = '600 ' + fs + 'px system-ui, sans-serif';
ctx.textBaseline = 'middle';
ctx.textAlign = 'left';
ctx.fillStyle = 'rgba(255,255,255,.92)';
var name = NAMES[algos[algoIdx % algos.length]];
ctx.fillText(name, ox, top / 2 + 1);
ctx.textAlign = 'right';
ctx.font = '500 ' + fs + 'px system-ui, sans-serif';
ctx.fillStyle = 'rgba(255,255,255,.6)';
var info = shown + ' searched';
if (phase !== 'search') info += path.length ? ' · path ' + (path.length - 1) : ' · no path';
ctx.fillText(info, ox + cols * cell - gap, top / 2 + 1);
}
resize();
if (reduced()) {
shown = order.length;
seenAt = seenAt.map(function () { return -1e9; });
phase = 'hold';
draw();
if (window.ResizeObserver) new ResizeObserver(function () {
if (resize()) { shown = order.length; seenAt = seenAt.map(function () { return -1e9; }); phase = 'hold'; draw(); }
}).observe(el);
return;
}
if (window.ResizeObserver) new ResizeObserver(function () { if (resize()) draw(); }).observe(el);
el.addEventListener('pointerdown', function (e) {
var b = el.getBoundingClientRect();
var cx = Math.floor((e.clientX - b.left - ox) / cell), cy = Math.floor((e.clientY - b.top - oy) / cell);
if (cx < 0 || cy < 0 || cx >= cols || cy >= rows) return;
var j = idx(cx, cy);
if (j === start) return;
walls[j] = false;
goal = j;
run();
});
var last = 0;
var timer = anime.createTimer({
loop: true,
duration: 1000,
autoplay: false,
onUpdate: function () {
var now = performance.now();
var dt = last ? Math.min(100, now - last) : 16;
last = now;
clock += dt;
if (phase === 'search') {
acc += dt / 1000 * speed;
while (acc >= 1 && shown < order.length) { seenAt[order[shown]] = clock; shown++; acc -= 1; }
if (shown >= order.length) { phase = 'path'; phaseT = 0; }
} else if (phase === 'path') {
phaseT += dt / Math.max(500, path.length * 28);
if (phaseT >= 1 || path.length < 2) { phase = 'hold'; phaseT = 0; }
} else if (phase === 'hold') {
phaseT += dt / 2200;
if (phaseT >= 1 && loop) { phase = 'fade'; phaseT = 0; }
} else if (phase === 'fade') {
phaseT += dt / 500;
fadeOut = Math.max(0, 1 - phaseT);
if (phaseT >= 1) {
algoIdx++;
// Every algorithm gets a turn on the same walls, then new walls.
if (algoIdx % algos.length === 0) newWalls();
run();
}
}
draw();
}
});
new IntersectionObserver(function (entries) {
if (entries[0].isIntersecting) { last = 0; timer.play(); } else timer.pause();
}).observe(el);
}
function init() {
document.querySelectorAll('[data-pathfinding-visualiser]').forEach(function (el) {
if (el._pfv) return;
el._pfv = true;
build(el);
});
}
if (document.readyState === 'loading') document.addEventListener('DOMContentLoaded', init);
else init();
})();
</script><div data-pathfinding-visualiser style="height: 360px; background: #120a24"></div>