README
¶
AStar: High-Performance, Generic Solver for Go
A highly performant, fully generic A* solver for Go. Perfect for optimal pathfinding and abstract state-space search.
What is A*?
The A* (A-star) algorithm is a graph traversal and path search algorithm heavily used in computer science due to its completeness, optimality, and optimal efficiency. It is widely considered the best algorithm for finding the shortest path between nodes (e.g., in a 2D grid/map for game development).
While most commonly used as a Pathfinder, this library provides a completely domain-agnostic Solver. You can use it to solve complex puzzles, optimize network routing, or navigate grids, simply by providing your own Heuristic, Cost, and Successors functions.
⚡ Performance
This solver is built for extreme performance. By utilizing Go 1.18+ Generics, custom memory arenas, and highly optimized data structures, we drastically reduce memory allocations and prevent heap escapes during the hot path of the search.
Key Optimizations:
WithIndexedSliceDict: Replaces standard Go maps with a pre-allocated slice for tracking visited nodes. It completely eliminates hashing overhead and interface boxing.- Node Arena: An internal chunk-based memory arena ensures that millions of nodes can be processed with near-zero allocations after the initial setup.
Benchmarks (Apple M1 Max)
As the grid size increases, the IndexedSliceDict shows massive scaling advantages. It outperforms the default Go map implementation by nearly 2x on small grids, and scales up to over 4.3x faster execution times on large spaces (2048x2048), all while maintaining a perfectly flat memory allocation profile.
| Grid Size | Dictionary Type | Time (ns/op) | Memory (B/op) | Allocs (allocs/op) |
|---|---|---|---|---|
| 64x64 | IndexedSliceDict |
20,884 | 4,216 | 12 |
IndexedMapDict |
36,467 | 4,216 | 12 | |
DefaultMapDict |
38,557 | 4,216 | 12 | |
| 256x256 | IndexedSliceDict |
108,993 | 16,504 | 14 |
IndexedMapDict |
201,557 | 16,507 | 14 | |
DefaultMapDict |
209,424 | 16,505 | 14 | |
| 512x512 | IndexedSliceDict |
256,729 | 50,578 | 16 |
IndexedMapDict |
668,239 | 50,561 | 16 | |
DefaultMapDict |
804,137 | 50,563 | 16 | |
| 1024x1024 | IndexedSliceDict |
720,912 | 120,383 | 18 |
IndexedMapDict |
2,361,323 | 120,278 | 18 | |
DefaultMapDict |
3,084,423 | 120,306 | 18 | |
| 2048x2048 | IndexedSliceDict |
2,009,488 | 260,743 | 20 |
IndexedMapDict |
7,348,637 | 260,084 | 20 | |
DefaultMapDict |
8,680,021 | 260,230 | 20 |
🚀 Getting Started (Pathfinding Example)
Here is a step-by-step example of how to configure the solver to find the shortest path on a 2D grid.
Define your domain state
The solver is generic, so you define the state. For a map, a simple Point struct works best.
type Point struct {
X, Y int
}
Define the Rules (Heuristic, Cost, Successors)
You must define how the algorithm evaluates the distance to the goal, the cost of moving, and how to find neighboring states.
// 1. Heuristic: Estimates the distance to the goal (e.g., Manhattan distance)
const weight = 2.0 // Adjust this factor to make the heuristic more or less aggressive
heuristic := func(current, goal Point) float64 {
dx := math.Abs(float64(goal.X - current.X))
dy := math.Abs(float64(goal.Y - current.Y))
return (dx + dy) * weight
// Note: Multiply by a weight > 1.0 here to create a "Weighted A*",
// drastically increasing speed at the cost of absolute optimal paths.
}
// 2. Cost: The penalty for entering a specific node (e.g., a swamp is harder to cross than a road)
cost := func(p Point) float64 {
return 1.0 // Assume a flat cost for this example
}
// 3. Successors: Populates the buffer with valid moves from the current state
dirs := []Point{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
successors := func(p Point, buffer []Point) []Point {
for _, d := range dirs {
nx, ny := p.X+d.X, p.Y+d.Y
// Check bounds and avoid obstacles here
if nx >= 0 && nx < 64 && ny >= 0 && ny < 64 {
buffer = append(buffer, Point{X: nx, Y: ny})
}
}
return buffer
}
Initialize the Solver and Find the Path
Pass your rules into astar.New. To unlock maximum performance, use WithIndexedSliceDict by providing an Indexer that maps your state to a unique integer.
// The Indexer maps a 2D coordinate to a 1D slice index
indexer := func(p Point) int {
return p.Y * 64 + p.X
}
maxNodes := 64 * 64
// Initialize the Solver
finder := astar.New(heuristic, cost, successors,
astar.WithSuccessorCapacity[Point](4), // Pre-allocate buffer for 4 directions
astar.WithIndexedSliceDict(maxNodes, indexer),
)
start := Point{X: 0, Y: 0}
goal := Point{X: 63, Y: 63}
// Execute the search
finder.Solve(start, goal)
path := finder.Result()
if path != nil {
fmt.Println("Found path with length:", len(path))
}
Documentation
¶
Index ¶
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func NewBufferedSuccessors ¶
func NewBufferedSuccessors[T comparable](capacity int, generate SuccessorsFunc[T]) *bufferedSuccessors[T]
Types ¶
type Cost ¶
type Cost[T comparable] func(T) float64
Cost defines the exact penalty (weight) for moving into a given state. In a standard A* search, this value should be strictly accurate to guarantee optimal paths.
type Heuristic ¶
type Heuristic[T comparable] func(current, goal T) float64
Heuristic defines the estimated cost to reach the goal state from the current state.
Note on Performance vs. Optimality: To drastically narrow the search space and speed up the solver, the heuristic's contribution should dominate the actual step cost. You can achieve this by multiplying the heuristic result by a weight (e.g., > 1.0) or by reducing the output of the Cost function. This effectively turns the algorithm into Weighted A*, which visits far fewer nodes but sacrifices the guarantee of finding the absolute shortest path.
type Indexer ¶
type Indexer[T comparable] func(T) int
Indexer maps a complex state of type T to a unique, contiguous integer identifier. It is required when using highly optimized internal structures like IndexedSliceDict.
type Solver ¶
type Solver[T comparable] struct { // contains filtered or unexported fields }
Solver is a generic, high-performance pathfinding and state-space search engine based on the A* algorithm. It is entirely agnostic to the underlying domain problem.
func New ¶
func New[T comparable]( heuristic Heuristic[T], cost Cost[T], successors SuccessorsFunc[T], opts ...SolverOption[T], ) *Solver[T]
New initializes and returns a new Solver configured with the provided rules (heuristic, cost, and successors) and optional performance tuning parameters (SolverOptions).
func (*Solver[T]) Iter ¶
Iter returns a Go 1.23 iterator sequence that allows stepping through the algorithm's execution. It yields 'false' while actively searching, and 'true' the moment the goal is reached. This is exceptionally useful for visualizing the pathfinding process, debugging, or aborting the search early based on custom conditions.
Example (DefaultDict) ¶
package main
import (
"fmt"
"math"
"github.com/kjkrol/astar"
)
type Point struct {
X, Y int
}
func setupPathFinder(opts ...astar.SolverOption[Point]) (*astar.Solver[Point], Point, Point) {
const size = 64
const insurmountableObstacle = 100.0
grid := make([][]float64, size)
for y := range size {
grid[y] = make([]float64, size)
for x := range size {
val := float64(((x + y) % 5) + 1)
if x%4 == 2 && y%4 != 2 {
val = insurmountableObstacle
}
if (x == 0 && y == 0) || (x == size-1 && y == size-1) {
val = 1
}
grid[y][x] = val
}
}
start := Point{X: 0, Y: 0}
goal := Point{X: 63, Y: 63}
heuristic := func(p, g Point) float64 {
return (math.Abs(float64(g.X-p.X)) + math.Abs(float64(g.Y-p.Y))) * 10.0
}
cost := func(p Point) float64 {
return grid[p.Y][p.X]
}
dirs := []Point{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
var successors astar.SuccessorsFunc[Point] = func(p Point, buffer []Point) []Point {
for _, d := range dirs {
nx, ny := p.X+d.X, p.Y+d.Y
if nx >= 0 && nx < size && ny >= 0 && ny < size {
if grid[ny][nx] == insurmountableObstacle {
continue
}
buffer = append(buffer, Point{X: nx, Y: ny})
}
}
return buffer
}
pathFinder := astar.New(heuristic, cost, successors, opts...)
return pathFinder, start, goal
}
func main() {
pathFinder, start, goal := setupPathFinder()
var path []Point
for goalAchieved := range pathFinder.Iter(start, goal) {
if goalAchieved {
path = pathFinder.Result()
break
}
}
if len(path) > 0 {
fmt.Println("Path found:", true)
fmt.Println("Start is correct:", path[0] == start)
fmt.Println("Goal is correct:", path[len(path)-1] == goal)
fmt.Println("Path length >= 127:", len(path) >= 127)
} else {
fmt.Println("Path not found")
}
}
Output: Path found: true Start is correct: true Goal is correct: true Path length >= 127: true
Example (IndexedMapDict) ¶
package main
import (
"fmt"
"math"
"github.com/kjkrol/astar"
)
type Point struct {
X, Y int
}
func setupPathFinder(opts ...astar.SolverOption[Point]) (*astar.Solver[Point], Point, Point) {
const size = 64
const insurmountableObstacle = 100.0
grid := make([][]float64, size)
for y := range size {
grid[y] = make([]float64, size)
for x := range size {
val := float64(((x + y) % 5) + 1)
if x%4 == 2 && y%4 != 2 {
val = insurmountableObstacle
}
if (x == 0 && y == 0) || (x == size-1 && y == size-1) {
val = 1
}
grid[y][x] = val
}
}
start := Point{X: 0, Y: 0}
goal := Point{X: 63, Y: 63}
heuristic := func(p, g Point) float64 {
return (math.Abs(float64(g.X-p.X)) + math.Abs(float64(g.Y-p.Y))) * 10.0
}
cost := func(p Point) float64 {
return grid[p.Y][p.X]
}
dirs := []Point{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
var successors astar.SuccessorsFunc[Point] = func(p Point, buffer []Point) []Point {
for _, d := range dirs {
nx, ny := p.X+d.X, p.Y+d.Y
if nx >= 0 && nx < size && ny >= 0 && ny < size {
if grid[ny][nx] == insurmountableObstacle {
continue
}
buffer = append(buffer, Point{X: nx, Y: ny})
}
}
return buffer
}
pathFinder := astar.New(heuristic, cost, successors, opts...)
return pathFinder, start, goal
}
func main() {
indexer := func(p Point) int { return p.Y*64 + p.X }
pathFinder, start, goal := setupPathFinder(
astar.WithInitCapacity[Point](64*64),
astar.WithIndexedMapDict(indexer),
)
var path []Point
for goalAchieved := range pathFinder.Iter(start, goal) {
if goalAchieved {
path = pathFinder.Result()
break
}
}
if len(path) > 0 {
fmt.Println("Path found:", true)
fmt.Println("Start is correct:", path[0] == start)
fmt.Println("Goal is correct:", path[len(path)-1] == goal)
fmt.Println("Path length >= 127:", len(path) >= 127)
} else {
fmt.Println("Path not found")
}
}
Output: Path found: true Start is correct: true Goal is correct: true Path length >= 127: true
Example (IndexedSliceDict) ¶
package main
import (
"fmt"
"math"
"github.com/kjkrol/astar"
)
type Point struct {
X, Y int
}
func setupPathFinder(opts ...astar.SolverOption[Point]) (*astar.Solver[Point], Point, Point) {
const size = 64
const insurmountableObstacle = 100.0
grid := make([][]float64, size)
for y := range size {
grid[y] = make([]float64, size)
for x := range size {
val := float64(((x + y) % 5) + 1)
if x%4 == 2 && y%4 != 2 {
val = insurmountableObstacle
}
if (x == 0 && y == 0) || (x == size-1 && y == size-1) {
val = 1
}
grid[y][x] = val
}
}
start := Point{X: 0, Y: 0}
goal := Point{X: 63, Y: 63}
heuristic := func(p, g Point) float64 {
return (math.Abs(float64(g.X-p.X)) + math.Abs(float64(g.Y-p.Y))) * 10.0
}
cost := func(p Point) float64 {
return grid[p.Y][p.X]
}
dirs := []Point{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
var successors astar.SuccessorsFunc[Point] = func(p Point, buffer []Point) []Point {
for _, d := range dirs {
nx, ny := p.X+d.X, p.Y+d.Y
if nx >= 0 && nx < size && ny >= 0 && ny < size {
if grid[ny][nx] == insurmountableObstacle {
continue
}
buffer = append(buffer, Point{X: nx, Y: ny})
}
}
return buffer
}
pathFinder := astar.New(heuristic, cost, successors, opts...)
return pathFinder, start, goal
}
func main() {
indexer := func(p Point) int { return p.Y*64 + p.X }
pathFinder, start, goal := setupPathFinder(
astar.WithIndexedSliceDict(64*64, indexer),
)
var path []Point
for goalAchieved := range pathFinder.Iter(start, goal) {
if goalAchieved {
path = pathFinder.Result()
break
}
}
if len(path) > 0 {
fmt.Println("Path found:", true)
fmt.Println("Start is correct:", path[0] == start)
fmt.Println("Goal is correct:", path[len(path)-1] == goal)
fmt.Println("Path length >= 127:", len(path) >= 127)
} else {
fmt.Println("Path not found")
}
}
Output: Path found: true Start is correct: true Goal is correct: true Path length >= 127: true
func (*Solver[T]) Result ¶
func (a *Solver[T]) Result() []T
Result reconstructs and returns the path from the starting state to the current state. It is typically called immediately after the Iter sequence yields 'true'.
func (*Solver[T]) Solve ¶
func (a *Solver[T]) Solve(start, goal T) []T
Solve executes the search from the start state to the goal state. It runs the iterator to completion and returns the final path. If no path is found, it returns nil.
Example (DefaultDict) ¶
package main
import (
"fmt"
"math"
"github.com/kjkrol/astar"
)
type Point struct {
X, Y int
}
func setupPathFinder(opts ...astar.SolverOption[Point]) (*astar.Solver[Point], Point, Point) {
const size = 64
const insurmountableObstacle = 100.0
grid := make([][]float64, size)
for y := range size {
grid[y] = make([]float64, size)
for x := range size {
val := float64(((x + y) % 5) + 1)
if x%4 == 2 && y%4 != 2 {
val = insurmountableObstacle
}
if (x == 0 && y == 0) || (x == size-1 && y == size-1) {
val = 1
}
grid[y][x] = val
}
}
start := Point{X: 0, Y: 0}
goal := Point{X: 63, Y: 63}
heuristic := func(p, g Point) float64 {
return (math.Abs(float64(g.X-p.X)) + math.Abs(float64(g.Y-p.Y))) * 10.0
}
cost := func(p Point) float64 {
return grid[p.Y][p.X]
}
dirs := []Point{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
var successors astar.SuccessorsFunc[Point] = func(p Point, buffer []Point) []Point {
for _, d := range dirs {
nx, ny := p.X+d.X, p.Y+d.Y
if nx >= 0 && nx < size && ny >= 0 && ny < size {
if grid[ny][nx] == insurmountableObstacle {
continue
}
buffer = append(buffer, Point{X: nx, Y: ny})
}
}
return buffer
}
pathFinder := astar.New(heuristic, cost, successors, opts...)
return pathFinder, start, goal
}
func main() {
pathFinder, start, goal := setupPathFinder()
path := pathFinder.Solve(start, goal)
if len(path) > 0 {
fmt.Println("Path found:", true)
fmt.Println("Start is correct:", path[0] == start)
fmt.Println("Goal is correct:", path[len(path)-1] == goal)
fmt.Println("Path length >= 127:", len(path) >= 127)
} else {
fmt.Println("Path not found")
}
}
Output: Path found: true Start is correct: true Goal is correct: true Path length >= 127: true
Example (IndexedMapDict) ¶
package main
import (
"fmt"
"math"
"github.com/kjkrol/astar"
)
type Point struct {
X, Y int
}
func setupPathFinder(opts ...astar.SolverOption[Point]) (*astar.Solver[Point], Point, Point) {
const size = 64
const insurmountableObstacle = 100.0
grid := make([][]float64, size)
for y := range size {
grid[y] = make([]float64, size)
for x := range size {
val := float64(((x + y) % 5) + 1)
if x%4 == 2 && y%4 != 2 {
val = insurmountableObstacle
}
if (x == 0 && y == 0) || (x == size-1 && y == size-1) {
val = 1
}
grid[y][x] = val
}
}
start := Point{X: 0, Y: 0}
goal := Point{X: 63, Y: 63}
heuristic := func(p, g Point) float64 {
return (math.Abs(float64(g.X-p.X)) + math.Abs(float64(g.Y-p.Y))) * 10.0
}
cost := func(p Point) float64 {
return grid[p.Y][p.X]
}
dirs := []Point{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
var successors astar.SuccessorsFunc[Point] = func(p Point, buffer []Point) []Point {
for _, d := range dirs {
nx, ny := p.X+d.X, p.Y+d.Y
if nx >= 0 && nx < size && ny >= 0 && ny < size {
if grid[ny][nx] == insurmountableObstacle {
continue
}
buffer = append(buffer, Point{X: nx, Y: ny})
}
}
return buffer
}
pathFinder := astar.New(heuristic, cost, successors, opts...)
return pathFinder, start, goal
}
func main() {
indexer := func(p Point) int { return p.Y*64 + p.X }
pathFinder, start, goal := setupPathFinder(
astar.WithInitCapacity[Point](64*64),
astar.WithIndexedMapDict(indexer),
)
path := pathFinder.Solve(start, goal)
if len(path) > 0 {
fmt.Println("Path found:", true)
fmt.Println("Start is correct:", path[0] == start)
fmt.Println("Goal is correct:", path[len(path)-1] == goal)
fmt.Println("Path length >= 127:", len(path) >= 127)
} else {
fmt.Println("Path not found")
}
}
Output: Path found: true Start is correct: true Goal is correct: true Path length >= 127: true
Example (IndexedSliceDict) ¶
package main
import (
"fmt"
"math"
"github.com/kjkrol/astar"
)
type Point struct {
X, Y int
}
func setupPathFinder(opts ...astar.SolverOption[Point]) (*astar.Solver[Point], Point, Point) {
const size = 64
const insurmountableObstacle = 100.0
grid := make([][]float64, size)
for y := range size {
grid[y] = make([]float64, size)
for x := range size {
val := float64(((x + y) % 5) + 1)
if x%4 == 2 && y%4 != 2 {
val = insurmountableObstacle
}
if (x == 0 && y == 0) || (x == size-1 && y == size-1) {
val = 1
}
grid[y][x] = val
}
}
start := Point{X: 0, Y: 0}
goal := Point{X: 63, Y: 63}
heuristic := func(p, g Point) float64 {
return (math.Abs(float64(g.X-p.X)) + math.Abs(float64(g.Y-p.Y))) * 10.0
}
cost := func(p Point) float64 {
return grid[p.Y][p.X]
}
dirs := []Point{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
var successors astar.SuccessorsFunc[Point] = func(p Point, buffer []Point) []Point {
for _, d := range dirs {
nx, ny := p.X+d.X, p.Y+d.Y
if nx >= 0 && nx < size && ny >= 0 && ny < size {
if grid[ny][nx] == insurmountableObstacle {
continue
}
buffer = append(buffer, Point{X: nx, Y: ny})
}
}
return buffer
}
pathFinder := astar.New(heuristic, cost, successors, opts...)
return pathFinder, start, goal
}
func main() {
indexer := func(p Point) int { return p.Y*64 + p.X }
pathFinder, start, goal := setupPathFinder(
astar.WithIndexedSliceDict(64*64, indexer),
)
path := pathFinder.Solve(start, goal)
if len(path) > 0 {
fmt.Println("Path found:", true)
fmt.Println("Start is correct:", path[0] == start)
fmt.Println("Goal is correct:", path[len(path)-1] == goal)
fmt.Println("Path length >= 127:", len(path) >= 127)
} else {
fmt.Println("Path not found")
}
}
Output: Path found: true Start is correct: true Goal is correct: true Path length >= 127: true
type SolverOption ¶
type SolverOption[T comparable] func(*config[T])
SolverOption configures the internal behavior and data structures of the Solver.
func WithIndexedMapDict ¶
func WithIndexedMapDict[T comparable](indexer Indexer[T]) SolverOption[T]
WithIndexedMapDict configures the solver to use standard Go maps backed by an Indexer function. By mapping complex state types to simple integer keys, it bypasses Go's interface boxing and complex hashing overhead.
This provides a noticeable performance boost (often in the double-digit percentages) compared to the default map implementation, while remaining more memory-efficient than slice-based dictionaries for problems with sparse state spaces.
func WithIndexedSliceDict ¶
func WithIndexedSliceDict[T comparable](maxSize int, indexer Indexer[T]) SolverOption[T]
WithIndexedSliceDict configures the solver to use slice-based dictionaries for its internal "open" and "closed" sets. Because the underlying slice does not grow dynamically, the provided maxSize must represent the absolute maximum number of possible states (nodes). It also requires an Indexer function to map node properties to contiguous integer indices.
This is the fastest dictionary implementation available, typically doubling the solver's overall performance by completely eliminating map hashing overhead and reducing memory allocations.
func WithInitCapacity ¶
func WithInitCapacity[T comparable](capacity int) SolverOption[T]
WithInitCapacity sets the initial capacity for the solver's internal data structures, such as dictionaries and memory arenas. Providing an accurate estimate prevents costly dynamic allocations during the search execution. If the capacity is exceeded, the underlying structures will automatically grow (typically doubling their size).
func WithSuccessorCapacity ¶
func WithSuccessorCapacity[T comparable](capacity int) SolverOption[T]
WithSuccessorCapacity pre-allocates the internal buffer used for fetching neighbor nodes. Setting this to the maximum expected number of successors per node (e.g., 4 or 8 for 2D grids) guarantees zero allocations for successor retrieval from the very first search iteration.
type SuccessorsFunc ¶
type SuccessorsFunc[T comparable] func(current T, buffer []T) []T
SuccessorsFunc defines the rules of movement or state transitions. It populates the provided buffer with all valid, reachable neighbors from the current state and returns it. This is the ideal place to filter out unreachable nodes (like walls or obstacles).
Source Files