pathfinding

Documentation

Index

• func Astar[T Pathfinder[T]](start, goal T) (path []T, found bool)
• func AstarArea[T Pathfinder[T]](start T, goals []T) (path []T, found bool)
• func BFS[T Pathfinder[T]](start, goal T) (path []T, found bool)
• func DFS[T Pathfinder[T]](start, goal T) (path []T, found bool)
• func UCS[T Pathfinder[T]](start, goal T) (path []T, found bool)
• type Pathfinder

Functions

func Astar

func Astar[T Pathfinder[T]](start, goal T) (path []T, found bool)

Astar (or A*) is UCS but applies a heuristic to tell which states are better.

func AstarArea

func AstarArea[T Pathfinder[T]](start T, goals []T) (path []T, found bool)

AstarArea is A* but targets an area

func BFS

func BFS[T Pathfinder[T]](start, goal T) (path []T, found bool)

BFS explores the breadth of the tree before the depth. The implementation is identical to DFS except BFS uses a Queue (FIFO).

func DFS

func DFS[T Pathfinder[T]](start, goal T) (path []T, found bool)

DFS explores the depth of the tree/graph before the breadth. The implementation is identical to BFS except it uses a stack (FILO).

func UCS

func UCS[T Pathfinder[T]](start, goal T) (path []T, found bool)

UCS or Dijkstra is like BFS but takes cost into account by examining lower cost routes.

Types

type Pathfinder

type Pathfinder[T any] interface {
	comparable
	// EachNeighbor calls f for each neighbor of this node.
	EachNeighbor(func(T))
	// Cost returns the cost of moving to this node.
	Cost() int
	// Heuristic returns the estimated cost to the goal.
	// For grid based games this is usually the manhattan distance.
	Heuristic(T) int
}