To find the shortest path without exploring the whole map, add a hunch: at each step prefer the option that looks closest to the goal. If the hunch never overestimates, A* is guaranteed to find the true shortest path — while touching far fewer cells than blind search. Its cost bookkeeping is array work, which runs in real I-13.
THE TECHNIQUE f = g + h : cost-so-far plus a hunch
Each cell gets g (known cost from start) and h (a guess of cost to goal — here Manhattan distance). Always expand the frontier cell with the smallest f = g + h. Because h never overestimates, the first time the goal is reached, it is optimal. Watch it aim. live demo
HISTORY & CREDIT born to move a robot across a room
Taught as pure theory — it was built to make a chess program real robot stop bumping into things. cited
1968 · Peter Hart, Nils Nilsson & Bertram Raphael at SRI publish A* while building Shakey, the first mobile robot to reason about its own actions. the guarantee · if the heuristic h is admissible (never overestimates the true remaining cost), A* returns an optimal path; if also consistent, it never re-expands a node. the family · set h = 0 and A* becomes Dijkstra; a good h is what turns an exhaustive sweep into a beeline. Nilsson went on to help found the field of AI itself.
Every game unit that walks to where you click is running a descendant of Shakey. everywhere
RECOMMEND FOR I-13 the cost table runs; the frontier wants a heap
A*’s g-scores are an array, updated by relaxation just like Bellman–Ford (dart 046). That part runs:
$ i13 run astar.i13 # relax g over a grid-graph array
gStart_to_3 = 3 # best cost start -> node 3 (via 0-1-2-3)
gStart_to_4 = 4
Recommend: the cost bookkeeping is a no-wall on the array. The one piece that strains is the priority queue — A* repeatedly pulls the lowest-f frontier cell, which wants a binary heap for speed. A heap is array-backed (it runs), but efficient sift-up/down is happiest with in-place swaps and paired returns — nudging the same multiple-return frontier darts 045/048 named. Honest note: with a linear scan for the minimum (no heap), A* runs today, just at O(n) per step. The array made the map expressible; a heap type would make it fast.