Documentation
¶
Index ¶
- Constants
- func AbsInt(x int) int
- func Backtrace(node *Node) [][2]int
- func BiBacktrace(nodeA, nodeB *Node) [][2]int
- func CompressPath(path [][2]int) [][2]int
- func ExpandPath(path [][2]int) [][2]int
- func Interpolate(x0, y0, x1, y1 int) [][2]int
- func MaxInt(a, b int) int
- func PathLength(path [][2]int) float64
- type AStarFinder
- type BestFirstFinder
- type BiAStarFinder
- type BiBestFirstFinder
- type BiBreadthFirstFinder
- type BiDijkstraFinder
- type BreadthFirstFinder
- type DiagonalMovement
- type DijkstraFinder
- type Finder
- type FinderOptions
- type Grid
- type GridWithJPSSupport
- type HeuristicFunc
- type IDAStarFinder
- type JPFAlwaysMoveDiagonally
- type JPFMoveDiagonallyIfAtMostOneObstacle
- type JPFMoveDiagonallyIfNoObstacles
- type JPFNeverMoveDiagonally
- type JPSPlusFinder
- type JumpPointFinderBase
- type MinHeap
- type Node
- type Option
Constants ¶
const SQRT2 = 1.4142135623730951
SQRT2 is the square root of 2, used as the cost of a diagonal step.
Variables ¶
This section is empty.
Functions ¶
func BiBacktrace ¶
BiBacktrace returns the path from start to end node using bidirectional parent links.
func CompressPath ¶
CompressPath removes redundant collinear nodes from a path.
func ExpandPath ¶
ExpandPath interpolates all segments in a compressed path.
func Interpolate ¶
Interpolate returns all coordinates on the line from (x0, y0) to (x1, y1) using Bresenham's algorithm.
func PathLength ¶
PathLength computes the total length of a path.
Types ¶
type AStarFinder ¶
type AStarFinder struct {
// Heuristic is the heuristic function used to estimate the cost from a node
// to the goal. Defaults to Manhattan for cardinal-only movement and Octile
// for diagonal movement.
Heuristic HeuristicFunc
// Weight is the multiplier applied to the heuristic estimate (H-cost)
// to bias the search. Values > 1 make the search faster but potentially
// suboptimal; values < 1 make it more accurate but slower. Defaults to 1.
Weight float64
// DiagonalMovement controls whether diagonal moves are allowed and under
// what obstacle conditions. See DiagonalMovement values for details.
// Defaults to DiagonalNever when not configured via Options.
DiagonalMovement DiagonalMovement
// contains filtered or unexported fields
}
AStarFinder is an implementation of the A* pathfinding algorithm.
func NewAStarFinder ¶
func NewAStarFinder(opts ...Option) *AStarFinder
NewAStarFinder creates a new AStarFinder with default options.
type BestFirstFinder ¶
type BestFirstFinder struct {
AStarFinder
}
BestFirstFinder is a Best-First-Search pathfinder. It extends AStar by using a very high heuristic weight (1,000,000x).
func NewBestFirstFinder ¶
func NewBestFirstFinder(opts ...Option) *BestFirstFinder
NewBestFirstFinder creates a new BestFirstFinder.
type BiAStarFinder ¶
type BiAStarFinder struct {
// Heuristic is the heuristic function used to estimate the cost from the
// current node to the goal. Defaults to Manhattan (or Octile when diagonal
// movement is enabled).
Heuristic HeuristicFunc
// Weight is the heuristic weight multiplier. Higher values make the
// pathfinder more greedy. Defaults to 1.
Weight float64
// DiagonalMovement specifies whether diagonal moves are allowed and under
// what conditions. Defaults to DiagonalNever.
DiagonalMovement DiagonalMovement
// contains filtered or unexported fields
}
BiAStarFinder is a bidirectional A* pathfinder.
func NewBiAStarFinder ¶
func NewBiAStarFinder(opts ...Option) *BiAStarFinder
NewBiAStarFinder creates a new BiAStarFinder.
type BiBestFirstFinder ¶
type BiBestFirstFinder struct {
BiAStarFinder
}
BiBestFirstFinder is a bidirectional Best-First-Search pathfinder.
func NewBiBestFirstFinder ¶
func NewBiBestFirstFinder(opts ...Option) *BiBestFirstFinder
NewBiBestFirstFinder creates a new BiBestFirstFinder.
type BiBreadthFirstFinder ¶
type BiBreadthFirstFinder struct {
// DiagonalMovement specifies whether diagonal moves are allowed and
// under what conditions (e.g., never, always, or only when obstacles
// do not block the way).
DiagonalMovement DiagonalMovement
// contains filtered or unexported fields
}
BiBreadthFirstFinder is a bidirectional BFS pathfinder.
func NewBiBreadthFirstFinder ¶
func NewBiBreadthFirstFinder(opts ...Option) *BiBreadthFirstFinder
NewBiBreadthFirstFinder creates a new BiBreadthFirstFinder.
type BiDijkstraFinder ¶
type BiDijkstraFinder struct {
BiAStarFinder
}
BiDijkstraFinder is a bidirectional Dijkstra pathfinder.
func NewBiDijkstraFinder ¶
func NewBiDijkstraFinder(opts ...Option) *BiDijkstraFinder
NewBiDijkstraFinder creates a new BiDijkstraFinder.
type BreadthFirstFinder ¶
type BreadthFirstFinder struct {
// DiagonalMovement determines whether diagonal moves are allowed and
// under what obstacle conditions. Defaults to DiagonalNever.
DiagonalMovement DiagonalMovement
// contains filtered or unexported fields
}
BreadthFirstFinder is a Breadth-First-Search pathfinder.
func NewBreadthFirstFinder ¶
func NewBreadthFirstFinder(opts ...Option) *BreadthFirstFinder
NewBreadthFirstFinder creates a new BreadthFirstFinder.
type DiagonalMovement ¶
type DiagonalMovement int
DiagonalMovement represents allowed diagonal movement types.
const ( // DiagonalAlways allows diagonal movement regardless of obstacles. DiagonalAlways DiagonalMovement = 1 // DiagonalNever forbids diagonal movement entirely. DiagonalNever DiagonalMovement = 2 // DiagonalIfAtMostOneObstacle allows diagonal movement if at most one of the // two adjacent cardinal cells is blocked. DiagonalIfAtMostOneObstacle DiagonalMovement = 3 // DiagonalOnlyWhenNoObstacles only allows diagonal movement when both // adjacent cardinal cells are walkable. DiagonalOnlyWhenNoObstacles DiagonalMovement = 4 )
type DijkstraFinder ¶
type DijkstraFinder struct {
AStarFinder
}
DijkstraFinder is a Dijkstra pathfinder (A* with heuristic = 0).
func NewDijkstraFinder ¶
func NewDijkstraFinder(opts ...Option) *DijkstraFinder
NewDijkstraFinder creates a new DijkstraFinder.
type Finder ¶
Finder is the interface for all pathfinding algorithms.
The returned [][2]int is backed by an internal buffer and is only valid until the next FindPath call on the same Finder. If you need to persist the result, copy it (e.g., append([][2]int{}, path...)).
func NewJumpPointFinder ¶
NewJumpPointFinder creates a JPS finder based on the diagonal movement setting.
type FinderOptions ¶
type FinderOptions struct {
AllowDiagonal bool
DontCrossCorners bool
DiagonalMovement DiagonalMovement
Heuristic HeuristicFunc
Weight float64
TrackRecursion bool
TimeLimit float64 // in seconds, <= 0 for infinite
}
FinderOptions holds common options for all finders.
func ApplyOptions ¶
func ApplyOptions(opts []Option) *FinderOptions
ApplyOptions applies a list of Option functions to a FinderOptions.
type Grid ¶
type Grid interface {
Width() int
Height() int
IsInside(x, y int) bool
IsWalkableAt(x, y int) bool
SetWalkableAt(x, y int, walkable bool)
GetNodeAt(x, y int) *Node
GetNeighbors(node *Node, diagonal DiagonalMovement, buffer []*Node) []*Node
Clone() Grid
}
Grid is the interface that all pathfinding algorithms depend on. Different grid layouts (orthogonal, hex, staggered) implement this interface with their own neighbor topology.
type GridWithJPSSupport ¶
GridWithJPSSupport is optionally implemented by Grid types that support canonical JPS neighbor pruning (standard orthogonal grids with axis-aligned topology).
type HeuristicFunc ¶
HeuristicFunc is a function that computes distance given dx and dy.
var ( // Manhattan is the Manhattan distance heuristic: dx + dy. // Suitable for grids with cardinal-only movement. Manhattan HeuristicFunc // Euclidean is the straight-line distance heuristic: sqrt(dx^2 + dy^2). // Suitable for grids with any-angle movement. Euclidean HeuristicFunc // Octile is the octile distance heuristic: (sqrt2-1)*min(dx,dy) + max(dx,dy). // Suitable for grids with diagonal movement at sqrt(2) cost. Octile HeuristicFunc // Chebyshev is the Chebyshev distance heuristic: max(dx, dy). // Suitable for grids where diagonal movement cost equals cardinal cost. Chebyshev HeuristicFunc )
type IDAStarFinder ¶
type IDAStarFinder struct {
// Heuristic is the heuristic function used to estimate the cost from a node to the goal.
Heuristic HeuristicFunc
// Weight is the multiplier applied to the heuristic estimate (g + h*Weight).
Weight float64
// DiagonalMovement specifies whether diagonal moves are allowed and under what conditions.
DiagonalMovement DiagonalMovement
// TrackRecursion enables tracking of recursion depth for debugging or visualization purposes.
TrackRecursion bool
// TimeLimit is the maximum number of seconds to spend searching before giving up. A value <= 0 means no limit.
TimeLimit float64
// contains filtered or unexported fields
}
IDAStarFinder is an Iterative Deepening A* pathfinder.
func NewIDAStarFinder ¶
func NewIDAStarFinder(opts ...Option) *IDAStarFinder
NewIDAStarFinder creates a new IDAStarFinder.
type JPFAlwaysMoveDiagonally ¶
type JPFAlwaysMoveDiagonally struct {
JumpPointFinderBase
}
JPFAlwaysMoveDiagonally is JPS that always moves diagonally.
func NewJPFAlwaysMoveDiagonally ¶
func NewJPFAlwaysMoveDiagonally(opts ...Option) *JPFAlwaysMoveDiagonally
NewJPFAlwaysMoveDiagonally creates a new JPFAlwaysMoveDiagonally.
type JPFMoveDiagonallyIfAtMostOneObstacle ¶
type JPFMoveDiagonallyIfAtMostOneObstacle struct {
JumpPointFinderBase
}
JPFMoveDiagonallyIfAtMostOneObstacle is JPS that moves diagonally when at most one obstacle exists.
func NewJPFMoveDiagonallyIfAtMostOneObstacle ¶
func NewJPFMoveDiagonallyIfAtMostOneObstacle(opts ...Option) *JPFMoveDiagonallyIfAtMostOneObstacle
NewJPFMoveDiagonallyIfAtMostOneObstacle creates a new JPFMoveDiagonallyIfAtMostOneObstacle.
type JPFMoveDiagonallyIfNoObstacles ¶
type JPFMoveDiagonallyIfNoObstacles struct {
JumpPointFinderBase
}
JPFMoveDiagonallyIfNoObstacles is JPS that only moves diagonally when there are no obstacles.
func NewJPFMoveDiagonallyIfNoObstacles ¶
func NewJPFMoveDiagonallyIfNoObstacles(opts ...Option) *JPFMoveDiagonallyIfNoObstacles
NewJPFMoveDiagonallyIfNoObstacles creates a new JPFMoveDiagonallyIfNoObstacles.
type JPFNeverMoveDiagonally ¶
type JPFNeverMoveDiagonally struct {
JumpPointFinderBase
}
JPFNeverMoveDiagonally is JPS with only horizontal/vertical movement.
func NewJPFNeverMoveDiagonally ¶
func NewJPFNeverMoveDiagonally(opts ...Option) *JPFNeverMoveDiagonally
NewJPFNeverMoveDiagonally creates a new JPFNeverMoveDiagonally.
type JPSPlusFinder ¶ added in v0.2.0
type JPSPlusFinder struct {
Heuristic HeuristicFunc
DiagonalMovement DiagonalMovement
Weight float64
// contains filtered or unexported fields
}
JPSPlusFinder implements Jump Point Search Plus — a precomputation-based optimization of JPS. It replaces the iterative jump() function with an O(1) table lookup of precomputed jump distances.
Call Precompute(grid) before FindPath. The grid is assumed to be static; changes to the grid require calling Precompute again.
func NewJPSPlusFinder ¶ added in v0.2.0
func NewJPSPlusFinder(opts ...Option) *JPSPlusFinder
NewJPSPlusFinder creates a JPS+ finder with the given options.
func (*JPSPlusFinder) FindPath ¶ added in v0.2.0
func (j *JPSPlusFinder) FindPath(startX, startY, endX, endY int, grid Grid) [][2]int
FindPath performs JPS+ pathfinding using the precomputed jump table. Precompute(grid) must have been called first with the same grid.
func (*JPSPlusFinder) LoadPrecomputed ¶ added in v0.2.0
func (j *JPSPlusFinder) LoadPrecomputed(data []byte) error
LoadPrecomputed loads previously exported jump table data. Must be called before FindPath with a grid of matching dimensions.
func (*JPSPlusFinder) Precompute ¶ added in v0.2.0
func (j *JPSPlusFinder) Precompute(grid Grid)
Precompute builds the jump distance table for the given grid. Must be called before FindPath. The grid is assumed static.
func (*JPSPlusFinder) PrecomputedData ¶ added in v0.2.0
func (j *JPSPlusFinder) PrecomputedData() ([]byte, error)
PrecomputedData serializes the jump table to binary data. The returned slice can be saved to a file and loaded later with LoadPrecomputed, avoiding the cost of re-running Precompute on server restart.
func (*JPSPlusFinder) PrecomputedSize ¶ added in v0.2.0
func (j *JPSPlusFinder) PrecomputedSize() int
PrecomputedSize returns the byte size of the serialized jump table. Useful for estimating storage or memory before exporting.
type JumpPointFinderBase ¶
type JumpPointFinderBase struct {
Heuristic HeuristicFunc
DiagonalMovement DiagonalMovement
TrackRecursion bool
// contains filtered or unexported fields
}
JumpPointFinderBase is the base implementation for Jump Point Search.
func NewJumpPointFinderBase ¶
func NewJumpPointFinderBase(opts ...Option) *JumpPointFinderBase
NewJumpPointFinderBase creates a new JumpPointFinderBase.
type MinHeap ¶
type MinHeap struct {
// contains filtered or unexported fields
}
MinHeap is a binary heap for A* open list, ordered by F value. The less function pointer is intentionally NOT used — the comparison is hardcoded as a.F < b.F to enable compiler inlining of the hot path.
func NewMinHeap ¶
func NewMinHeap() *MinHeap
NewMinHeap creates a new MinHeap with an initial capacity of 64.
func (*MinHeap) Pop ¶
Pop removes and returns the node with the smallest F value from the heap. The popped node's HeapIndex is set to -1. Returns nil when the heap is empty (though callers should check Empty first).
func (*MinHeap) UpdateItem ¶
UpdateItem restores the heap invariant after a node's F value has decreased. In the A* algorithm this is only called when G (and thus F) strictly decreases, so the node can only move upward toward the root — the sift-down pass is unnecessary.
type Node ¶
type Node struct {
X int
Y int
Walkable bool
// Pathfinding state (reused across searches)
G, H, F float64
Parent *Node
Opened int // 0=unopened, 1=BY_START, 2=BY_END (for bidirectional)
Closed bool
By int // 1=BY_START, 2=BY_END (for bidirectional BFS)
// JPF tracking
Tested bool
RetainCount int
// heap index
HeapIndex int
// SearchID matches the finder's search sequence to avoid resetting per node.
// 0 = initial state, updated on first use by each finder call.
SearchID int
}
Node represents a single node on a grid.
func (*Node) ResetSearch ¶
ResetSearch resets all search-related fields if seq doesn't match. This allows repeated use of the same node across multiple FindPath calls without cloning the entire grid.
type Option ¶
type Option func(*FinderOptions)
Option configures a finder.
func WithAllowDiagonal ¶
WithAllowDiagonal enables diagonal movement.
func WithDiagonal ¶
func WithDiagonal(d DiagonalMovement) Option
WithDiagonal sets the diagonal movement rule.
func WithHeuristic ¶
func WithHeuristic(h HeuristicFunc) Option
WithHeuristic sets the heuristic function.
func WithTimeLimit ¶
WithTimeLimit sets the time limit in seconds.
func WithTrackRecursion ¶
func WithTrackRecursion() Option
WithTrackRecursion enables recursion tracking.
Source Files