A Star Search Algorithm from Scratch (2026)
A* (A-Star) is a best-first search algorithm that finds the shortest path from a start to a goal using a heuristic function. It combines the actual cost from the start with an estimated cost to the goal: f(n) = g(n) + h(n).
When the heuristic is admissible (never overestimates the true cost), A* is guaranteed to find the optimal path and is more efficient than Dijkstra for goal-directed search.
A* Algorithm with Admissible Heuristic
A* maintains an open set (priority queue) of frontier nodes ordered by f(n). It expands the node with the smallest f value, updating g-scores of neighbors. The algorithm terminates when the goal is popped from the open set.
Common admissible heuristics include Euclidean distance, Manhattan distance, and octile distance for grid-based pathfinding.
int aStar(vector>& grid, pair start, pair goal) {
int R = grid.size(), C = grid[0].size();
auto heuristic = [&](int x, int y) { return abs(x - goal.first) + abs(y - goal.second); };
priority_queue, vector>, greater<>> pq;
vector> g(R, vector(C, INT_MAX));
pq.push({0, start.first, start.second});
g[start.first][start.second] = 0;
int dirs[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
while (!pq.empty()) {
auto [f, x, y] = pq.top(); pq.pop();
if (x == goal.first && y == goal.second) return g[x][y];
if (f > g[x][y] + heuristic(x, y)) continue;
for (auto [dx, dy] : dirs) {
int nx = x + dx, ny = y + dy;
if (nx >= 0 && nx < R && ny >= 0 && ny < C && grid[nx][ny] == 0) {
int ng = g[x][y] + 1;
if (ng < g[nx][ny]) {
g[nx][ny] = ng;
pq.push({ng + heuristic(nx, ny), nx, ny});
}
}
}
}
return -1;
} Frequently Asked Questions
What makes a heuristic admissible?
A heuristic is admissible if it never overestimates the actual cost to reach the goal. For grid pathfinding, Manhattan distance is admissible when movement is only cardinal, and Euclidean distance is always admissible.
How does A* compare to Dijkstra?
A* is Dijkstra with a heuristic. Dijkstra (h=0) explores equally in all directions. A* with a good heuristic focuses search toward the goal, drastically reducing explored nodes while preserving optimality.
Originally published on Ayodhyyya. Last updated June 1, 2026.