pathfinding

Documentation

Index

• type Cost
• type Link
• type Point
  • func Search(start Point, goal Point, canTraverse func(Point) bool) []Point
  • func (p Point) Adjacent(exists func(Point) bool) (px []Link)
  • func (p Point) Heuristic(goal Point) Cost
• type PointEntry
• type SearchState
  • func NewSearchState() *SearchState
  • func (ss *SearchState) GetEntry(p Point) *PointEntry
  • func (ss *SearchState) Len() int
  • func (ss *SearchState) Less(i, j int) bool
  • func (ss *SearchState) Pop() interface{}
  • func (ss *SearchState) Push(x interface{})
  • func (ss *SearchState) Swap(i, j int)

Types

type Cost

type Cost uint32

const (
	HorizontalCost Cost = 2
	VerticalCost   Cost = 2
	DiagonalCost   Cost = 3
)

we cannot have diagonal costs be the same as the others, because then the path will zig-zag

type Link

type Link struct {
	Point
	Cost
}

type Point

type Point struct {
	X, Y uint
}

func Search

func Search(start Point, goal Point, canTraverse func(Point) bool) []Point

implemented from https://en.wikipedia.org/wiki/A*_search_algorithm

func (Point) Adjacent

func (p Point) Adjacent(exists func(Point) bool) (px []Link)

func (Point) Heuristic

func (p Point) Heuristic(goal Point) Cost

compute the largest of the horizontal and vertical distance, because diagonals.

type PointEntry

type PointEntry struct {
	// contains filtered or unexported fields
}

type SearchState

type SearchState struct {
	// contains filtered or unexported fields
}

based on example from https://golang.org/pkg/container/heap/

func NewSearchState

func NewSearchState() *SearchState

func (*SearchState) GetEntry

func (ss *SearchState) GetEntry(p Point) *PointEntry

func (*SearchState) Len

func (ss *SearchState) Len() int

func (*SearchState) Less

func (ss *SearchState) Less(i, j int) bool

func (*SearchState) Pop

func (ss *SearchState) Pop() interface{}

func (*SearchState) Push

func (ss *SearchState) Push(x interface{})

func (*SearchState) Swap

func (ss *SearchState) Swap(i, j int)