Documentation
¶
Overview ¶
Package paths provides utilities for efficient pathfinding in rectangular maps.
Index ¶
- type Astar
- type Dijkstra
- type Neighbors
- type Node
- type PathRange
- func (pr *PathRange) AstarPath(ast Astar, from, to gruid.Point) []gruid.Point
- func (pr *PathRange) BreadthFirstMap(nb Pather, sources []gruid.Point, maxCost int) []Node
- func (pr *PathRange) BreadthFirstMapAt(p gruid.Point) int
- func (pr *PathRange) CCMap(nb Pather, p gruid.Point) []gruid.Point
- func (pr *PathRange) CCMapAll(nb Pather)
- func (pr *PathRange) CCMapAt(p gruid.Point) int
- func (pr *PathRange) DijkstraMap(dij Dijkstra, sources []gruid.Point, maxCost int) []Node
- func (pr *PathRange) DijkstraMapAt(p gruid.Point) int
- func (pr *PathRange) GobDecode(bs []byte) error
- func (pr *PathRange) GobEncode() ([]byte, error)
- func (pr *PathRange) Range() gruid.Range
- func (pr *PathRange) SetRange(rg gruid.Range)
- type Pather
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Astar ¶
type Astar interface {
// Neighbors returns the available neighbor positions of a given
// position. Implementations may use a cache to avoid allocations.
Neighbors(gruid.Point) []gruid.Point
// Cost represents the cost from one position to an adjacent one. It
// should not produce paths with negative costs.
Cost(gruid.Point, gruid.Point) int
// Estimation offers an estimation cost for a path from a position to
// another one. The estimation should always give a value lower or
// equal to the cost of the best possible path.
Estimation(gruid.Point, gruid.Point) int
}
Astar is the interface that allows to use the A* algorithm used by the AstarPath function.
type Dijkstra ¶
type Dijkstra interface {
// Neighbors returns the available neighbor positions of a given
// position. Implementations may use a cache to avoid allocations.
Neighbors(gruid.Point) []gruid.Point
// Cost represents the cost from one position to an adjacent one. It
// should not produce paths with negative costs.
Cost(gruid.Point, gruid.Point) int
}
Dijkstra is the interface that allows to build a dijkstra map using the DijkstraMap function.
type Neighbors ¶
type Neighbors struct {
// contains filtered or unexported fields
}
Neighbors fetches adjacent positions. It returns a cached slice for efficiency, so results are invalidated by next method calls. It is suitable for use in satisfying the Dijkstra, Astar and Pather interfaces.
func (*Neighbors) All ¶
All returns 8 adjacent positions, including diagonal ones, filtered by keep function.
type Node ¶
Node represents a position in a dijkstra map with a related distance cost relative to the most close source.
type PathRange ¶
type PathRange struct {
// contains filtered or unexported fields
}
PathRange allows for efficient path finding within a range. It caches structures, so that they can be reused without further memory allocations.
It implements gob.Encoder and gob.Decoder for easy serialization.
func NewPathRange ¶
NewPathRange returns a new PathFinder for positions in a given range, such as the range occupied by the whole map, or a part of it.
func (*PathRange) AstarPath ¶
AstarPath return a path from a position to another, including thoses positions, in the path order. It returns nil if no path was found.
func (*PathRange) BreadthFirstMap ¶
BreadthFirstMap efficiently computes a map of minimal distance costs from source positions to all the positions in the PathFinder range up to a maximal cost. Other positions will have the value maxCost+1, including unreachable ones. It returns a cached slice of map nodes in increasing cost order.
It can be viewed as a particular case of DijkstraMap built with a cost function that returns 1 for all neighbors, but it is more efficient.
func (*PathRange) BreadthFirstMapAt ¶
BreadthFirstMapAt returns the cost associated to a position in the last computed breadth first map. It returns the last maxCost + 1 if the position is out of range, the same as in-range unreachable positions. BreadthFirstMapAt uses a cached breadth first map, that will be invalidated in case a new one is computed using the same PathFinder.
func (*PathRange) CCMap ¶
CCMap computes the connected component which contains a given position. It returns a cached slice with all the positions in the same connected component as p, or nil if p is out of range. It makes the assumption that the paths are bidirectional, allowing for efficient computation.
It makes uses of the same caching structures as ComputeCCAll, so CCAt will return -1 on all unreachable positions from p.
func (*PathRange) CCMapAll ¶
CCMapAll computes a map of the connected components. It makes the assumption that the paths are bidirectional, allowing for efficient computation.
func (*PathRange) CCMapAt ¶
CCMapAt returns a positive number identifying the position's connected component as computed by either the last CCMap or CCMapAll call. It returns -1 on out of range positions.
func (*PathRange) DijkstraMap ¶
DijkstraMap computes a dijkstra map given a list of source positions and a maximal cost from those sources. It returns a slice with the nodes of the map, in cost increasing order. The resulting slice is cached for efficiency, so future calls to DijkstraMap will invalidate its contents.
func (*PathRange) DijkstraMapAt ¶
DijkstraMapAt returns the cost associated to a position in the last computed Dijkstra map. It returns maxCost + 1 if the position is out of range.
type Pather ¶
type Pather interface {
// Neighbors returns the available neighbor positions of a given
// position. Implementations may use a cache to avoid allocations.
Neighbors(gruid.Point) []gruid.Point
}
Pather is the interface used by algorithms that only need neighbor information. It's the minimal interface that allows to build paths.
Source Files