# grid
`import "github.com/matjam/bunyip/grid"`
Package grid provides the tile-map helpers roguelikes and strategy games need: a generic cell grid, A\* and Dijkstra pathfinding, Bresenham lines, shadowcasting field of view and flood fill.
Grid\[T] is a rectangular array of cells with bounds checking (In, At, Set, Fill, Each). The algorithms take a cost or passability function over points, so they work on any map representation, not only a Grid. AStar finds one path with four or eight-way movement and a cost per step, including zero and fractional costs. It uses a zero heuristic because the callback provides no positive lower bound on step costs, so the search is uninformed and expands cells in every direction. For speed, call AStarWithMinCost with the smallest cost any step can have, or set Pathfinder.MinCost once for a map. Dijkstra fills a map of distances from many sources at once. Downhill selects a lower-valued neighbour, useful for uniform-cost movement toward the sources. FOV computes which cells are visible from a point against an opacity function. Line walks the cells between two points for projectiles and line of sight. FloodFill collects a connected region.
Pathfinding and FOV functions borrow pooled scratch space, which can allocate when first used, grown, or discarded by the runtime. To search or cast sight without allocating after buffer growth, keep a Pathfinder for the map and a Vision for the viewer, and call their methods: Pathfinder appends a path to a slice the caller owns and fills a Dijkstra map the caller already has, and Vision reuses the scratch space a field of view cast needs. Both hold scratch space rather than results, so give each goroutine its own.
Points are integer cell coordinates with +Y down, matching the renderer's 2D space and Tilemap; nothing here depends on gfx.
## Variables
```go
var (
Dirs4 = []Point{ /* … */ }
Dirs8 = []Point{ /* … */ }
)
```
Dirs4 and Dirs8 are the neighbour offsets, cardinals first.
```go
var Blocked = float32(math.Inf(1))
```
Blocked is the step cost of an impassable move.
## Functions
### FOV
```go
func FOV(origin Point, radius int, opaque func(Point) bool, visit func(Point))
```
FOV computes which cells are visible from origin within radius by recursive shadowcasting, calling visit once for each (the origin included). opaque says whether a cell blocks sight; it is only asked about cells the caster reaches, so it must tolerate coordinates off the map. visit can also receive out-of-bounds coordinates; filter them before storing results. Radius is Euclidean in cells; negative radius is treated as zero. Scratch comes from a shared pool and may allocate on first use or growth. Keep a Vision to reuse it.
Example:
```go
package main
import (
"fmt"
"github.com/matjam/bunyip/grid"
)
// A five-by-three map with a wall in the middle column, open at the top.
var walls = []string{
".....",
"..#..",
"..#..",
}
func main() {
inMap := func(p grid.Point) bool { return p.X >= 0 && p.Y >= 0 && p.X < 5 && p.Y < 3 }
// Cells off the map count as opaque so light stops at the edge.
opaque := func(p grid.Point) bool { return !inMap(p) || walls[p.Y][p.X] == '#' }
var seen []grid.Point
grid.FOV(grid.Point{X: 0, Y: 2}, 10, opaque, func(p grid.Point) {
if inMap(p) {
seen = append(seen, p)
}
})
// The wall's near face is visible; the cells behind it are not.
fmt.Println(len(seen), "cells visible of 15")
}
```
Output:
```
10 cells visible of 15
```
## Types
### Cost
```go
type Cost func(from, to Point) float32
```
Cost gives the nonnegative price of stepping from one cell to a neighbour, or Blocked. Zero and fractional costs are valid. Negative costs are treated as blocked. Return finite costs or Blocked, never NaN. The callback controls diagonal prices and corner cutting; the search does not check adjacent cardinal cells or add a diagonal multiplier. Diagonal moves are only offered when the search allows them. Keep costs stable during a search; directed costs are supported.
### Grid
```go
type Grid[T any] struct {
W, H int
Cells []T
}
```
Grid is a W by H array of cells in row-major order. Cells is owned by the grid; keep its length equal to W\*H when constructing or resizing a grid manually. The zero value is an empty grid.
#### Dijkstra
```go
func Dijkstra(w, h int, sources []Point, diagonal bool, cost Cost) *Grid[float32]
```
Dijkstra returns the cost from the nearest source to every cell, with Blocked for cells that cannot be reached. Roguelikes use the result as a Dijkstra map. Distances follow cost in the source-to-cell direction; reverse the callback's arguments when seeking costs back to a source over directed edges. To reuse output and scratch across frames, keep a Pathfinder and call DijkstraInto; pooled scratch may allocate initially.
Example:
```go
package main
import (
"fmt"
"github.com/matjam/bunyip/grid"
)
// A five-by-three map with a wall in the middle column, open at the top.
var walls = []string{
".....",
"..#..",
"..#..",
}
func cost(from, to grid.Point) float32 {
if walls[to.Y][to.X] == '#' {
return grid.Blocked
}
return 1
}
func main() {
// A Dijkstra map gives every cell its distance to the player; a
// monster walks downhill to chase, or uphill to flee.
dist := grid.Dijkstra(5, 3, []grid.Point{{X: 4, Y: 2}}, false, cost)
next, _ := grid.Downhill(dist, grid.Point{X: 0, Y: 2}, false)
fmt.Println(dist.At(0, 2), next)
}
```
Output:
```
8 {1 2}
```
#### New
```go
func New[T any](w, h int) *Grid[T]
```
New makes a grid of zero cells.
#### Grid.At
```go
func (g *Grid[T]) At(x, y int) T
```
At returns the cell, or the zero value outside the grid.
#### Grid.Each
```go
func (g *Grid[T]) Each(fn func(x, y int, v T))
```
Each visits every cell in row-major order.
#### Grid.Fill
```go
func (g *Grid[T]) Fill(v T)
```
Fill sets every cell.
#### Grid.In
```go
func (g *Grid[T]) In(x, y int) bool
```
In reports whether the coordinate is inside the grid.
#### Grid.Set
```go
func (g *Grid[T]) Set(x, y int, v T)
```
Set writes a cell; writes outside the grid are ignored.
### Pathfinder
```go
type Pathfinder struct {
// MinCost is the smallest cost any traversable step on the map can
// have, diagonals included. To make every AStar call on this
// pathfinder a guided search, set it once when the map is made: AStar
// then searches as AStarWithMinCost does with this bound. The zero
// value leaves AStar uninformed. Overstating it loses the
// cheapest-path guarantee; zero, negative, NaN and infinite values
// count as zero.
MinCost float32
// contains filtered or unexported fields
}
```
Pathfinder holds the scratch space a search needs so that repeated searches on a map of one size allocate nothing. Make one per map with NewPathfinder and keep it for as long as the map lasts. A Pathfinder is not safe for concurrent use; give each goroutine its own.
#### NewPathfinder
```go
func NewPathfinder(w, h int) *Pathfinder
```
NewPathfinder makes a pathfinder for a w by h map.
#### Pathfinder.AStar
```go
func (p *Pathfinder) AStar(out []Point, start, goal Point, diagonal bool, cost Cost) ([]Point, bool)
```
AStar finds the cheapest path from start to goal, appends it to out including both endpoints, and reports true. With diagonal set, eight-way moves are considered. When there is no path it returns out unchanged and false, so the caller keeps its buffer. Pass out as buf\[:0] to search every frame without allocating.
With MinCost zero, the default, the search is uninformed: a zero heuristic preserves cheapest paths for zero and fractional costs, but orders the search by accumulated cost as in Dijkstra, which expands cells in every direction. For speed, set MinCost to the smallest cost any step can have, or call AStarWithMinCost.
#### Pathfinder.AStarWithMinCost
```go
func (p *Pathfinder) AStarWithMinCost(out []Point, start, goal Point, diagonal bool, cost Cost, minCost float32) ([]Point, bool)
```
AStarWithMinCost appends a path to out as AStar does, using minCost to guide the search. A finite positive minCost must be no greater than every traversable step cost, including diagonals. It scales Manhattan distance for four-way moves and Chebyshev distance for eight-way moves. The bound is not checked against the map; overstating it loses the cheapest-path guarantee. Zero, negative, NaN and infinite bounds fall back to the zero heuristic. minCost applies to this call in place of the MinCost field. When no path exists, out is unchanged and the result is false. Pass buf\[:0] to reuse the output storage.
#### Pathfinder.DijkstraInto
```go
func (p *Pathfinder) DijkstraInto(dist *Grid[float32], sources []Point, diagonal bool, cost Cost)
```
DijkstraInto fills dist with the cost from the nearest source to every cell, Blocked where a cell cannot be reached, reusing the map the caller already has. dist must be the pathfinder's own width and height; a map of another size is left alone.
#### Pathfinder.Resize
```go
func (p *Pathfinder) Resize(w, h int)
```
Resize points the pathfinder at a map of another size, growing its scratch space when it has to. Call it when the level changes rather than making a new pathfinder.
#### Pathfinder.Size
```go
func (p *Pathfinder) Size() (w, h int)
```
Size is the map size the pathfinder is set up for.
### Point
```go
type Point struct{ X, Y int }
```
Point is a cell coordinate.
#### AStar
```go
func AStar(w, h int, start, goal Point, diagonal bool, cost Cost) []Point
```
AStar finds the cheapest path from start to goal on a w by h grid, including both endpoints, or returns nil when there is none. With diagonal set, eight-way moves are considered. The scratch space the search needs comes from a shared pool; the returned path owns its storage. A game that searches every frame keeps a Pathfinder instead and calls its AStar method, which reuses scratch and caller-owned output storage. Initial searches or buffer growth may allocate. An out-of-bounds endpoint has no path; equal in-bounds endpoints return one point without calling cost.
Without a minimum step cost the search is uninformed: it uses a zero heuristic, which keeps it correct for zero and fractional costs but makes it expand cells in every direction, as Dijkstra does. On a 256 by 256 map that is several times slower than a guided search. For speed, call AStarWithMinCost with the smallest cost any step can have, 1 for a map where every move costs at least 1.
Example:
```go
package main
import (
"fmt"
"github.com/matjam/bunyip/grid"
)
// A five-by-three map with a wall in the middle column, open at the top.
var walls = []string{
".....",
"..#..",
"..#..",
}
func cost(from, to grid.Point) float32 {
if walls[to.Y][to.X] == '#' {
return grid.Blocked
}
return 1
}
func main() {
path := grid.AStar(5, 3, grid.Point{X: 0, Y: 2}, grid.Point{X: 4, Y: 2}, false, cost)
fmt.Println(len(path)-1, "steps:", path)
}
```
Output:
```
8 steps: [{0 2} {1 2} {1 1} {1 0} {2 0} {3 0} {4 0} {4 1} {4 2}]
```
#### AStarWithMinCost
```go
func AStarWithMinCost(w, h int, start, goal Point, diagonal bool, cost Cost, minCost float32) []Point
```
AStarWithMinCost finds a path as AStar does, using minCost to guide the search. A finite positive minCost promises a lower bound on every traversable step returned by cost, including diagonals. The heuristic scales Manhattan distance for four-way moves and Chebyshev distance for eight-way moves. The search does not scan the map to check the bound; overstating it loses the cheapest-path guarantee. Zero, negative, NaN and infinite bounds use the same zero heuristic as AStar. Scratch comes from a pool and may allocate on first use or growth; use Pathfinder.AStarWithMinCost with a reusable output buffer for repeated searches without allocations after buffers have grown.
#### Downhill
```go
func Downhill(dist *Grid[float32], p Point, diagonal bool) (Point, bool)
```
Downhill returns the neighbour of p with the lowest value in a Dijkstra map, and false when none is lower (p is a source or cut off). p must be in bounds. This compares cell values only; it does not test passability, diagonal restrictions or the cost of the chosen edge. It can stop on a zero-cost plateau and does not guarantee a cheapest route for weighted or directed movement. Multiplying a map by a negative factor before descending makes creatures flee instead.
#### FloodFill
```go
func FloodFill(w, h int, start Point, passable func(Point) bool) []Point
```
FloodFill returns every cell reachable from start through passable cells by four-way moves, start included when passable.
#### Line
```go
func Line(a, b Point) []Point
```
Line returns the cells on a straight line from a to b inclusive (Bresenham), in order from a.
#### Point.Add
```go
func (p Point) Add(q Point) Point
```
Add offsets the point.
#### Point.Chebyshev
```go
func (p Point) Chebyshev(q Point) int
```
Chebyshev is the eight-way step distance.
#### Point.Manhattan
```go
func (p Point) Manhattan(q Point) int
```
Manhattan is the four-way step distance.
### Vision
```go
type Vision struct {
// contains filtered or unexported fields
}
```
Vision holds the scratch space a field of view cast needs so that repeated casts allocate nothing. The zero value is ready to use, and one Vision serves any radius. A Vision is not safe for concurrent use; give each goroutine its own.
#### Vision.FOV
```go
func (v *Vision) FOV(origin Point, radius int, opaque func(Point) bool, visit func(Point))
```
FOV computes which cells are visible from origin within radius, calling visit once for each including the origin. It behaves exactly as the package-level FOV and reuses the caster's scratch space. Do not start another cast on this Vision from opaque or visit.