Documentation
¶
Overview ¶
Package pathfinding provides graph search primitives: A*, Dijkstra, BFS over a Graph interface; built-in GridGraph for grid-based worlds.
Navmesh support is a thin Graph adapter that consumers wire to their own polygon-soup loader (see kit/unreal/navmesh for the UE5 case).
Index ¶
- Constants
- func AStar(g Graph, start, goal NodeID, out *Path) (float32, bool)
- func BFS(g Graph, start NodeID, maxDepth int, out *[]NodeID)
- func Dijkstra(g Graph, start NodeID, maxCost float32, costs map[NodeID]float32)
- func FunnelSmooth(start, goal geometry.Vec3, portals []Portal) []geometry.Vec3
- type BidirectionalSearch
- type Graph
- type GridGraph
- type GridGraph8
- func (g *GridGraph8) EdgeCost(a, b NodeID) float32
- func (g *GridGraph8) Heuristic(a, b NodeID) float32
- func (g *GridGraph8) ID(x, y int) NodeID
- func (g *GridGraph8) Neighbors(n NodeID, out *[]NodeID)
- func (g *GridGraph8) Size() int
- func (g *GridGraph8) Walkable(x, y int) bool
- func (g *GridGraph8) XY(id NodeID) (int, int)
- type JPS
- type NodeID
- type Path
- type Portal
- type Search
Constants ¶
const SentinelNode = NodeID(^uint32(0))
SentinelNode is a reserved NodeID used to mark "no predecessor" / "uninitialised" in path-reconstruction arrays. Graph implementations must not return this value from Neighbors.
Variables ¶
This section is empty.
Functions ¶
func AStar ¶
AStar is a convenience wrapper for one-off searches. Allocates a fresh Search workspace; for repeated queries against the same Graph, construct a Search via NewSearch and reuse it.
func FunnelSmooth ¶
FunnelSmooth applies the simple stupid funnel algorithm to a sequence of portals (corridor) between start and goal, producing an any-angle path that follows the actual geometry rather than the polygon centres.
Standard reference: Mikko Mononen's "Simple Stupid Funnel Algorithm". Returns waypoints in start → goal order.
Types ¶
type BidirectionalSearch ¶
type BidirectionalSearch struct {
// contains filtered or unexported fields
}
BidirectionalSearch runs two A* searches simultaneously — one from start, one from goal — and terminates when their frontiers meet. Typically explores ~half as many nodes as unidirectional A* on symmetric graphs, ~2× faster in practice.
Holds its own forward + backward workspaces, sized at construction.
func NewBidirectionalSearch ¶
func NewBidirectionalSearch(g Graph) *BidirectionalSearch
NewBidirectionalSearch returns a workspace for repeated bidirectional A* queries against g.
func (*BidirectionalSearch) AStar ¶
func (s *BidirectionalSearch) AStar(start, goal NodeID, out *Path) (float32, bool)
AStar finds the lowest-cost path from start to goal using bidirectional search. Returns total cost and ok=true on success.
Note: bidirectional A* with a non-trivial heuristic requires careful termination conditions; we use the simple "stop when a frontier node has been closed by both directions" rule, which is correct for admissible+consistent heuristics on undirected graphs (the GridGraph case).
type Graph ¶
type Graph interface {
// Size returns the total number of nodes — Search sizes its dense
// gScore / came / closed workspaces against this. Every NodeID
// returned from any Graph method must satisfy 0 ≤ id < Size().
Size() int
// Neighbors appends neighbours of n to *out (slice reused for
// allocation-free expansion).
Neighbors(n NodeID, out *[]NodeID)
// EdgeCost returns the cost of moving from a to b. Should be finite
// and non-negative for A*/Dijkstra.
EdgeCost(a, b NodeID) float32
// Heuristic estimates remaining cost from a to b. Must be admissible
// (≤ true cost) for A* optimality.
Heuristic(a, b NodeID) float32
}
Graph is the search surface for the algorithms in this package.
type GridGraph ¶
type GridGraph struct {
// contains filtered or unexported fields
}
GridGraph is a 4-connected uniform grid where each cell is walkable or not. NodeID encodes (x, y) as x*width + y.
func NewGridGraph ¶
NewGridGraph constructs a GridGraph of the given dimensions. The walkable callback decides per-cell traversability.
func (*GridGraph) ID ¶
ID encodes (x, y) into a NodeID. Out-of-bounds coords are not validated; callers should keep within [0, width)×[0, height).
type GridGraph8 ¶
type GridGraph8 struct {
// contains filtered or unexported fields
}
GridGraph8 is an 8-connected uniform grid (vs. the 4-connected GridGraph). Diagonal moves cost √2; orthogonal cost 1. Used by Jump Point Search where diagonal expansion is essential.
func NewGridGraph8 ¶
func NewGridGraph8(width, height int, walkable func(x, y int) bool) *GridGraph8
NewGridGraph8 constructs an 8-connected grid.
func (*GridGraph8) EdgeCost ¶
func (g *GridGraph8) EdgeCost(a, b NodeID) float32
func (*GridGraph8) Heuristic ¶
func (g *GridGraph8) Heuristic(a, b NodeID) float32
func (*GridGraph8) ID ¶
func (g *GridGraph8) ID(x, y int) NodeID
func (*GridGraph8) Neighbors ¶
func (g *GridGraph8) Neighbors(n NodeID, out *[]NodeID)
func (*GridGraph8) Size ¶
func (g *GridGraph8) Size() int
func (*GridGraph8) Walkable ¶
func (g *GridGraph8) Walkable(x, y int) bool
type JPS ¶
type JPS struct {
// contains filtered or unexported fields
}
JPS runs Jump Point Search over an 8-connected GridGraph8. JPS is a symmetry-breaking pruning of A* that skips co-linear "forced" moves without expanding them — typically 10-30× faster than plain A* on uniform grids.
type Portal ¶
Portal describes a corridor edge shared between two adjacent navmesh polygons. Left and Right are the two endpoints of the edge in world space, oriented relative to the traversal direction.
type Search ¶
type Search struct {
// contains filtered or unexported fields
}
Search holds reusable workspace for repeated A* queries against a single Graph. Construct one per graph at boot and call AStar many times — the workspace arrays are allocated once and reused.
Not safe for concurrent use; one Search per goroutine.
func NewSearch ¶
NewSearch returns a Search bound to g. The workspace is sized to g.Size() at construction.
func (*Search) AStar ¶
AStar finds the lowest-cost path from start to goal in the bound Graph. Returns total cost and ok=true on success; ok=false if the goal is unreachable. The path is written to *out (reused for allocation-free repeated searches).
func (*Search) BFS ¶
BFS performs breadth-first traversal from start up to maxDepth, writing the visited NodeIDs into *out (in visit order). Useful for unweighted reachability ("which cells are within 5 moves").
func (*Search) Dijkstra ¶
Dijkstra runs unweighted single-source shortest paths from start, stopping once cumulative cost exceeds max. The returned map contains the optimal cost to each reachable node within the budget.
Reuses the Search workspace's gScore / closed slices and heap. Pass math.MaxFloat32 for no budget.
Source Files