hpa

Documentation

Index

• Constants
• func ChunkOf(x, y, chunkSize int) (int, int)
• func PortalKey(chunkID, pos, dir, chunkSize int) int
• type HPAFinder
  • func NewHPAFinder(opts ...HPAOption) *HPAFinder
  • func (f *HPAFinder) Build(grid finder.Grid)
  • func (f *HPAFinder) FindPath(startX, startY, endX, endY int, grid finder.Grid) [][2]int
• type HPAOption
  • func WithAllowDiagonal(dontCrossCorners bool) HPAOption
  • func WithChunkSize(cs int) HPAOption
  • func WithConcreteFinder(fnd finder.Finder) HPAOption
  • func WithDiagonal(d finder.DiagonalMovement) HPAOption
  • func WithHeuristic(h finder.HeuristicFunc) HPAOption
  • func WithStringPulling(enabled bool) HPAOption
  • func WithWeight(w float64) HPAOption
• type HPAWorld
  • func BuildWorld(grid finder.Grid, chunkSize int) *HPAWorld
  • func (w *HPAWorld) ChunkIDOf(x, y int) int
  • func (w *HPAWorld) IsSingleChunk(x1, y1, x2, y2 int) bool
• type Portal

Constants

const (
	DirN = 0 // north (top edge)
	DirE = 1 // east (right edge)
	DirS = 2 // south (bottom edge)
	DirW = 3 // west (left edge)
)

Cardinal direction constants used for portal orientation.

const MaxPortalsPerChunk = 256

MaxPortalsPerChunk = ChunkSize * 4 (N/E/S/W)

Functions

func ChunkOf

func ChunkOf(x, y, chunkSize int) (int, int)

ChunkOf returns the chunk coordinates for a world position.

func PortalKey

func PortalKey(chunkID, pos, dir, chunkSize int) int

PortalKey encodes chunk ID, edge position, and direction. key = position + direction*chunkSize + chunkID*MaxPortalsPerChunk

Types

type HPAFinder

type HPAFinder struct {
	// Heuristic is the heuristic function used for estimating path cost.
	Heuristic finder.HeuristicFunc
	// Weight is the heuristic weight (higher values bias toward faster
	// but potentially suboptimal paths).
	Weight float64
	// DiagonalMovement controls whether diagonal moves are permitted
	// and under what conditions.
	DiagonalMovement finder.DiagonalMovement
	// contains filtered or unexported fields
}

HPAFinder implements Hierarchical Pathfinding A*.

It implements finder.Finder, so it can be used wherever a Finder is expected. Call Build(grid) to pre-build the hierarchical portal graph before FindPath.

func NewHPAFinder

func NewHPAFinder(opts ...HPAOption) *HPAFinder

NewHPAFinder creates an HPA* finder. Call Build(grid) to pre-build the hierarchical portal graph before calling FindPath.

func (*HPAFinder) Build

func (f *HPAFinder) Build(grid finder.Grid)

Build pre-builds the hierarchical portal graph (HPAWorld) from the given grid. Must be called before FindPath. Can be called again to rebuild after grid changes. Clears the portal path cache on rebuild.

func (*HPAFinder) FindPath

func (f *HPAFinder) FindPath(startX, startY, endX, endY int, grid finder.Grid) [][2]int

FindPath performs HPA* on the given grid. The hierarchical graph must have been pre-built via Build(grid).

It implements finder.Finder. Panics if Build() has not been called.

type HPAOption

type HPAOption func(*HPAFinder)

HPAOption configures an HPAFinder.

func WithAllowDiagonal

func WithAllowDiagonal(dontCrossCorners bool) HPAOption

WithAllowDiagonal enables diagonal movement.

func WithChunkSize

func WithChunkSize(cs int) HPAOption

WithChunkSize sets the chunk size for world partitioning.

func WithConcreteFinder

func WithConcreteFinder(fnd finder.Finder) HPAOption

WithConcreteFinder sets the finder used for segment pathfinding.

func WithDiagonal

func WithDiagonal(d finder.DiagonalMovement) HPAOption

WithDiagonal sets the diagonal movement rule.

func WithHeuristic

func WithHeuristic(h finder.HeuristicFunc) HPAOption

WithHeuristic sets the heuristic function.

func WithStringPulling

func WithStringPulling(enabled bool) HPAOption

WithStringPulling enables or disables path smoothing via LOS string pulling. Enabled by default.

func WithWeight

func WithWeight(w float64) HPAOption

WithWeight sets the heuristic weight.

type HPAWorld

type HPAWorld struct {
	// Portals is the flat array of all portals indexed by PortalKey.
	// Unused slots remain nil.
	Portals []*Portal
	// NumPortals is the total number of allocated portals.
	NumPortals int
	// ChunkMapX is the number of chunks along the X axis.
	ChunkMapX int
	// ChunkMapY is the number of chunks along the Y axis.
	ChunkMapY int
	// PaddedWidth is the grid width rounded up to a multiple of ChunkSize.
	PaddedWidth int
	// PaddedHeight is the grid height rounded up to a multiple of ChunkSize.
	PaddedHeight int
	// ChunkSize is the edge length of a single chunk in cells.
	ChunkSize int
}

HPAWorld holds the hierarchical portal graph for a Grid.

func BuildWorld

func BuildWorld(grid finder.Grid, chunkSize int) *HPAWorld

BuildWorld constructs the HPA world: partition grid into chunks, detect edge portals (compressed — one per run of consecutive walkable cells), connect external portals (adjacent chunk), and connect internal portals (BFS within chunk).

func (*HPAWorld) ChunkIDOf

func (w *HPAWorld) ChunkIDOf(x, y int) int

ChunkIDOf returns the chunk ID for a world position.

func (*HPAWorld) IsSingleChunk

func (w *HPAWorld) IsSingleChunk(x1, y1, x2, y2 int) bool

IsSingleChunk reports whether two positions are in the same chunk.

type Portal

type Portal struct {
	CenterX int // world X of portal center
	CenterY int // world Y of portal center
	Length  int // number of cells this portal spans
	Offset  int // offset along the chunk edge (0-based)

	// External connections to neighboring chunks (portal keys)
	ExternalCount   int
	ExternalPortals [5]int

	// Internal connections to other portals in the same chunk
	InternalCount   int
	InternalPortals [255]int // portal key of connected portal
	InternalCosts   [255]int // movement cost (octile * 10)
}

Portal represents a portal on a chunk border or a diagonal corner portal.