Grid

Beta: Stable core, open to refinement pre-1.0.0

Summary

A mutable 2D grid with efficient region views, spatial operations, and seamless interoperability with Pipe2D. Store, edit, and transform 2D data with an ergonomic API designed for practical use.

Features

• Mutable 2D storage with type safety
• Zero-copy region views - edit or provide subgrids and transformation layers without copying
• Spatial operations - fill, paste, flood fill, pathfinding
• First-class Pipe2D interoperability – use grids as sources for pipes, or pipes as sources for grids
• Consistent API - for grids, regions, and your existing 2D structures
• Mask support - apply operations to arbitrary shapes

Example

npm i @xtia/grid

import { Grid } from "@xtia/grid"; // ~5.1kb gzipped (2.5kb + Pipe2D dep)

// initialise a 30x20 Grid<number> of 0's
const numGrid = Grid.solid(30, 20, 0);

// change a value
numGrid.set(3, 3, 50);

// initialise a chessboard
const chessGrid = Grid.init(8, 8, (x, y) => 
	(x + y) % 2 === 0 ? 'black' : 'white'
);

// read a value
const colour = chessGrid.get(4, 5);

// initialise a grid from a Pipe2D
const source = imagePipe
	.crop(10, 10, 64, 64)
	.scale(.5)
	.rotateLeft();
const grid = Grid.init(source);

Wrapping existing structures

Use Grid's interface and features over any read/write 2D structure:

const gameMap = [
	[0, 1, 3, 2],
	[1, 0, 1, 0],
	[3, 1, 0, 2],
	[2, 0, 2, 3]
];

// create a *live view* Grid over gameMap
const grid = Grid.wrap(
	gameMap[0].length, // width
	gameMap.length, // height
	(x, y) => gameMap[y][x], // get
	(x, y, value) => gameMap[y][x] = value // set
);

// reading the grid = reading the source
gameMap[0][0] = 5;
console.log(grid.get(0, 0)); // 5
// writing to the grid = writing to the source
grid.set(3, 3, 6);
console.log(gameMap[3][3]); // 6

Regions

Use grid.liveRegion(x, y, w, h) to define a subgrid. The subgrid is zero-copy view into the parent; changes to the subgrid affect the parent and vice-versa.

// game map with terrain
const world = Grid.solid(100, 100, "grass"); // Grid<string>

// add a lake
world.liveRegion(30, 30, 20, 20).fill("water");

// add mountains around the lake with a circular mask
const centre = world.cells.get(40, 40);
const mask = (x: number, y: number) => {
	const dist = Math.hypot(x - centre.x, y - centre.y);
	return dist > 12 && dist < 18; // mountain ring
};
world.writeMask(mask).fill("mountain");

// get a view of just the interesting area
const lakeRegion = world.liveRegion(25, 25, 30, 30);

// do we want a distinct, self-contained copy of the region?
const lakeGrid = Grid.init(lakeRegion);

Transformation Layers

grid.liveMap(read, write) creates a zero-copy view that reads and writes the parent through the provided transformation functions.

const spriteMap = world.liveMap(
	type => type + ".png", // add .png on parent-read
	sprite => sprite.replace(/\..*/, '') // remove it on parent-write
);

console.log(spriteMap.get(0, 0)); // read the transformed view: "grass.png"
spriteMap.set(1, 0, "forest.png"); // modify the view
console.log(world.get(1, 0)); // read the parent: "forest"

For one-way read-mapping, use grid.valuePipe - a Pipe2D view into the grid's data.

// create a one-way, player-centred sprite map
const viewport = world.valuePipe
	.oob("mountain")
	.map(t => t + ".png")
	.crop(playerX - 5, playerY - 5, 10, 10);

// or get a list of locations of cells with mountains
const mountainCells = world.cells.toFlatArrayXY()
	.filter(cell => cell.value === "mountain")
	.map(cell => [cell.x, cell.y]);

// or get a live, renderable minimap
import { C } from "@xtia/rgba";

const colourMap = new Map(Object.entries({
	grass: C.x0f0,
	water: C.x00f,
	forest: C.x080,
	mountain: C.xa70
}));
const minimap = world.valuePipe
	.map(colourMap)
	.floorCoordinates()
	.crop(viewX, viewY, vw, vh)
	.stretch(canvas.width, canvas.height);

Write-masking

Any Source2D<boolean> ({ width, height, get(x, y) }), or function of (x, y) => boolean, can be used to create a layer that restricts or allows changes to cells based on their position.

writeMask(mask) returns a zero-copy view that silently rejects changes at positions for which the mask returns false.

// a shape
const circle = grid.cells.get(50, 50)
  .createVisibilityMap(() => true, { maxDistance: 10 });

// a pattern
const chessboard = (x, y) => (x + y) % 2 === 0;

const stencil = Grid.init(100, 100, () => Math.random() < .5));
stencil.liveRegion(2, 2, 97, 97).fill(true);

grid.writeMask(circle).fill(1);
grid.writeMask(chessboard).fill(2);
grid.writeMask(stencil).fill(3);
grid.writeMask(() => Math.random() < .7).fill(4);

Cell interface

grid.cells provides a Pipe2D, for convenient transformation, of Cell objects, each representing a live view into a grid location.

const topLeft = world.cells.get(0, 0);
console.log(topLeft.value); // "mountain"

topLeft.value = "forest"; // modifies the underlying data
console.log(spriteMap.get(0, 0)); // now "forest.png";

// navigate by offset
const adjacentCell = topLeft.look(1, 0);
console.log(adjacentCell?.x, adjacentCell?.y); // 1, 0

Cells provide methods for locational utilities such as pathfinding and visibility mapping.

Cells are unique to, owned by, and coordinated relative to the view that provided them. Their pathfinding and visibility mapping features are unaware of space outside of their view's bounds.

Pipe2D integration

Pipe2D, a transformable, live read-view of any 2D space, can be used to initialise, paste to and read from a Grid. Providing grid.cells and grid.valuePipe as pipes makes many otherwise cumbersome operations trivial:

// Conway's Game of Life
const evolve = () => grid.paste(grid.cells.map(cell => {
	const food = cell.allNeighbours.filter(c => c.value).length;
	return cell.value ? food == 2 || food == 3 : food == 3
}));

For more information about this implementation, and a live demo, see Grid of Life.

Neighbours

cell.cardinalNeighbours and cell.allNeighbours each provide an array of adjacent Cells, the latter including diagonals:

// derive a display number for clicked cells in Minesweeper
const numOfAdjacentMines = clickedCell.allNeighbours
	.filter(cell => cell.value.isMine)
	.length;

Path finding

findPath() computes an optimal path from a cell to another location in the grid, accounting for cell/traversal costs according to a user-provided predicate or Map<T, number>.

const costs = {
	grass: 1,
	water: Infinity,
	mountain: Infinity,
	forest: 2
};

const start = world.cells.get(5, 5);
const destination = world.cells.get(90, 90);

const path = start.findPath(
	destination, // or simply [90, 90]
	(cell) => costs[cell.value]
); // Cell<string>[]

Map<T> costing

As well as a callback of (cell, context) => number, findPath() can accept a Map<T> to assign traversal costs to values.

const costs = new Map<string, number>();
costs.set("grass", 1);
costs.set("forest", 2);

// ...

const path = start.findPath(destination, costs);

Visibility mapping

createVisibilityMap() returns a Pipe2D<boolean> that maps which cells are 'visible' from the starting point, according to a user-provided predicate to determine which cells block vision.

// createVisibilityMap(isClear);
const visibility = start.createVisibilityMap(
	cell => cell.value === "grass" // anything except grass blocks vision
);

screenGrid.writeMask(visibility).paste(spriteMap, 0, 0);

Reusing path data

Use cell.getPathMap(costFunc) to create a Pipe2D of optimal paths from the parent cell. The grid space is explored once to produce an internal traversal map, and paths to individual cells are constructed from that data (and cached) when that pipe is queried.

const pathMap = start.getPathMap(c => costs[c.value]);

const pathToCentre = pathMap.get(50, 50);
const pathToCorner = pathMap.get(99, 99);

Unlike visibility maps, which are lazily evaluated according to the supplied isClear function when the map is queried (but can be easily cached with visMap.withCache()), path maps use a relatively expensive traversal map that's created when the map is created. This distinction is hinted through the create* vs get* naming.

The storage layer

Grid itself is an interface that sits on top of a synchronous 2D read/write mechanism. GridBase is a subclass of Grid with built-in storage.

Although the factory methods Grid.solid<T>() and Grid.init<T>()) belong to Grid, they return a GridBase<T>. Grid.wrap<T>() and Grid.wrapBytes(), on the other hand, return Grid<T> and Grid<U8A> respectively, as they use storage layers provided by the user. The only API distinction is that GridBase provides a 'change' event, via grid.on("change", handler).

We can suppress the 'change' event until a process concludes with grid.batchUpdate(callback).

Save and load

Pipe2D makes it easy to save and restore grid data:

const snapshot = world.valuePipe.stash();

const restored = Grid.init(snapshot);
// or paste it to an existing grid
world.paste(snapshot);

For persistent storage or transmission, Pipe2D can export as array:

const saved = snapshot.toFlatArrayXY(); // ["grass", "forest", "grass", ...]

const restoredSnapshot = Pipe2D.fromFlatArrayXY(saved);

Experimental methods

Grid.wrapBytes()

Access a byte array as a Grid of 'byte chunks'; useful, for example, for wrapping canvas ImageData as a Grid interface.

Reading a value from a Grid created with this method yields a live subarray from the source, and writing to the grid updates the source at the computed offset.

// wrapping canvas ImageData
const imageData = canvasContext.getImageData(0, 0, canvas.width, canvas.height);
const imageGrid = Grid.wrapBytes(imageData);

// manipulate a chunk directly
const pixel = imageGrid.get(5, 5);
pixel[3] /= 2; // chunks are live subarrays

// optionally wrap byte chunks with a colour library
const rgbaGrid = imageGrid.liveMap(
	bytes => new RGBA(bytes),
	rgba => rgba.asBytes
);

rgbaGrid.liveRegion(0, 0, 5, 5).fill(parseRGBA("#f00"));

// write back
canvasContext.putImageData(imageData, 0, 0);

wrapBytes() can accept any byte array, yielding a chunk size of (bytes.length / (width * height)):

const byteGrid = Grid.wrapBytes(
	width,
	height,
	bytes, // Uint8Array or Uint8ClampedArray
);