Optimal Grid Navigation with the A-Star Pathfinding Algorithm in JavaScript
Pathfinding across discrete spatial graphs is a cornerstone challenge in robotics, game engine engineering, and logistics planning. While foundational graph search algorithms like Breadth-First Search and Dijkstra's algorithm guarantee discovery of the shortest path, they explore nodes uniformly in all radial directions without any awareness of the goal's location. Conversely, Greedy Best-First Search rapidly drives toward the target using heuristic distance but frequently produces convoluted routes or gets trapped by concave obstacles. The A* (A-Star) search algorithm resolves this dilemma by blending Dijkstra's formal path-cost tracking with heuristic-guided directional search, discovering mathematically optimal routes while evaluating a fraction of the search space.
The efficiency of A* stems from its evaluation function, expressed as f(n) = g(n) + h(n). In this formulation, g(n) represents the exact, accumulated movement cost from the starting coordinate to candidate node n, while h(n) is an admissible heuristic that estimates the cheapest path from node n to the designated target. For four-directional orthogonal grid topographies, Manhattan distance serves as an ideal admissible heuristic because it never overestimates the true remaining distance. By maintaining an open set of frontier nodes prioritized by f(n) alongside a closed set of evaluated coordinates, A* guarantees finding the shortest navigable path around barriers and maze structures.
Example
// Heuristic evaluation: f(n) = g(n) + h(n)
function manhattanDistance(nodeA, nodeB) {
return Math.abs(nodeA.x - nodeB.x) + Math.abs(nodeA.y - nodeB.y);
}
// Calculate total expected cost for node candidate
function calculateNodeScore(currentNode, targetNode, stepCost = 1) {
const g = currentNode.g + stepCost;
const h = manhattanDistance(currentNode, targetNode);
const f = g + h;
return { g, h, f };
}Implementation
/**
* A* 2D Grid Pathfinding Implementation in Modern JavaScript
*/
class PathNode {
constructor(x, y, isObstacle = false) {
this.x = x;
this.y = y;
this.isObstacle = isObstacle;
this.g = 0; // Cost from start along discovered path
this.h = 0; // Heuristic estimate to goal
this.f = 0; // Total evaluation score (g + h)
this.parent = null; // Pointer to reconstruct optimal route
}
}
class AStarGrid {
/**
* @param {number[][]} matrix 0 represents walkable cell, 1 represents obstacle
*/
constructor(matrix) {
this.height = matrix.length;
this.width = matrix[0].length;
this.grid = matrix.map((row, y) =>
row.map((cellValue, x) => new PathNode(x, y, cellValue === 1))
);
}
/**
* Admissible Manhattan distance heuristic with tie-breaker
*/
heuristic(nodeA, nodeB) {
const dx = Math.abs(nodeA.x - nodeB.x);
const dy = Math.abs(nodeA.y - nodeB.y);
// Standard Manhattan distance
const manhattan = dx + dy;
// Slight tie-breaker scale (0.1%) to favor direct lines toward target
// and prevent examining flat f-score nodes unnecessarily
return manhattan * 1.001;
}
/**
* Validates grid boundaries and passable status
*/
getNeighbors(node) {
const neighbors = [];
const directions = [
{ x: 0, y: -1 }, // North
{ x: 1, y: 0 }, // East
{ x: 0, y: 1 }, // South
{ x: -1, y: 0 } // West
];
for (const dir of directions) {
const nx = node.x + dir.x;
const ny = node.y + dir.y;
if (nx >= 0 && nx < this.width && ny >= 0 && ny < this.height) {
const candidate = this.grid[ny][nx];
if (!candidate.isObstacle) {
neighbors.push(candidate);
}
}
}
return neighbors;
}
/**
* Reconstructs node coordinate path from goal back to start
*/
reconstructPath(endNode) {
const path = [];
let current = endNode;
while (current !== null) {
path.push({ x: current.x, y: current.y });
current = current.parent;
}
return path.reverse();
}
/**
* Finds the shortest path between start and goal coordinates
* @param {Object} startPos Start coordinates with x and y
* @param {Object} goalPos Destination coordinates with x and y
* @returns {Array<Object> | null} Array of coordinate objects or null if blocked
*/
findPath(startPos, goalPos) {
const startNode = this.grid[startPos.y][startPos.x];
const goalNode = this.grid[goalPos.y][goalPos.x];
if (startNode.isObstacle || goalNode.isObstacle) {
return null;
}
// Set of nodes pending evaluation
const openSet = [startNode];
// Map tracking visited nodes using coordinate keys
const closedSet = new Set();
startNode.g = 0;
startNode.h = this.heuristic(startNode, goalNode);
startNode.f = startNode.h;
while (openSet.length > 0) {
// Find node with lowest f score in openSet
let lowestIndex = 0;
for (let i = 1; i < openSet.length; i++) {
if (openSet[i].f < openSet[lowestIndex].f) {
lowestIndex = i;
} else if (openSet[i].f === openSet[lowestIndex].f) {
// Tie-break favoring nodes closer to the target (lower h)
if (openSet[i].h < openSet[lowestIndex].h) {
lowestIndex = i;
}
}
}
const current = openSet.splice(lowestIndex, 1)[0];
// Goal reached
if (current.x === goalNode.x && current.y === goalNode.y) {
return this.reconstructPath(current);
}
closedSet.add(`${current.x},${current.y}`);
const neighbors = this.getNeighbors(current);
for (const neighbor of neighbors) {
const neighborKey = `${neighbor.x},${neighbor.y}`;
if (closedSet.has(neighborKey)) {
continue; // Already processed
}
// Distance between orthogonal neighbors is 1
const tentativeG = current.g + 1;
const inOpenSet = openSet.includes(neighbor);
if (!inOpenSet || tentativeG < neighbor.g) {
neighbor.parent = current;
neighbor.g = tentativeG;
neighbor.h = this.heuristic(neighbor, goalNode);
neighbor.f = neighbor.g + neighbor.h;
if (!inOpenSet) {
openSet.push(neighbor);
}
}
}
}
// No path available (target isolated by obstacles)
return null;
}
}
// ==========================================
// Example Execution
// ==========================================
// 0 = open, 1 = obstacle wall
const levelMap = [
[0, 0, 0, 0, 0, 0, 0],
[0, 1, 1, 1, 1, 1, 0],
[0, 0, 0, 0, 0, 1, 0],
[1, 1, 1, 0, 0, 1, 0],
[0, 0, 0, 0, 0, 0, 0]
];
const navigator = new AStarGrid(levelMap);
const route = navigator.findPath({ x: 0, y: 0 }, { x: 6, y: 4 });
console.log('Shortest Navigation Route:', route);
// Outputs: [{x:0,y:0}, {x:0,y:1 (avoided)}, ..., {x:6,y:4}]Main Point: The A* algorithm achieves provably optimal pathfinding by prioritizing nodes using both accumulated movement cost and an admissible heuristic distance toward the destination.
Credits
Photo by Pawel Czerwinski on Unsplash