Package github.com/matjam/bunyip/grid

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.

Index

Variables
func FOV(origin Point, radius int, opaque func(Point) bool, visit func(Point))
type Cost
type Grid
type Pathfinder
type Point
type Vision
- func (v *Vision) FOV(origin Point, radius int, opaque func(Point) bool, visit func(Point))

Variables

var (
	Dirs4 = []Point{ /* … */ }
	Dirs8 = []Point{ /* … */ }
)

Dirs4 and Dirs8 are the neighbour offsets, cardinals first.

var Blocked = float32(math.Inf(1))

Blocked is the step cost of an impassable move.

Functions

FOV source

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

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

type Cost source

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.

type Grid source

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 source

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

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 source

func New[T any](w, h int) *Grid[T]

New makes a grid of zero cells.

At source

func (g *Grid[T]) At(x, y int) T

At returns the cell, or the zero value outside the grid.

Each source

func (g *Grid[T]) Each(fn func(x, y int, v T))

Each visits every cell in row-major order.

Fill source

func (g *Grid[T]) Fill(v T)

Fill sets every cell.

In source

func (g *Grid[T]) In(x, y int) bool

In reports whether the coordinate is inside the grid.

Set source

func (g *Grid[T]) Set(x, y int, v T)

Set writes a cell; writes outside the grid are ignored.

type Pathfinder source

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 source

func NewPathfinder(w, h int) *Pathfinder

NewPathfinder makes a pathfinder for a w by h map.

AStar source

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.

AStarWithMinCost source

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.

DijkstraInto source

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.

Resize source

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.

Size source

func (p *Pathfinder) Size() (w, h int)

Size is the map size the pathfinder is set up for.

type Point source

type Point struct{ X, Y int }

Point is a cell coordinate.

AStar source

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

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 source

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 source

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 source

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 source

func Line(a, b Point) []Point

Line returns the cells on a straight line from a to b inclusive (Bresenham), in order from a.

Add source

func (p Point) Add(q Point) Point

Add offsets the point.

Chebyshev source

func (p Point) Chebyshev(q Point) int

Chebyshev is the eight-way step distance.

Manhattan source

func (p Point) Manhattan(q Point) int

Manhattan is the four-way step distance.

type Vision source

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.

FOV source

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.

Source files

bench_test.go example_test.go grid.go grid_test.go mincost_test.go pathcost_test.go