Pathfinding visualizer

This website visualizes pathfinding algorithms.

Currently, available algorithms are Dijkstra, A* with several different heuristics, depth-first and greedy best-first.

A* is an extension of Dijkstra's algorithm and uses heuristics to determine which nodes should be visited next.

A* selects the path that minimizes f(n) = g(n) + h(n),
where n is the last node on the path, g(n) is the cost of the path from the start node to n, and h(n) is a heuristic that estimates the cost of the cheapest path from n to the goal.

A* octile distance

A* with octile distance heuristic is the best choice for this grid. It always finds a shortest path only on grids which allow moves in 8 directions and diagonal moves have a cost of SQRT(2).

Octile distance heuristic is defined by:

function(node, goal) {
    let dx = Math.abs(node.x - goal.x);
    let dy = Math.abs(node.y - goal.y);
    return dx + dy + (SQRT2 - 2) * Math.min(dx, dy);
}

Chebyshev distance is basically just octile distance, but diagonal moves have a cost of 1 compared to SQRT(2) of octile distance.

Read more on A* from Wikipedia or octile distance from Amit’s A* Pages.