When is A* guaranteed to find an optimal path?

When the heuristic never overestimates true remaining cost (admissible) and, for efficient implementations with a consistent h, ties are handled properly. Manhattan is admissible for 4-connected uniform grids; octile suits 8-connected diagonal moves.

How does greedy best-first differ from A*?

Greedy expands nodes by h alone and ignores g, so it can rush toward the goal through expensive terrain. A* balances sunk cost g with remaining estimate h via f = g + h.

Why do open and closed sets matter visually?

The open set is the frontier of candidates; the closed set has already been expanded. Their growth shows how much of the map each algorithm explores before committing to a path.

A* / Dijkstra Pathfinding (Grid)

Interactive 40×28 grid pathfinder: A* (f=g+h), Dijkstra, or greedy best-first; Manhattan / octile / Euclidean heuristics, 4- vs 8-connectivity, paint walls + weighted cells, watch open / closed sets expand.

About this model

Grid pathfinding searches for a low-cost route from start to goal on a 40×28 cell map. This simulator compares Dijkstra (uniform-cost search), A* with f = g + h, and greedy best-first search, using Manhattan, octile, or Euclidean heuristics and 4- or 8-connectivity. You paint walls and weighted cells while watching the open and closed sets expand. A* is optimally efficient among optimal algorithms when h is admissible; Dijkstra is the h = 0 special case; greedy follows h and can be fast but suboptimal. The model is discrete grid search without anytime repairing, jump-point optimization, or continuous visibility graphs. Change algorithm, heuristic, and connectivity to see expansion patterns and path cost trade-offs.

Who it's for: Algorithms, AI search, robotics path planning, and intermediate computer-science courses.

Key terms

A* search
Dijkstra algorithm
Heuristic
Open set
Grid pathfinding
Admissible heuristic

How it works

**Interactive A\* / Dijkstra / Greedy best-first pathfinding on a 40×28 grid. Pick A\* (f = g + h, optimal with admissible heuristic), Dijkstra (f = g, ignores the goal — optimal but explores everywhere), or Greedy best-first (f = h alone — fast but not optimal). Paint walls, drag the S / G markers, drop weighted cells (cost ×5), toggle 8-connectivity, and watch the open / closed sets expand frame-by-frame. Try a maze with Manhattan vs Euclidean** heuristic and 4- vs 8-connectivity to see how the heuristic biases the search.

Key equations

A*: f(n) = g(n) + h(n), open := min-heap by f

Manhattan h = |Δr| + |Δc|; Octile h = max + (√2−1)·min

Frequently asked questions

When is A* guaranteed to find an optimal path?: When the heuristic never overestimates true remaining cost (admissible) and, for efficient implementations with a consistent h, ties are handled properly. Manhattan is admissible for 4-connected uniform grids; octile suits 8-connected diagonal moves.
How does greedy best-first differ from A*?: Greedy expands nodes by h alone and ignores g, so it can rush toward the goal through expensive terrain. A* balances sunk cost g with remaining estimate h via f = g + h.
Why do open and closed sets matter visually?: The open set is the frontier of candidates; the closed set has already been expanded. Their growth shows how much of the map each algorithm explores before committing to a path.

Continue with similar topics in this category — or all 48 in Engineering.

View category →

NewSchool

Maze Generators + A* (Grid)

Launch Simulator

Perfect mazes on the same 40×28 cell lattice as the pathfinding lab: recursive backtracker, Wilson, Eller, or randomized Prim; then solve with Manhattan A* (4-neighbors). Paint walls or erase passages and move S/G.

NewSchool

Minimum Spanning Tree (Prim & Kruskal)

Launch Simulator

Random planar points, complete Euclidean-weighted graph: step through Prim from a root or Kruskal with union–find; compare total MST weight.

NewSchool

RRT Path Planner (grid)

Launch Simulator

Same 40×28 wall map as A*: random samples, nearest-neighbor steer, goal bias, collision-checked edges; grow an RRT and compare summary stats with one-click Manhattan A* baseline.

NewSchool

Beam Deflection: Unit Load Method

Launch Simulator

Simply supported Euler-Bernoulli beam with point load P and UDL w: closed-form deflection vs virtual-work unit-load integral.

NewSchool

Thin-Walled Pressure Vessel Stress

Launch Simulator

Cylinder vs sphere membrane stresses: hoop σθ, longitudinal σz, von Mises stress, r/t thin-wall check, and yield safety factor.

NewSchool

Planetary Gear Set

Launch Simulator

Sun, planets, internal ring: Willis equation, hold Sun/ring/carrier and compare speed ratios.

A* / Dijkstra Pathfinding (Grid)

About this model

How it works

Key equations

Frequently asked questions

Related simulators

Maze Generators + A* (Grid)

Minimum Spanning Tree (Prim & Kruskal)

RRT Path Planner (grid)

Beam Deflection: Unit Load Method

Thin-Walled Pressure Vessel Stress

Planetary Gear Set

A* / Dijkstra Pathfinding (Grid)

About this model

How it works

Key equations

Frequently asked questions