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 target and how states mutate based on your grid topography.
// 1. Heuristic: Estimates the distance to the target (e.g., Manhattan distance)
heuristic := func(from, to Point) float64 {
dx := math.Abs(float64(to.X - from.X))
dy := math.Abs(float64(to.Y - from.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(from, prev Point, buffer []astar.Transition[Point]) []astar.Transition[Point] {
for _, d := range dirs {
nx, ny := from.X+d.X, from.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 == prev.X && ny == prev.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}
target := Point{X: 63, Y: 63}
// Execute the search by injecting the grid transition rules
path := solver.Solve(start, target, 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(from, to T) float64
Heuristic defines the estimated cost to travel from one state to another.
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(from, to T, transitions Transitions[T]) iter.Seq[bool]
Iter yields false while searching and true once the 'to' state is reached. The sequence terminates immediately after reaching the target.
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(from, to T, transitions Transitions[T]) []T
Solves the optimal transition sequence between the 'from' and 'to' states. It returns the full sequence of states, or nil if no solution exists.
Example ¶
package main
import (
"fmt"
"github.com/kjkrol/astar"
)
// Point represents a coordinate on a 2D grid.
type Point2d struct {
X, Y int
}
func main() {
// Define a simple 3x3 grid where 1 represents a wall/blocked cell.
grid := [][]int{
{0, 0, 0},
{1, 1, 0},
{0, 0, 0},
}
width, height := 3, 3
// Indexer maps a Point to a unique dense integer for maximum performance.
// This allows the slice-based dictionary to bypass heavy hashmap lookups.
indexer := func(p Point2d) int {
return p.Y*width + p.X
}
// Define a simple Manhattan distance heuristic
heuristic := func(from, to Point2d) float64 {
dx := from.X - to.X
dy := from.Y - to.Y
if dx < 0 {
dx = -dx
}
if dy < 0 {
dy = -dy
}
return float64(dx + dy)
}
// Setup the solver with maximum optimizations for a bounded space.
solver := astar.New[Point2d](
heuristic,
astar.WithInitCapacity[Point2d](width*height),
astar.WithIndexedSliceDict(width*height, indexer),
)
// Define transitions (allowed movements on our grid).
transitions := func(from, prev Point2d, buffer []astar.Transition[Point2d]) []astar.Transition[Point2d] {
// Reset buffer slice while preserving underlying allocation
buffer = buffer[:0]
// 4-directional movement vectors (Up, Down, Left, Right)
dirs := []Point2d{{0, -1}, {0, 1}, {-1, 0}, {1, 0}}
for _, d := range dirs {
next := Point2d{X: from.X + d.X, Y: from.Y + d.Y}
// 1. Boundary check
if next.X < 0 || next.X >= width || next.Y < 0 || next.Y >= height {
continue
}
// 2. Obstacle check
if grid[next.Y][next.X] == 1 {
continue
}
// 3. Prevent immediate backtracking to the previous state
if next == prev {
continue
}
// Append valid step with a uniform move cost of 1.0
buffer = append(buffer, astar.Transition[Point2d]{To: next, Cost: 1.0})
}
return buffer
}
// Define start and target states
from := Point2d{X: 0, Y: 0}
to := Point2d{X: 0, Y: 2}
// Solve the problem
path := solver.Solve(from, to, transitions)
fmt.Printf("Path length: %d\n", len(path))
fmt.Printf("Steps: %v\n", path)
}
Output: Path length: 7 Steps: [{0 0} {1 0} {2 0} {2 1} {2 2} {1 2} {0 2}]
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(from, prev T, buffer []Transition[T]) []Transition[T]
Transitions defines how steps between states are discovered and how their costs are calculated. It populates the provided reusable buffer with all valid, directly reachable transitions from the 'from' 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 neighbor nodes and compute dynamic transition costs (edge weights).
- Filter out invalid, blocked, or out-of-bounds destinations.
- Prevent immediate backtracking or simple cycles by utilizing the 'prev' state.
- Perform early pruning by excluding transitions whose cost exceeds custom thresholds.
Returns the sliced buffer containing the valid transitions.
Source Files