A* Search — VisualAlgorithms Docs

How it works

A* is Dijkstra's algorithm guided by a heuristic. Each node is prioritized by f = g + h, where g is the known cost from the start and h is an estimate of the remaining cost to the goal. With an admissible heuristic it finds an optimal path while exploring far fewer nodes.

On a grid the Manhattan (or octile, for diagonal movement) distance is the usual heuristic.

Implementation

      
 function astarPathfind(grid, start, end, allowDiag, heuristicFn) {
  const rows = grid.length;
  const cols = grid[0].length;
  const h = heuristicFn || HEURISTICS.manhattan;
  const gScore = Matrix(rows, cols, Infinity);
  const visited = new Set();
  const prev = new Map();
  const heap = PriorityQueue("f");
  gScore[start[0]][start[1]] = 0;
  priorityQueuePush(heap, {
    f: h(start[0], start[1], end[0], end[1]),
    g: 0,
    row: start[0],
    col: start[1]
  });
  while (priorityQueueSize(heap)) {
    const __pattern1 = priorityQueuePop(heap);
    const cr = __pattern1.row;
    const cc = __pattern1.col;
    const cg = __pattern1.g;
    const currentKey = key(cr, cc);
    if (visited.has(currentKey)) continue;
    visited.add(currentKey);
    visitNode(cr, cc);
    if (cr === end[0] && cc === end[1]) {
      reconstructPath(prev, start, end);
      return;
    }
    for (const [nr, nc] of getNeighbors(grid, cr, cc, allowDiag)) {
      const neighborKey = key(nr, nc);
      if (visited.has(neighborKey)) continue;
      const ng = cg + stepCost(grid, cr, cc, nr, nc);
      if (ng < gScore[nr][nc]) {
        gScore[nr][nc] = ng;
        prev.set(neighborKey, [cr, cc]);
        priorityQueuePush(heap, {
          f: ng + h(nr, nc, end[0], end[1]),
          g: ng,
          row: nr,
          col: nc
        });
        pushFrontier(nr, nc);
      }
    }
  }
  reportNoPath();
} def astarPathfind(grid, start, end, allowDiag, heuristicFn):
    rows = grid.length
    cols = grid[0].length
    h = (heuristicFn or HEURISTICS.manhattan)
    gScore = Matrix(rows, cols, Infinity)
    visited = Set()
    prev = Map()
    heap = PriorityQueue("f")
    gScore[start[0]][start[1]] = 0
    priorityQueuePush(heap, {f: h(start[0], start[1], end[0], end[1]), g: 0, row: start[0], col: start[1]})
    while priorityQueueSize(heap):
        __pattern1 = priorityQueuePop(heap)
        cr = __pattern1.row
        cc = __pattern1.col
        cg = __pattern1.g
        currentKey = key(cr, cc)
        if visited.has(currentKey):
            continue
        visited.add(currentKey)
        visitNode(cr, cc)
        if ((cr == end[0]) and (cc == end[1])):
            reconstructPath(prev, start, end)
            return
        for nr, nc in getNeighbors(grid, cr, cc, allowDiag):
            neighborKey = key(nr, nc)
            if visited.has(neighborKey):
                continue
            ng = (cg + stepCost(grid, cr, cc, nr, nc))
            if (ng < gScore[nr][nc]):
                gScore[nr][nc] = ng
                prev.set(neighborKey, [cr, cc])
                priorityQueuePush(heap, {f: (ng + h(nr, nc, end[0], end[1])), g: ng, row: nr, col: nc})
                pushFrontier(nr, nc)
    reportNoPath() #include <vector>
#include <algorithm>
void astarPathfind(int grid, int start, int end, int allowDiag, int heuristicFn) {
    auto rows = grid.length;
    auto cols = grid[0].length;
    auto h = (heuristicFn || HEURISTICS.manhattan);
    auto gScore = Matrix(rows, cols, Infinity);
    auto visited = Set();
    auto prev = Map();
    auto heap = PriorityQueue("f");
    gScore[start[0]][start[1]] = 0;
    priorityQueuePush(heap, {f: h(start[0], start[1], end[0], end[1]), g: 0, row: start[0], col: start[1]});
    while(priorityQueueSize(heap)) {
        auto __pattern1 = priorityQueuePop(heap);
        auto cr = __pattern1.row;
        auto cc = __pattern1.col;
        auto cg = __pattern1.g;
        auto currentKey = key(cr, cc);
        if(visited.has(currentKey)) {
            continue;
        }
        visited.add(currentKey);
        visitNode(cr, cc);
        if(((cr == end[0]) && (cc == end[1]))) {
            reconstructPath(prev, start, end);
            return;
        }
        for(auto& [nr, nc] : getNeighbors(grid, cr, cc, allowDiag)) {
            auto neighborKey = key(nr, nc);
            if(visited.has(neighborKey)) {
                continue;
            }
            auto ng = (cg + stepCost(grid, cr, cc, nr, nc));
            if((ng < gScore[nr][nc])) {
                gScore[nr][nc] = ng;
                prev.set(neighborKey, [cr, cc]);
                priorityQueuePush(heap, {f: (ng + h(nr, nc, end[0], end[1])), g: ng, row: nr, col: nc});
                pushFrontier(nr, nc);
            }
        }
    }
    reportNoPath();
} public void astarPathfind(int grid, int start, int end, int allowDiag, int heuristicFn) {
    var rows = grid.length;
    var cols = grid[0].length;
    var h = (heuristicFn || HEURISTICS.manhattan);
    var gScore = Matrix(rows, cols, Infinity);
    var visited = Set();
    var prev = Map();
    var heap = PriorityQueue("f");
    gScore[start[0]][start[1]] = 0;
    priorityQueuePush(heap, {f: h(start[0], start[1], end[0], end[1]), g: 0, row: start[0], col: start[1]});
    while(priorityQueueSize(heap)) {
        var __pattern1 = priorityQueuePop(heap);
        var cr = __pattern1.row;
        var cc = __pattern1.col;
        var cg = __pattern1.g;
        var currentKey = key(cr, cc);
        if(visited.has(currentKey)) {
            continue;
        }
        visited.add(currentKey);
        visitNode(cr, cc);
        if(((cr == end[0]) && (cc == end[1]))) {
            reconstructPath(prev, start, end);
            return;
        }
        foreach(var (nr, nc) in getNeighbors(grid, cr, cc, allowDiag)) {
            var neighborKey = key(nr, nc);
            if(visited.has(neighborKey)) {
                continue;
            }
            var ng = (cg + stepCost(grid, cr, cc, nr, nc));
            if((ng < gScore[nr][nc])) {
                gScore[nr][nc] = ng;
                prev.set(neighborKey, [cr, cc]);
                priorityQueuePush(heap, {f: (ng + h(nr, nc, end[0], end[1])), g: ng, row: nr, col: nc});
                pushFrontier(nr, nc);
            }
        }
    }
    reportNoPath();
} #include <stdio.h>
void astarPathfind(int grid, int start, int end, int allowDiag, int heuristicFn) {
    var rows = grid.length;
    var cols = grid[0].length;
    var h = (heuristicFn || HEURISTICS.manhattan);
    var gScore = Matrix(rows, cols, Infinity);
    var visited = Set();
    var prev = Map();
    var heap = PriorityQueue("f");
    gScore[start[0]][start[1]] = 0;
    priorityQueuePush(heap, {f: h(start[0], start[1], end[0], end[1]), g: 0, row: start[0], col: start[1]});
    while(priorityQueueSize(heap)) {
        var __pattern1 = priorityQueuePop(heap);
        var cr = __pattern1.row;
        var cc = __pattern1.col;
        var cg = __pattern1.g;
        var currentKey = key(cr, cc);
        if(visited.has(currentKey)) {
            continue;
        }
        visited.add(currentKey);
        visitNode(cr, cc);
        if(((cr == end[0]) && (cc == end[1]))) {
            reconstructPath(prev, start, end);
            return;
        }
        for(int _fod_i = 0; _fod_i < getNeighbors(grid, cr, cc, allowDiag)_len; _fod_i++) {
            int nr = getNeighbors(grid, cr, cc, allowDiag)[_fod_i][0];
            int nc = getNeighbors(grid, cr, cc, allowDiag)[_fod_i][1];
            var neighborKey = key(nr, nc);
            if(visited.has(neighborKey)) {
                continue;
            }
            var ng = (cg + stepCost(grid, cr, cc, nr, nc));
            if((ng < gScore[nr][nc])) {
                gScore[nr][nc] = ng;
                prev.set(neighborKey, [cr, cc]);
                priorityQueuePush(heap, {f: (ng + h(nr, nc, end[0], end[1])), g: ng, row: nr, col: nc});
                pushFrontier(nr, nc);
            }
        }
    }
    reportNoPath();
} 

Advantages

Optimal with an admissible heuristic, and usually much faster than Dijkstra.
Tunable: the heuristic lets you trade optimality for speed when needed.

Disadvantages

Optimality depends on a well-chosen, admissible heuristic.
Memory use grows with the open set on large maps.

When to use it

The default for goal-directed pathfinding on grids and game maps whenever a good heuristic exists.