README
¶
kjkrol/astar
kjkrol/astart is 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 state-space search algorithm heavily used in computer science due to its completeness, optimality, and optimal efficiency. It is widely considered the industry standard for finding the shortest path or optimal sequence of transitions between nodes.
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 and Transitions logic. The Solver remains strictly agnostic of the underlying graph structure or domain-specific cost metrics, making it a universal state-space resolution engine.
📦 Installation
GOKe requires Go 1.23 or newer.
go get github.com/kjkrol/goke
⏱️ 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)
The benchmarks below represent execution metrics under standard A* operational stress (CostWeight_1.0), where the algorithm fully evaluates path costs and alternative routes.
As the state space expands, the IndexedSliceDict provides massive scaling advantages over map-based lookups. For a large 2048x2048 environment, it reduces execution time from 1.41 seconds down to just 0.54 seconds—outperforming the standard Go map implementation by 2.6x.
| Grid Size | Dictionary Type | Time (ms/op) | Memory (kB/op) | Allocs (allocs/op) |
|---|---|---|---|---|
| 64x64 | IndexedSliceDict |
0.36 ms | 4.2 kB | 12 |
IndexedMapDict |
0.58 ms | 4.1 kB | 12 | |
DefaultMapDict |
0.62 ms | 4.1 kB | 12 | |
| 256x256 | IndexedSliceDict |
6.85 ms | 33.2 kB | 14 |
IndexedMapDict |
10.98 ms | 16.2 kB | 14 | |
DefaultMapDict |
11.94 ms | 16.3 kB | 14 | |
| 512x512 | IndexedSliceDict |
30.15 ms | 388.3 kB | 16 |
IndexedMapDict |
59.11 ms | 49.8 kB | 16 | |
DefaultMapDict |
60.11 ms | 49.8 kB | 16 | |
| 1024x1024 | IndexedSliceDict |
126.10 ms | 6,253.1 kB | 21 |
IndexedMapDict |
288.12 ms | 124.6 kB | 21 | |
DefaultMapDict |
308.14 ms | 124.7 kB | 21 | |
| 2048x2048 | IndexedSliceDict |
541.76 ms | 98,545.3 kB | 34 |
IndexedMapDict |
1,411.57 ms | 324.5 kB | 34 | |
DefaultMapDict |
1,416.12 ms | 324.5 kB | 34 |
🚀 Getting Started (Pathfinding Example)
Here is a step-by-step example of how to configure the solver to find the optimal path on a 2D terrain grid.
Define your domain state and world grid
The solver is generic, so you define the state representation. For a grid map, a Point struct represents coordinates, and a 2D slice simulates the world terrain.
type Point struct {
X, Y int
}
const (
GridSize = 64
// Terrain types and their cost/weights
TerrainWalkway = 1.0
TerrainMud = 3.5
TerrainWall = 999.0 // Insurmountable obstacle
)
// Example world grid layout (pre-allocated or loaded from game data)
var grid [GridSize][GridSize]float64
Define the Rules (Heuristic & Transitions)
You must define how the algorithm estimates the remaining distance to the goal and how states mutate based on your grid topography.
// 1. Heuristic: Estimates the distance to the goal (e.g., Manhattan distance)
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
}
// 2. Transitions: Populates the buffer with valid moves and their terrain costs in a single pass.
dirs := []Point{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
transitions := func(p, pp Point, buffer []astar.Transition[Point]) []astar.Transition[Point] {
for _, d := range dirs {
nx, ny := p.X+d.X, p.Y+d.Y
// 1. Boundary check
if nx >= 0 && nx < GridSize && ny >= 0 && ny < GridSize {
// 2. Prevent immediate backtracking to the parent node
if nx == pp.X && ny == pp.Y {
continue
}
// 3. Static obstacle pruning (e.g., skip walls entirely)
terrainCost := grid[ny][nx]
if terrainCost >= TerrainWall {
continue
}
// 4. Register valid transition with its intrinsic edge weight
buffer = append(buffer, astar.Transition[Point]{
To: Point{X: nx, Y: ny},
Cost: terrainCost,
})
}
}
return buffer
}
Initialize the Solver and Find the Path
Pass your static heuristic into astar.New. To unlock maximum performance on fixed state spaces, use WithIndexedSliceDict by providing an indexer function mapped to your grid dimensions.
// The Indexer maps a 2D coordinate to a unique 1D slice index
indexer := func(p Point) int {
return p.Y * GridSize + p.X
}
maxNodes := GridSize * GridSize
// Initialize the Solver with static configuration
solver := astar.New(
heuristic,
astar.WithIndexedSliceDict(maxNodes, indexer),
)
start := Point{X: 0, Y: 0}
goal := Point{X: 63, Y: 63}
// Execute the search by injecting the grid transition rules
path := solver.Solve(start, goal, transitions)
if path != nil {
fmt.Println("Found optimal path with steps:", len(path))
}
License
kjkrol/astar is licensed under the MIT License. See the LICENSE file for more details.
Documentation
¶
Index ¶
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
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 step cost. 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], opts ...SolverOption[T], ) *Solver[T]
New initializes and returns a new Solver configured with the provided heuristic and optional configuration parameters.
func (*Solver[T]) Iter ¶
func (a *Solver[T]) Iter(start, goal T, successors Transitions[T]) iter.Seq[bool]
Iter returns a Go 1.23 iterator sequence that allows stepping through the algorithm's execution. It yields 'false' while actively searching, and yields 'true' exactly once the moment the goal state is reached, immediately terminating the sequence afterwards.
This is exceptionally useful for visualizing the state space traversal, step-by-step debugging, or aborting the search early based on custom external conditions.
Example (DefaultDict) ¶
// Requesting a 64x64 grid with a cost weight of 1.0
const size = 64
grid := setupGrid(size)
pathFinder := setupPathFinder()
transitions := setupTransitions(1.0, grid)
start := Point{X: 0, Y: 0}
goal := Point{X: size - 1, Y: size - 1}
// Consume the iterator until completion.
// The sequence self-terminates as soon as the goal is found.
for range pathFinder.Iter(start, goal, transitions) {
}
path := pathFinder.Result()
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)
} else {
fmt.Println("Path not found")
}
Output: Path found: true Start is correct: true Goal is correct: true
Example (IndexedMapDict) ¶
const size = 64
grid := setupGrid(size)
indexer := func(p Point) int { return p.Y*size + p.X }
pathFinder := setupPathFinder(
astar.WithInitCapacity[Point](size*size),
astar.WithIndexedMapDict(indexer),
)
transitions := setupTransitions(1.0, grid)
start := Point{X: 0, Y: 0}
goal := Point{X: size - 1, Y: size - 1}
for range pathFinder.Iter(start, goal, transitions) {
}
path := pathFinder.Result()
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)
} else {
fmt.Println("Path not found")
}
Output: Path found: true Start is correct: true Goal is correct: true
Example (IndexedSliceDict) ¶
const size = 64
grid := setupGrid(size)
indexer := func(p Point) int { return p.Y*size + p.X }
pathFinder := setupPathFinder(
astar.WithIndexedSliceDict(size*size, indexer),
)
transitions := setupTransitions(1.0, grid)
start := Point{X: 0, Y: 0}
goal := Point{X: size - 1, Y: size - 1}
for range pathFinder.Iter(start, goal, transitions) {
}
path := pathFinder.Result()
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)
} else {
fmt.Println("Path not found")
}
Output: Path found: true Start is correct: true Goal is correct: 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, successors Transitions[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) ¶
const size = 64
grid := setupGrid(size)
pathFinder := setupPathFinder()
transitions := setupTransitions(1.0, grid)
start := Point{X: 0, Y: 0}
goal := Point{X: size - 1, Y: size - 1}
path := pathFinder.Solve(start, goal, transitions)
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)
} else {
fmt.Println("Path not found")
}
Output: Path found: true Start is correct: true Goal is correct: true
Example (IndexedMapDict) ¶
const size = 64
grid := setupGrid(size)
indexer := func(p Point) int { return p.Y*size + p.X }
pathFinder := setupPathFinder(
astar.WithInitCapacity[Point](size*size),
astar.WithIndexedMapDict(indexer),
)
transitions := setupTransitions(1.0, grid)
start := Point{X: 0, Y: 0}
goal := Point{X: size - 1, Y: size - 1}
path := pathFinder.Solve(start, goal, transitions)
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)
} else {
fmt.Println("Path not found")
}
Output: Path found: true Start is correct: true Goal is correct: true
Example (IndexedSliceDict) ¶
const size = 64
grid := setupGrid(size)
indexer := func(p Point) int { return p.Y*size + p.X }
pathFinder := setupPathFinder(
astar.WithIndexedSliceDict(size*size, indexer),
)
transitions := setupTransitions(1.0, grid)
start := Point{X: 0, Y: 0}
goal := Point{X: size - 1, Y: size - 1}
path := pathFinder.Solve(start, goal, transitions)
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)
} else {
fmt.Println("Path not found")
}
Output: Path found: true Start is correct: true Goal is correct: 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 Transition ¶ added in v1.0.4
type Transition[T comparable] struct { To T // The destination state of this transition. Cost float64 // The edge weight or cost associated with this state change. }
Transition represents a valid movement or mutation in the state space, capturing the destination state and the cost incurred to reach it.
type Transitions ¶ added in v1.0.4
type Transitions[T comparable] func(current, parent T, buffer []Transition[T]) []Transition[T]
Transitions defines how states mutate and how transition costs are calculated. It populates the provided reusable buffer with all valid, directly reachable transitions from the current state in a single pass.
This decoupled design keeps the Solver strictly generic and agnostic of the underlying graph structure, state representation, or domain-specific cost metrics. It is the ideal place to:
- Evaluate valid state mutations and compute dynamic transition costs (edge weights).
- Filter out invalid, blocked, or out-of-bounds states.
- Prevent immediate backtracking or simple cycles by utilizing the 'parent' state.
- Perform early pruning by excluding transitions whose cost exceeds custom thresholds.
Returns the sliced buffer containing the valid transitions.
Source Files