A* finds the shortest path across a grid by ordering its search on steps already taken plus a guess at the steps still to go.
Strategy
Informed search, guided by a heuristic
Order the queue by steps taken plus a guess at the steps left, so the search leans toward the goal.
- Score: add the steps already taken to the guess at what remains.
- Choose: expand the square with the smallest total.
- Repeat: score its neighbors and go again until the goal comes off the queue.
Step the search and watch it lean toward the goal. Cyan squares show their score.
Purpose
Find the shortest path between two squares on a map with obstacles in the way.
Input
A grid, a start point and a goal point.
Output
The route as a []point, along with how many steps it takes.
Constraints
- The guess has to stay under the real remaining distance, or the route can come out too long.
- Manhattan distance is the guess to use while moves are limited to four directions.
- A goal with no open route leaves the queue empty and the path nil.
How A* works
It counts the steps taken to reach each square and adds a guess at how many remain. Ordering by that total pulls the search toward the goal. The guess has to stay under the real remaining distance, or the route it settles on can be too long.
What A* keeps track of
| Name | Type | What it is for |
|---|---|---|
| point | struct{ X, Y int } | One square on the grid. |
| grid | [][]int | The map. 0 is open floor, 1 is a wall. |
| steps | map[point]int | How many steps it took to reach each square. |
| guess | func(a, b point) int | The estimated distance still to go. |
| prev | map[point]point | The square you came from, which rebuilds the route. |
| queue | container/heap | Hands back the square with the smallest steps-plus-guess. |
Walk through it
1 Lay out the map and say where you can step
A square is open when it is on the grid and not a wall. Four neighbors, no diagonals.
var grid = [][]int{
{0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 1, 1, 1, 1, 0, 0},
{0, 0, 1, 0, 0, 0, 0, 0},
{0, 0, 1, 0, 1, 1, 1, 0},
{0, 0, 0, 0, 1, 0, 0, 0},
}
func open(p point) bool {
return p.Y >= 0 && p.Y < len(grid) &&
p.X >= 0 && p.X < len(grid[0]) &&
grid[p.Y][p.X] == 0
}2 Guess how far is left
The grid walk to the goal with nothing in the way. Walls only make the real journey longer, so the guess stays under the truth.
func guess(a, b point) int {
return abs(a.X-b.X) + abs(a.Y-b.Y)
}3 Order the queue by steps taken plus steps guessed
The start goes in on guesswork alone, since no steps are taken yet.
steps := map[point]int{start: 0}
prev := map[point]point{}
q := &queue{{start, guess(start, goal)}}
heap.Init(q)4 Take the most promising square and look around it
Every neighbor costs one step more than the square you stand on. When that beats its best so far, record it and queue it.
for q.Len() > 0 {
cur := heap.Pop(q).(item).at
if cur == goal {
break
}
for _, next := range neighbors(cur) {
taken := steps[cur] + 1
if best, seen := steps[next]; !seen || taken < best {
steps[next] = taken
prev[next] = cur
heap.Push(q, item{next, taken + guess(next, goal)})
}
}
}5 Walk back from the goal to get the route
prev holds the square you came from, so follow it back and reverse.
route := []point{goal}
for at := goal; at != start; {
at = prev[at]
route = append([]point{at}, route...)
}The whole program
The route from the top left to the bottom right, and how many squares it looked at.
package main
import (
"container/heap"
"fmt"
)
type point struct{ X, Y int }
// grid is the map. 0 is open floor, 1 is a wall.
var grid = [][]int{
{0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 1, 1, 1, 1, 0, 0},
{0, 0, 1, 0, 0, 0, 0, 0},
{0, 0, 1, 0, 1, 1, 1, 0},
{0, 0, 0, 0, 1, 0, 0, 0},
}
func abs(n int) int {
if n < 0 {
return -n
}
return n
}
// guess is the heuristic: the grid walk to the goal if nothing were in the
// way. It never overestimates, which is what keeps the answer shortest.
func guess(a, b point) int {
return abs(a.X-b.X) + abs(a.Y-b.Y)
}
// open reports whether p is on the grid and not a wall.
func open(p point) bool {
return p.Y >= 0 && p.Y < len(grid) && p.X >= 0 && p.X < len(grid[0]) && grid[p.Y][p.X] == 0
}
func neighbors(p point) []point {
var out []point
for _, n := range []point{{p.X + 1, p.Y}, {p.X - 1, p.Y}, {p.X, p.Y + 1}, {p.X, p.Y - 1}} {
if open(n) {
out = append(out, n)
}
}
return out
}
// item is a square waiting to be explored, ordered by steps taken plus
// steps guessed.
type item struct {
at point
score int
}
type queue []item
func (q queue) Len() int { return len(q) }
func (q queue) Less(i, j int) bool { return q[i].score < q[j].score }
func (q queue) Swap(i, j int) { q[i], q[j] = q[j], q[i] }
func (q *queue) Push(x any) { *q = append(*q, x.(item)) }
func (q *queue) Pop() any {
old := *q
last := old[len(old)-1]
*q = old[:len(old)-1]
return last
}
// FindPath returns the shortest route from start to goal, and how many
// squares were taken off the queue getting there.
func FindPath(start, goal point) ([]point, int) {
steps := map[point]int{start: 0}
prev := map[point]point{}
visited := 0
q := &queue{{start, guess(start, goal)}}
heap.Init(q)
for q.Len() > 0 {
cur := heap.Pop(q).(item).at
visited++
if cur == goal {
break
}
for _, next := range neighbors(cur) {
taken := steps[cur] + 1
if best, seen := steps[next]; !seen || taken < best {
steps[next] = taken
prev[next] = cur
heap.Push(q, item{next, taken + guess(next, goal)})
}
}
}
if _, ok := steps[goal]; !ok {
return nil, visited
}
route := []point{goal}
for at := goal; at != start; {
at = prev[at]
route = append([]point{at}, route...)
}
return route, visited
}
func main() {
start := point{0, 0}
goal := point{7, 4}
route, visited := FindPath(start, goal)
fmt.Println(len(route)-1, "steps")
fmt.Println(visited, "squares taken off the queue")
fmt.Println(route)
}$ go run main.go
11 steps
24 squares taken off the queue
[{0 0} {1 0} {2 0} {3 0} {4 0} {5 0} {6 0} {7 0} {7 1} {7 2} {7 3} {7 4}]