kjkrol/astart is a highly performant, fully generic A* solver for Go. Perfect for optimal pathfinding and abstract state-space search.

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.

GOKe requires Go 1.23 or newer.

go get github.com/kjkrol/goke

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.

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.

Here is a step-by-step example of how to configure the solver to find the optimal path on a 2D terrain 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

Additionally, you need to define a heuristic function (e.g., Manhattan distance) to estimate the remaining distance to the target:

// Heuristic is part of your domain definition
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
}

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.

Note: The solver allocates its internal memory structures once during initialization. This instance is designed to be reused sequentially across multiple distinct pathfinding queries to avoid GC pressure. It is not thread-safe; if you need concurrent pathfinding, use separate solver instances per goroutine or orchestrate them via a pool.

// 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 once with static configuration
solver := astar.New(
	heuristic,
	astar.WithIndexedSliceDict(maxNodes, indexer),
)

Every time you call Solve(), you pass a transition rule. This allows you to dynamicly change movement logic on the fly without reallocating solver internal buffers, ensuring zero-allocation hot paths.

// Transitions: Populates the pre-allocated buffer with valid moves and 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
}

start := Point{X: 0, Y: 0}
target := Point{X: 63, Y: 63}

// Execute the search by injecting the grid transition rules into the reused solver
path := solver.Solve(start, target, transitions)

if path != nil {
	fmt.Println("Found optimal path with steps:", len(path))
}

kjkrol/astar is licensed under the MIT License. See the LICENSE file for more details.