Documentation
¶
Overview ¶
Package waypoint provides graph-based pathfinding on arbitrary waypoint graphs.
A WaypointGraph consists of nodes with positions and connections (edges) between them. WaypointFinder implements finder.Finder by finding the closest waypoint nodes to the start/end tile coordinates and running A* on the graph.
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type EdgeState ¶
type EdgeState int
EdgeState represents the traversability state of a waypoint connection.
- Static: always traversable (default)
- Dynamic: temporarily traversable, may be blocked by moving obstacles
- Null: not traversable (treated as removed)
type GridLOS ¶
GridLOS is the interface required for LOS-based node selection. It matches a subset of the finder.Grid interface.
type WaypointEdge ¶
type WaypointEdge struct {
To *WaypointNode
Cost float64
State EdgeState
}
WaypointEdge represents a directed connection between two waypoint nodes.
type WaypointFinder ¶
type WaypointFinder struct {
// contains filtered or unexported fields
}
WaypointFinder implements finder.Finder on a waypoint graph.
It finds the closest waypoint nodes with line-of-sight to the start/end positions (via the grid parameter) and runs A* on the graph.
func NewWaypointFinder ¶
func NewWaypointFinder(opts ...WaypointOption) *WaypointFinder
NewWaypointFinder creates a WaypointFinder with the given options. By default it creates an internal WaypointGraph. Use WithGraph to inject a pre-built graph.
func (*WaypointFinder) FindPath ¶
func (f *WaypointFinder) FindPath(startX, startY, endX, endY int, grid finder.Grid) [][2]int
FindPath implements finder.Finder by searching the waypoint graph. The grid is used for LOS-based node selection — only nodes with a clear line of sight from the start/end position are considered. Path is automatically smoothed via string pulling to remove redundant waypoints.
func (*WaypointFinder) Graph ¶
func (f *WaypointFinder) Graph() *WaypointGraph
Graph returns the underlying waypoint graph for node/edge operations.
func (*WaypointFinder) SmoothPath ¶
func (f *WaypointFinder) SmoothPath(path [][2]int, grid finder.Grid) [][2]int
SmoothPath removes unnecessary waypoints from a path by checking line-of-sight between each point. Only points where the direct line is blocked by obstacles are kept. The result is written in-place over the input buffer.
type WaypointGraph ¶
type WaypointGraph struct {
Nodes []*WaypointNode
// contains filtered or unexported fields
}
WaypointGraph holds all nodes in the waypoint graph.
func NewWaypointGraph ¶
func NewWaypointGraph() *WaypointGraph
NewWaypointGraph creates an empty waypoint graph with spatial indexing.
func (*WaypointGraph) AddNode ¶
func (g *WaypointGraph) AddNode(x, y int) *WaypointNode
AddNode adds a node at tile coordinate (x, y) and returns it. The node is automatically registered in the spatial index.
func (*WaypointGraph) ConnectNearby ¶
func (g *WaypointGraph) ConnectNearby(maxDistance int, grid GridLOS)
ConnectNearby auto-connects all nodes that are within maxDistance of each other and have a clear line of sight on the given grid. Nodes that already have edges are not reconnected. Uses the spatial index for O(n*k) complexity (k = average nodes in neighboring cells) instead of O(n^2).
func (*WaypointGraph) FindClosest ¶
func (g *WaypointGraph) FindClosest(x, y int) *WaypointNode
FindClosest finds the closest node to tile coordinate (x, y). Uses the spatial index for O(1)~O(k) lookup instead of O(n) scan.
func (*WaypointGraph) FindClosestWithLOS ¶
func (g *WaypointGraph) FindClosestWithLOS(x, y int, grid GridLOS) *WaypointNode
FindClosestWithLOS finds the closest node that has a clear line of sight from the given position on the specified grid. If no node has LOS, falls back to the closest node regardless of LOS. Uses the spatial index for efficient lookup.
type WaypointNode ¶
type WaypointNode struct {
ID int
X int
Y int
Edges []*WaypointEdge
}
WaypointNode represents a node in the waypoint graph.
func NewWaypointNode ¶
func NewWaypointNode(id, x, y int) *WaypointNode
NewWaypointNode creates a new waypoint node at the given tile coordinate.
func (*WaypointNode) Connect ¶
func (n *WaypointNode) Connect(other *WaypointNode, states ...EdgeState)
Connect creates a bidirectional edge between this node and another, with the given state. If state is not specified, defaults to EdgeStateStatic.
func (*WaypointNode) ConnectOneWay ¶
func (n *WaypointNode) ConnectOneWay(other *WaypointNode, states ...EdgeState)
ConnectOneWay creates a directed edge from this node to another.
type WaypointOption ¶
type WaypointOption func(*WaypointFinder)
WaypointOption configures a WaypointFinder.
func WithGraph ¶
func WithGraph(g *WaypointGraph) WaypointOption
WithGraph sets the waypoint graph. If not provided, a new empty graph is created internally. Use this when sharing a graph between multiple finders or when loading a pre-built graph.
Source Files