Documentation
¶
Overview ¶
Package paths provides utilities for efficient pathfinding in rectangular maps.
Index ¶
- func DistanceChebyshev(p, q gruid.Point) int
- func DistanceManhattan(p, q gruid.Point) int
- 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) JPSPath(path []gruid.Point, from, to gruid.Point, passable func(gruid.Point) bool, ...) []gruid.Point
- 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 ¶
func DistanceChebyshev ¶
DistanceChebyshev computes the maximum norm (infinity-norm). See:
https://en.wikipedia.org/wiki/Chebyshev_distance
It can often be used as A* distance heuristic when 8-way movement is used.
func DistanceManhattan ¶
DistanceManhattan computes the taxicab norm (1-norm). See:
https://en.wikipedia.org/wiki/Taxicab_geometry
It can often be used as A* distance heuristic when 4-way movement is used.
Types ¶
type Astar ¶
type Astar interface {
Dijkstra
// 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 {
Pather
// Cost represents the cost from one position to an adjacent one. It
// should not produce 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. Its methods return 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 returns 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. This means, in particular, that the pather should return no neighbors for obstacles.
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. This means, in particular, that the pather should return no neighbors for obstacles.
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.
func (*PathRange) JPSPath ¶
func (pr *PathRange) JPSPath(path []gruid.Point, from, to gruid.Point, passable func(gruid.Point) bool, diags bool) []gruid.Point
JPSPath returns a path from a position to another, including these positions, in the path order. It uses the given path slice to avoid allocations unless its capacity is not enough. The passable function controls which positions can be passed. If diags is false, only movements in straight cardinal directions are allowed.
The function returns nil if no path was found.
In most situations, JPSPath has significantly better performance than AstarPath. The algorithm's limitation is that it only handles uniform costs and natural neighbors in grid geometry.
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