README
Documentation
¶
Overview ¶
Collection of data structures and algorithms. Most are available elsewhere with better testing and performance. We reinvent the wheel for fun and practice.
Index ¶
- Constants
- func GetMapKeysSorted[K constraints.Ordered, V any](m map[K]V) []K
- func PathSearchNoHeuristic(a, b Node) int
- func SortMapByValue[K constraints.Ordered, V any](m map[K]V, sortFn func(a, b V) bool) []K
- type GraphNode
- type Grid
- func (g *Grid[T]) Dimensions() (x, y int)
- func (g *Grid[T]) Get(x, y int) T
- func (g *Grid[T]) GetCost(x, y int) int
- func (g *Grid[T]) GetFromNodeKey(key NodeKey) (int, int)
- func (g *Grid[T]) GetNode(x, y int) GridNode[T]
- func (g *Grid[T]) InBounds(x, y int) bool
- func (g *Grid[T]) IsBlocked(x, y int) bool
- func (g *Grid[T]) Set(x, y int, data T)
- func (g *Grid[T]) SetAll(data T)
- func (g *Grid[T]) SetAllCosts(cost int)
- func (g *Grid[T]) SetBlocked(x, y int)
- func (g *Grid[T]) SetCost(x, y, cost int)
- func (g *Grid[T]) SetNeighbourHoodMode4()
- func (g *Grid[T]) SetNeighbourHoodMode8(dcost float32)
- func (g *Grid[T]) SetUnBlocked(x, y, cost int)
- func (g *Grid[T]) String() string
- type GridNode
- type Heap
- type HeapNode
- type MappedSlice
- type Node
- type NodeKey
- type Paths
- type Queue
- type Set
- type Stack
Constants ¶
const QueueDefaultSize = 16
Variables ¶
This section is empty.
Functions ¶
func GetMapKeysSorted ¶
func GetMapKeysSorted[K constraints.Ordered, V any](m map[K]V) []K
Get the keys of a map sorted by key value
func PathSearchNoHeuristic ¶
Used in PathSearch in place of an actual heuristic function. Returns 0.
func SortMapByValue ¶
func SortMapByValue[K constraints.Ordered, V any](m map[K]V, sortFn func(a, b V) bool) []K
Get the keys of a map sorted by the map value. Provide a function to do the value sort test.
Types ¶
type GraphNode ¶
A generic implementation of Node. GraphNodes can hold any data. The transition weights (costs) are positive ints.
func NewGraphNode ¶
func (*GraphNode[T]) LinkBidirectional ¶
Set node as neighbour of current node and current node as neighbour of node.
func (*GraphNode[T]) Neighbours ¶
Get neighbours of node.
type Grid ¶
type Grid[T any] struct { // contains filtered or unexported fields }
A generic grid for pathfinding.
func (*Grid[T]) Dimensions ¶
Return grid width and height.
func (*Grid[T]) GetFromNodeKey ¶
Returns x,y from a NodeKey
func (*Grid[T]) GetNode ¶
Convert a cell into a GridNode which can be used as input in the path search methods.
func (*Grid[T]) SetAllCosts ¶
Set all travel costs to the same value.
func (*Grid[T]) SetBlocked ¶
Set grid cell to blocked. Blocked cells are ignored when pathfinding.
func (*Grid[T]) SetNeighbourHoodMode4 ¶
func (g *Grid[T]) SetNeighbourHoodMode4()
Set neighbourhood mode to 4 neighbours (top, bot, left, right). Cost of traveling to neighbours is the whatever the Cost() of that cell is.
func (*Grid[T]) SetNeighbourHoodMode8 ¶
Set neighbourhood mode to 8 neighbours (top, bot, left, right, top-left, top-right, bot-left, bot-right). When moving diagonally, cost is calculated as cell cost multiplied by dcost (typically sqrt(2)).
func (*Grid[T]) SetUnBlocked ¶
Set grid cell to unblocked. Provide a travel cost for the unblocked cell. Unblocked cells can be traversed when pathfinding.
type GridNode ¶
type GridNode[T any] struct { // contains filtered or unexported fields }
GridNode satisfies Node interface so it can be used for pathfinding. Grid can convert its cells to a GridNode using GetNode.
func (*GridNode[T]) Cost ¶
Returns the cost of traveling from this current node to node. It is taken from the Cost() method of the grid data at the node's (destination's) location. If current and node are diagonal, the cost is multiplied by a diagonal cost multiplier (controlled with Grid.SetNeighbourHoodMode8).
func (*GridNode[T]) Key ¶
Grid cells are uniquly identifiable by their x,y coords. We combine into one key using the index formula: y*width+x.
func (*GridNode[T]) Neighbours ¶
Get the neighbours of this node. Will return 4 if grid is set to fourNeibourhood(4N) or 8 if set to eightNeibourhood(8N). Edges of the grid will return 3(4N)/5(8N) nodes and corners will return 2(4N)/3(8N) nodes.
type Heap ¶
type Heap[T HeapNode] struct { // contains filtered or unexported fields }
A binary heap implemented with an array. It is a max heap by default, but can be changed to a min heap. Switching can happen in place if needed, at cost O(n). It accepts data that implements the HeapNode interface.
func (*Heap[T]) PeekTop ¶
func (h *Heap[T]) PeekTop() T
Return the top of the heap without removing it.
func (*Heap[T]) SetMaxHeapMode ¶
func (h *Heap[T]) SetMaxHeapMode()
Max priority at the top of the heap. Will reorganize elements if needed. Max is the default.
func (*Heap[T]) SetMinHeapMode ¶
func (h *Heap[T]) SetMinHeapMode()
Min priority at the top of the heap. Will reorganize elements if needed.
type HeapNode ¶
type HeapNode interface {
Priority() int
}
Data going in Heap must implement Priority() which lets the Heap decide which element is on top.
type MappedSlice ¶
type MappedSlice[ST any, MT comparable] struct { S []ST M map[MT]mappedSliceRange }
MappedSlice is an indexed slice. It can be used to retrieve specific sub-portions of the slice without searching. Can be used in cases where map-like access is required (where a map would be appropriate) and the whole slice is often iterated upon (where a slice is faster than a map). Can also be used to store multiple small slices in a continuous piece of memory.
func (*MappedSlice[ST, MT]) AddMapped ¶
func (i *MappedSlice[ST, MT]) AddMapped(data ST, key MT)
Add data and index it with key.
func (*MappedSlice[ST, MT]) AddSliceMapped ¶
func (i *MappedSlice[ST, MT]) AddSliceMapped(data []ST, key MT)
Add a data slice and index it with a key.
func (MappedSlice[ST, MT]) Get ¶
func (i MappedSlice[ST, MT]) Get(key MT) []ST
Get slice portion indexed with key.
func (MappedSlice[ST, MT]) New ¶
func (i MappedSlice[ST, MT]) New() MappedSlice[ST, MT]
type Node ¶
type Node interface {
Key() NodeKey
// Gets the neighbours of node
Neighbours() []Node
// Cost of going to node. Return negative cost if Node is not a neighbour
Cost(Node) int
}
Node is the interface of a graph node. See GraphNode for a generic implementation.
type NodeKey ¶
type NodeKey int
Identifier for graph nodes.
func PathSearch ¶
Search for a path to a specific node. Faster than PathSearchAll since it can exit as soon as it reaches the destination. Pass a heuristic funcion to prioritize node evaluation. For example, on a grid, the heuristic can be the Manhattan distance of the two nodes which turns PathSearch into A*. Pass PathSearchNoHeuristic to do Dijkstra with early exit.
type Paths ¶
type Paths struct {
Start NodeKey
// contains filtered or unexported fields
}
Paths is the result of running PathSearchAll and stores all paths starting at node Start. To get a path to a specific destination use PathTo.
func PathSearchAll ¶
Search all paths starting at node. Uses Dijkstra's method. Returns a Paths object which contains a map with destination->source entries. Use Paths.PathTo() to get paths from start to specific nodes.
type Queue ¶
type Queue[T any] struct { // contains filtered or unexported fields }
FIFO Q
func (*Queue[T]) SetResizeChunk ¶
How much to increase the q by when it runs out of space.
type Set ¶
type Set[T comparable] struct { // contains filtered or unexported fields }
A map implementation of a set. Important set operations are currently missing (intersect, diff, union).
Source Files