CrawfisSoftware.Grid 1.2.1

CrawfisSoftware.Grid

2D grid (rectangular) graph primitives and utilities used in maze generation and other procedural content generation (PCG) algorithms.

This repository ships the CrawfisSoftware.Grid NuGet package and provides:

• A generic Grid<N,E> that implements IIndexedGraph<N,E> (index-based graph where each cell is a node).
• A convenience OccupancyGrid (Grid<bool,bool>) for walkable/blocked maps.
• A Direction flags enum (N, E, S, W) with helpers.
• Utilities for pathfinding and stamping/tiling grids into larger grids.

Targets: netstandard2.1, net8.0.

Package

• NuGet: CrawfisSoftware.Grid
• Repository: https://github.com/Crawfis-Software/CrawfisSoftware.Grid

Install

dotnet add package CrawfisSoftware.Grid

Concepts

Grid coordinates and indices

Cells are addressed in two ways:

• Grid coordinates: (column, row) aka (i, j).
• Node index: index = column + row * width.

The grid is 4-connected by default (Von Neumann neighborhood): West, North, East, South.

Wrapping (toroidal grids)

Grid<N,E> supports optional wrapping:

• WrapHorizontal: right edge connects to left edge.
• WrapVertical: top edge connects to bottom edge.

Main API

Direction

Direction is a [Flags] enum with the primary compass directions:

• Direction.N, Direction.E, Direction.S, Direction.W

Helpers in DirectionExtensions:

• Reverse()
• GetEdgeDirection(i, j, width)
• shape classification: IsDeadEnd(), IsStraight(), IsTurn(), IsTJunction(), IsCrossSection()
• NumberOfExits()

Grid<N,E>

Grid<N,E> is an index-based graph where each cell is a node label of type N, and each directed edge has a label of type E.

Common members:

• Width, Height
• GetNodeLabel(column, row) and GetNodeLabel(nodeIndex)
• GetEdgeLabel(column, row, direction)
• Neighbors(nodeIndex)
• OutEdges(nodeIndex), InEdges(nodeIndex), Edges
• TraverseEdge(column, row, direction)
• TryGetGridLocation(nodeIndex, out column, out row)

Edge directions are configurable via EdgeDirections.

OccupancyGrid

OccupancyGrid is a specialized Grid<bool,bool> for maps where each cell is either occupied/walkable (true) or blocked (false).

Key members:

• MarkCell(column, row, cellValue)
• Fill(cellValue) and Fill(cellValue, leftColumn, rightColumn, bottomRow, topRow)
• Clear()
• GridValues to access the underlying bool[,]
• ToString() prints a simple ASCII view

Extension methods:

• Invert() returns a new inverted grid.

Pathfinding

GridUtility includes a shortest-path helper for Grid<int,int>:

• FindShortestPath(this Grid<int,int> grid, EdgeCostDelegate<int> edgeCostFunction, int start, int target, float heuristicAcceleration = 1.6f)

This delegates to the path/query infrastructure provided by the dependent graph packages (see Dependencies).

Traversal utilities

GridTraversalExtensions contains helpers for computing boundaries from traversals:

• WalkableGridBoundary(startingIndex, maxDistance) uses breadth-first traversal edges.
• WalkableBoundary(startingIndex, costDelegate, maxDistance) uses Dijkstra traversal edges.

Both return boundary segments as (cellIndex, offset) where offset indicates which edge of the cell is crossed.

Stamps and tiling

Stamps are small OccupancyGrid instances that can be “stamped” into a larger grid.

• StampSet<TName> maps a key (e.g. Direction, bool) to a stamp.
• GridUtility.StampInto(grid, stamp, lowerLeftColumn, lowerLeftRow) copies a stamp into a larger grid.
• GridUtility.ReplaceWithStamps(grid, stampSet) expands a grid into a larger one by replacing each source cell with a stamp.

StampSetFactory provides common stamp sets for turning direction-encoded mazes into higher-resolution occupancy grids:

• CreateStampSet3x3Bool() (corners closed)
• CreateStampSet3x3BoolOpen() (corners open where appropriate)
• CreateStampSet2x2Bool()
• CreateStampSetOpenNxM(width, height, horizontalWallThickness, verticalWallThickness)
• CreateStampSetClosedNxM(width, height, horizontalWallThickness, verticalWallThickness, doorSize = -1)

Examples

Create and print an OccupancyGrid

using CrawfisSoftware.Collections.Graph;

var grid = new OccupancyGrid(width: 10, height: 6);
grid.Fill(true);

// Block a small region
grid.Fill(false, leftColumn: 3, rightColumn: 5, bottomRow: 2, topRow: 3);

Console.WriteLine(grid);

Invert a grid

using CrawfisSoftware.Collections.Graph;

var inverted = grid.Invert();

Expand a direction grid into a larger occupancy grid (stamping)

This is commonly used when you have a coarse grid (e.g., where each cell encodes open directions) and you want a higher-resolution occupancy map.

using CrawfisSoftware.Collections.Graph;

// Assume you have a grid where each cell is a Direction (N/E/S/W flags)
// and you want to expand it into a 3x3-per-cell occupancy representation.
var stamps = StampSetFactory.CreateStampSet3x3BoolOpen();

// Example: treat the source as an occupancy grid of "open" vs "closed".
// If you already have a Direction grid, you would typically register direction stamps
// and stamp per-cell accordingly (see StampSetFactory).

// For bool-driven stamping:
var boolStamps = GridUtility.CreateOccupancyStampSet(width: 3, height: 3);
var expanded = GridUtility.ReplaceWithStamps(grid, boolStamps);

Find a shortest path in a Grid<int,int>

using CrawfisSoftware.Collections.Graph;

// Create a simple grid where nodes/edges are ints.
var nav = new Grid<int, int>(
    width: 20,
    height: 10,
    nodeAccessor: null,
    edgeAccessor: null);

// EdgeCostDelegate<int> comes from the CrawfisSoftware graph dependencies.
// The simplest cost function returns a constant.
EdgeCostDelegate<int> cost = _ => 1;

int start = 0;
int target = 199;

var pathEdges = nav.FindShortestPath(cost, start, target);
foreach (var e in pathEdges)
{
    Console.WriteLine($"{e.From} -> {e.To}");
}

Dependencies

This package builds on the CrawfisSoftware graph abstractions:

• CrawfisSoftware.IGraph
• CrawfisSoftware.Graph

These dependencies provide interfaces such as IIndexedGraph<N,E> and algorithms/utilities such as traversal and path-query helpers.

Build

dotnet build

Pack (NuGet)

dotnet pack -c Release

Repository layout

• src/ - library source
• README.md - package readme (packed into NuGet)

Contributing

Issues and pull requests are welcome:

• https://github.com/Crawfis-Software/CrawfisSoftware.Grid/issues

License

MIT (see package metadata in the project file).