Grid

38 min read

Square, hex, and triangle grid utilities you can use to address cells, edges, and corners in world space, run neighbor and range queries, draw lines of sight, and flood-fill connected regions in any tile-based game.

Summary

A grid is the world reduced to a regular pattern of cells. Three topologies cover almost every grid-aligned game: the square grid for top-down maps, boards, and tile puzzles; the hex grid for war games, strategy maps, and any system that wants six symmetric directions of movement; and the triangle grid for surfaces that need a third symmetric primitive. Scylla Core provides all three with a shared API surface and the same addressing model: every cell, every edge between two cells, and every corner shared by adjacent cells has a typed coordinate you can look up, map to world space, and use as a key into per-edge or per-corner data.

Each topology comes in two storage variants:

  • The dense grids (ScyllaSquareGrid<TCell>, ScyllaHexGrid<TCell>, ScyllaTriGrid<TCell>) preallocate every cell in a flat array and provide O(1) random access. They are the right pick for bounded, fully-populated maps where most cells carry data.
  • The sparse grids (ScyllaSparseSquareGrid<TCell>, ScyllaSparseHexGrid<TCell>, ScyllaSparseTriGrid<TCell>) store cells in a hash map and grow on demand. They are the right pick for unbounded worlds, for grids where only a small fraction of cells are populated, or when the bounds are not known at construction.

Beyond cell storage, each topology provides an addressing model that distinguishes three first-class concepts:

  • A cell is identified by a coord (SquareCoord, HexCoord, TriCoord); cells store the gameplay payload.
  • An edge is identified by an edge coord (SquareEdgeCoord, HexEdgeCoord, TriEdgeCoord) that pairs an owning cell with an EdgeDirection; edges are where wall, fence, river, and door data live.
  • A corner is identified by a corner coord (SquareCornerCoord, HexCornerCoord, TriCornerCoord); corners are where shared markers, junctions, and decorations live.

Edge and corner data are stored in dedicated EdgeMap<TData> and CornerMap<TData> containers that mirror the cell grid but key off the corresponding edge or corner address.

A GridLayout value (SquareGridLayout, HexGridLayout, TriGridLayout) controls the world-space placement of every cell. Cell size, optional origin offset, and (for hex grids) pointy-top vs flat-top orientation are encoded in the layout, and each layout exposes GridToWorld and WorldToGrid for converting between coordinates and Unity world space. Convenience helpers cover the rest: GridUtil.Distance, GridUtil.DrawLine, GridUtil.GetRange, GridUtil.GetRing, GridUtil.FloodFill, hex offset and doubled coordinate conversions, and AsSynchronized wrappers for grids that need concurrent access. The grid integrates with the broader framework through the IScyllaCollection contract (Count, IsEmpty, ThreadSafety) and through ScyllaGridGraphAdapter (see Graph) for plugging a grid into the pathfinding and graph algorithms.

Use the grid structures for:

  • Roguelikes, tactics games, board games, and turn-based strategy games.
  • Tile-based platformers and dungeon crawlers.
  • Hex war games and strategy maps.
  • Voxel surface annotations and chunked map metadata.
  • Wall, fence, river, and door data (edges) and corner markers (corners).
  • Procedural map generation paired with the Procedural Map Generation utilities.
  • Any system that needs explicit, lossless, integer-addressed spatial keys.

Features

The three topologies share a contract; capabilities below are listed once and apply across the topologies unless noted.

  • Three topologies, one contract. Square, hex, and triangle grids share the IScyllaGrid<TCoord, TCell> interface for the cell surface. Topology-specific algorithms (range queries, hex rings, triangle adjacency) live on the concrete types and on GridUtil.
  • Dense and sparse storage. Each topology ships with both a dense, fully-preallocated grid for O(1) random access and a sparse, dictionary-backed grid for unbounded extent. Both implement the same interface.
  • Cell, edge, and corner addressing. Every grid distinguishes cells (gameplay data), edges (walls, fences, doors, rivers), and corners (junction markers, decorations). Dedicated EdgeMap<TData> and CornerMap<TData> containers store edge and corner data keyed by the corresponding coord.
  • World-space layouts. SquareGridLayout, HexGridLayout, and TriGridLayout carry cell size, origin offset, and (for hex) orientation. GridToWorld and WorldToGrid convert in both directions and are also exposed as methods on every grid.
  • Allocation-free neighbor queries. GetNeighborsNonAlloc(coord, Span<TCoord>, ...) fills a caller-provided Span with adjacent coords. No List allocation, no garbage. Square grids also accept a SquareAdjacency argument (VonNeumann for 4-way, Moore for 8-way).
  • Range, ring, and spiral queries. Hex grids and GridUtil expose GetRange, GetRing, and GetSpiral for filling a Span with every cell within a radius, at exactly a radius, or in a spiral order out from a center.
  • Bresenham and supercover line drawing. GridUtil.DrawLine walks a straight line between two coords with Bresenham stepping; GridUtil.DrawLineSupercover additionally returns every cell the geometric line crosses (square only). The hex grid exposes DrawLine natively as well.
  • Distance metrics. Square grids support Manhattan, Chebyshev, Euclidean, and Octile (diagonal-aware) distance. Hex distance is the symmetric cube-coord distance. Triangle distance follows the topology’s natural step count.
  • Fluent builders. Every grid type exposes CreateBuilder() with WithSize, WithLayout, WithDefaultValue, and Synchronized setters. Required vs optional configuration is checked at Build() time.
  • Synchronized wrappers. Every grid exposes AsSynchronized(object syncRoot = null) that returns a thread-safe wrapper backed by a lock. The builder’s Synchronized setter produces the same wrapper directly.
  • Generic flood fill. GridUtil.FloodFill<TCoord> works on any coordinate type. You supply an isPassable predicate and a NeighborWriter<TCoord> delegate, so the same routine handles square, hex, and triangle topologies, or any custom coord type.
  • Hex coordinate conversions. GridUtil converts between axial hex coordinates and four common offset systems (odd-r, even-r, odd-q, even-q) plus the doubled-width and doubled-height systems used by some tilemap exporters. DoubledWidthDistance and DoubledHeightDistance compute hex distance directly in doubled coordinates without converting to axial.
  • Hex diagonal neighbors. HexCoord.Diagonal(int index) and HexCoord.DiagonalNeighbor(int direction) access the six diagonal directions (two steps through a shared corner vertex, cube distance 2).
  • Pivot-based hex reflections. Overloads HexCoord.ReflectQ/R/S(coord, center) reflect around an arbitrary pivot rather than the origin, translating to origin, reflecting, then translating back.
  • Non-uniform hex layout. HexGridLayout accepts independent sizeX and sizeY circumradii for elliptical hex cells. Both are exposed as properties (SizeX, SizeY).
  • Range intersection. GridUtil.GetRangeIntersection returns all hexes that fall inside two overlapping hex ranges simultaneously, using per-axis cube-interval math.
  • Spiral index math. GridUtil.SpiralRingStart, SpiralIndexToRadius, SpiralIndexToCoord, and CoordToSpiralIndex work with spiral traversal order without traversing the full spiral.
  • Movement range with obstacles. GridUtil.GetReachable runs a step-capped BFS from a start hex, respecting a per-cell obstacle predicate, and fills a dictionary with every reachable hex and its minimum step count.
  • Field of view. GridUtil.IsVisible checks line of sight between two hexes. GridUtil.ComputeFieldOfView fills a Span<HexCoord> with all hexes visible from a center within a given radius.
  • Map shape region generators. GridUtil.GetHexagonalRegion, GetRectangularRegion (with HexLayoutMode.Slanted or Staggered), GetTriangularRegion, and GetRhombusRegion fill a Span<HexCoord> with the coordinates of a geometrically defined map region.
  • Sparse hex grid wrappers. ScyllaSparseHexGrid exposes QMin and RMin for bounded grids, plus GetRange, GetRing, GetSpiral, and DrawLine instance methods that filter results to occupied cells only.
  • Foreach enumeration. Every grid exposes a struct Enumerator and GetEnumerator() so foreach over the populated cells is allocation-free.

Topologies

The three topologies differ in the number of neighbors per cell, the distance math, and the world-space layout. Pick the topology that matches your game’s movement and adjacency rules.

TopologyCoord typeCell neighborsEdge neighborsDistance metricsNotes
SquareSquareCoord4 (Von Neumann) or 8 (Moore)4Manhattan, Chebyshev, Euclidean, OctileDefault for roguelikes, board games, and most tile-based games. The Von Neumann/Moore choice determines whether diagonal movement counts as adjacency.
HexHexCoord66Hexagonal (cube-coord max)Symmetric six-way movement, no diagonal/orthogonal split, uniform distance in every direction. Pointy-top or flat-top orientation is fixed at layout time. Use for war games and strategy.
TriangleTriCoord3 (edge) or up to 12 (vertex)3Triangular step distanceAlternating up/down triangles share three edge neighbors and twelve vertex neighbors. Useful for tri-aligned surfaces, geodesic-style maps, and dual-triangle decorations on hex topologies.

The SquareAdjacency enum (VonNeumann, Moore) selects 4-way or 8-way square adjacency at the call site. Hex and triangle grids do not need an adjacency parameter because their neighbor counts are fixed by topology.

Addressing model

A grid identifies three kinds of spatial objects. Understanding which is which is the difference between fighting the API and using it for what it was built for.

ConceptCoord typesStorageUse for
CellSquareCoord, HexCoord, TriCoordThe grid itselfGameplay payload: tiles, units, terrain type, sprite index, occupancy.
EdgeSquareEdgeCoord, HexEdgeCoord, TriEdgeCoord*EdgeMap<TData>Walls, fences, rivers, doors, anything that lies between two adjacent cells.
CornerSquareCornerCoord, HexCornerCoord, TriCornerCoord*CornerMap<TData>Junctions, intersections, towers, gems, markers that sit at the vertex of cells.

Each coord type carries enough information to round-trip through equality and dictionary lookup, exposes GridToWorld via its associated layout, and can be enumerated from any adjacent coord. For example, SquareEdgeCoord.GetEdgesOfCellNonAlloc(cell, buffer) fills a Span<SquareEdgeCoord> with the four edges of a given cell, and SquareEdgeCoord.GetCellsNonAlloc(edge, buffer) returns the two cells an edge separates.

Recipes

These recipes cover every part of the grid public surface. Each one is a self-contained answer to a single game-development problem, so scan the names, find the one that matches what you are building, and copy the solution. The first recipe gets a square grid up and running; the rest assume you have one.

Lay out a tile-based playfield

Problem. You are starting a new dungeon crawler or tactics game and you need a grid of tiles up and running with the minimum amount of ceremony. The grid has to know its size, how large each cell is in world space, and what value to start every tile at. The fluent builder is the shortest path.

Solution. WithSize and WithLayout are required; everything else has a default. The non-builder constructor is also available for callers that prefer positional arguments.

/* A 32x32 dense square grid storing TileType cells, with 1.0 unit cell size. */
var layout = new SquareGridLayout(cellWidth: 1f, cellHeight: 1f);

var map = ScyllaSquareGrid<TileType>.CreateBuilder()
    .WithSize(width: 32, height: 32)        /* Required. Defines the grid extent.              */
    .WithLayout(layout)                     /* Required. Cell size and origin in world space.   */
    .WithDefaultValue(TileType.Floor)       /* Optional. Every cell starts at TileType.Floor.   */
    .Build();

Read, write, and probe cells

Problem. You have a tile-based game and you need to read and write cells constantly – setting walls during level generation, reading tile types for pathfinding, probing bounds before moving a unit. Anyone who has shipped a tile-based game has spent more lines on cell access than on anything else, so the surface is deliberately small.

Solution. The cell surface is TryGet, TrySet, Contains, and an indexer. Reads and writes that fall outside the grid’s extent fail safely on the Try* calls and throw on the indexer.

/* Indexer write. Throws if the coord is out of bounds. */
map[new SquareCoord(0, 0)] = TileType.Wall;

/* TrySet returns false on out-of-bounds rather than throwing.
 * Use when the coord comes from gameplay data you have not validated yet. */
var placed = map.TrySet(new SquareCoord(31, 31), TileType.Door);

/* Indexer read. */
var tile = map[new SquareCoord(5, 5)];

/* Try-read pattern for unverified coords; typical in pathfinding expansion
 * where neighbor coords may lie outside the map boundary. */
if (map.TryGet(new SquareCoord(50, 50), out var farTile))
{
    Use(farTile);
}

/* Cheap existence probe; returns true when the coord maps to a valid cell. */
var present = map.Contains(new SquareCoord(0, 0));

Walk every cell in a grid

Problem. There is always a system that wants to visit every cell once: a fog-of-war reveal pass, a Game of Life tick, a save-time tile serializer, a lighting system that needs to tint every floor tile. You want that pass to be fast and allocation-free.

Solution. Every grid exposes a struct Enumerator and GetEnumerator, so foreach is allocation-free. Two-axis iteration via nested loops is equally cheap and gives you direct coord access.

/* Allocation-free foreach over every populated cell. The Enumerator is a struct,
 * so the loop itself does not allocate even on a 256x256 map. */
foreach (var entry in map)
{
    var coord = entry.Coord;
    var cell  = entry.Value;
    Visit(coord, cell);
}

/* Explicit coord iteration for dense grids. Use when you need the coord
 * constructed locally and prefer index-driven logic. */
for (var row = 0; row < 32; row++)
{
    for (var col = 0; col < 32; col++)
    {
        var coord = new SquareCoord(col, row);
        var cell  = map[coord];
        Visit(coord, cell);
    }
}

/* Bulk reset to a single value. Faster than iterating and writing manually:
 * use it to clear the map between dungeon floors. */
map.Fill(TileType.Floor);

Find adjacent cells for A* and fire spread

Problem. You are writing an A* pathfinder, a fire-spread system, or a UI tooltip that lists adjacent terrain. In every case the question is not “what is here” but “what surrounds this cell”. You need the neighboring coords, and you need them without triggering a garbage collection mid-frame.

Solution. GetNeighborsNonAlloc writes adjacent coords into a caller-supplied Span<TCoord> and returns how many were written. Allocate the buffer once at the largest expected size and reuse it on every query. Square grids take a SquareAdjacency argument that selects 4-way or 8-way neighbors.

/* Allocate the buffer once at the largest expected size; reuse for every query.
 * 8 covers Moore square, which is the biggest square case. */
Span<SquareCoord> neighbors = stackalloc SquareCoord[8];

/* 4-way (Von Neumann): N, E, S, W. Use for classic roguelike movement where
 * diagonal steps are not allowed. */
var count = map.GetNeighborsNonAlloc(
    coord: new SquareCoord(5, 5),
    buffer: neighbors,
    adjacency: SquareAdjacency.VonNeumann);

for (var i = 0; i < count; i++)
{
    Inspect(neighbors[i]);
}

/* 8-way (Moore): all cardinal and diagonal neighbors. Use for movement systems
 * where cutting across corners is allowed, or for Conway-style simulations. */
count = map.GetNeighborsNonAlloc(
    coord: new SquareCoord(5, 5),
    buffer: neighbors,
    adjacency: SquareAdjacency.Moore);

Convert a screen tap to a grid cell

Problem. Your game needs two conversions constantly: putting a unit sprite at the world position of a given cell, and turning a mouse click or touch tap back into the cell the player selected. The grid knows its own layout and can do both conversions, so you do not need to duplicate the cell-sizing math anywhere in your codebase.

Solution. GridToWorld and WorldToGrid are exposed directly on every grid instance (via the layout it was built with). WorldToGrid returns the nearest cell for any world position, including ones outside the grid boundary, so always follow it with a Contains check.

/* Place a unit at the world position of grid cell (5, 5).
 * GridToWorld returns Vector2; lift to 3D for Unity's transform. */
var worldPos = map.GridToWorld(new SquareCoord(5, 5));
unit.transform.position = new Vector3(worldPos.x, 0f, worldPos.y);

/* Convert a click position back to a grid cell. The raycast hits the
 * ground plane; WorldToGrid snaps the hit point to the nearest cell. */
var ray = Camera.main.ScreenPointToRay(Input.mousePosition);
if (groundPlane.Raycast(ray, out var hit))
{
    var hitPoint    = new Vector2(hit.point.x, hit.point.z);
    var clickedCell = map.WorldToGrid(hitPoint);

    if (map.Contains(clickedCell))
    {
        HighlightCell(clickedCell);
    }
}

Measure range and draw line of sight

Problem. Anyone who has built a tactics game knows that “how far apart are these two cells?” and “which cells does this line of sight cross?” are the questions the rules engine asks constantly. You need cell-to-cell distance with the right metric for your movement rules, and you need straight-line rasterization for sight, shooting, and ability targeting.

Solution. Cell-to-cell distance and straight-line rasterization live in GridUtil and on the coord types as DistanceTo shortcuts. Square distance accepts a metric enum; hex distance is uniformly defined by the cube-coordinate formula. Two line helpers give you Bresenham stepping and supercover stepping – pick the one that matches your game’s corner rules.

/* Square distance with explicit metric selection. Manhattan counts orthogonal
 * steps only, Chebyshev counts the longer axis (good for 8-way movement),
 * Euclidean is the true geometric distance. */
var manhattan = GridUtil.Distance(
    a: new SquareCoord(0, 0),
    b: new SquareCoord(5, 3),
    metric: SquareDistanceMetric.Manhattan);    /* = 8 */

var chebyshev = GridUtil.Distance(
    a: new SquareCoord(0, 0),
    b: new SquareCoord(5, 3),
    metric: SquareDistanceMetric.Chebyshev);    /* = 5 */

var euclid = GridUtil.Distance(
    a: new SquareCoord(0, 0),
    b: new SquareCoord(5, 3),
    metric: SquareDistanceMetric.Euclidean);    /* ~= 5.83 */

/* Bresenham line: returns every cell the stair-stepped line visits.
 * Use when your rules say diagonal walls block line of sight. */
Span<SquareCoord> line = stackalloc SquareCoord[64];
var written = GridUtil.DrawLine(
    from: new SquareCoord(0, 0),
    to: new SquareCoord(10, 5),
    buffer: line);

/* Supercover line: returns every cell the geometric line crosses, including
 * corner-clipped cells the Bresenham line skips. Use when your rules allow
 * sight through diagonal gaps between walls. */
written = GridUtil.DrawLineSupercover(
    from: new SquareCoord(0, 0),
    to: new SquareCoord(10, 5),
    buffer: line);

Lay out a hex-based strategy map

Problem. You are building a strategy or tactics game and six-way adjacency is starting to feel obviously right: every cell has the same distance to every neighbor, there are no diagonal/orthogonal asymmetries, and movement feels consistent in every direction. Civilization, Panzer General, Advance Wars on hex, Battle for Wesnoth – they all reach for hexes for the same reason. You want the same grid infrastructure without reimplementing axial coordinates.

Solution. The hex grid uses axial coordinates (q, r) internally and supports pointy-top and flat-top orientation via HexOrientation. Range, ring, and line queries are available directly on the grid; offset-coord conversions for tilemap exporters live on GridUtil.

/* Pointy-top hex grid covering a 16x16 axial region with 1-unit cell size.
 * Pointy-top means one hex vertex points straight up; flat-top means one
 * flat edge faces up. Commit to one and do not switch. */
var hexLayout = new HexGridLayout(
    size: 1f,
    orientation: HexOrientation.PointyTop);

var world = ScyllaHexGrid<TerrainType>.CreateBuilder()
    .WithSize(width: 16, height: 16)
    .WithLayout(hexLayout)
    .WithDefaultValue(TerrainType.Plains)
    .Build();

/* Six-way neighbor query; no adjacency argument because hex topology is
 * symmetric and the neighbor count never varies. */
Span<HexCoord> hexNeighbors = stackalloc HexCoord[6];
var count = world.GetNeighborsNonAlloc(
    coord: new HexCoord(8, 8),
    buffer: hexNeighbors);

/* Range query: every cell within radius 3 of the center. The canonical
 * "highlight movement range" call in a tactics game. */
Span<HexCoord> rangeBuffer = stackalloc HexCoord[64];
var inRange = world.GetRange(
    center: new HexCoord(8, 8),
    range: 3,
    buffer: rangeBuffer);

/* Ring query: only cells at exactly radius 3. Use for an ability that
 * affects a specific ring of cells (a shockwave at range 2, for example). */
var onRing = world.GetRing(
    center: new HexCoord(8, 8),
    radius: 3,
    buffer: rangeBuffer);

/* Convert from an exporter's offset coordinate system to internal axial.
 * Tilemap exporters typically write odd-r or even-r offset coords. */
var fromOddR = GridUtil.OddRToAxial(col: 4, row: 7);

/* Symmetric cube-coordinate distance. The same formula regardless of
 * topology orientation; distance(a, b) always equals distance(b, a). */
var hexDist = GridUtil.Distance(new HexCoord(0, 0), new HexCoord(5, 3));

Highlight movement range around a unit

Problem. It is a tactics game. The player selects a unit and you need to show every hex that unit can reach in a given number of steps, accounting for terrain, walls, and other obstructions. A raw range query shows the geometric disc; you need the reachable subset of it.

Solution. GridUtil.GetReachable performs a step-capped BFS from the unit’s hex. It fills a Dictionary<HexCoord, int> with every reachable hex mapped to the minimum step count needed to reach it, so you can tint cells by distance if your rules have per-step movement costs.

var distances = new Dictionary<HexCoord, int>();
var frontier  = new Queue<HexCoord>();

/* Highlight every hex the selected unit can reach in 3 steps. */
GridUtil.GetReachable(
    start:      selectedUnit.Hex,
    maxSteps:   selectedUnit.MoveRange,
    isBlocked:  coord => !world.TryGet(coord, out var tile) || tile.IsImpassable,
    distances:  distances,
    frontier:   frontier);

foreach (var (hex, steps) in distances)
{
    ShowMovementHighlight(hex, steps);
}

/* Clear the containers between selections so the next call starts fresh. */
distances.Clear();
frontier.Clear();

Reveal field of view around the player

Problem. The player moves into a new hex and you need to reveal every hex they can see: torch-lit rooms in a dungeon, radar range in a strategy game, sentry sight lines. You need something faster than “can the player see each hex on the map individually” and you want it to work with your existing wall data.

Solution. GridUtil.ComputeFieldOfView casts a hex line from the player to every hex within the given radius and collects those with an unobstructed path. For one-off sight checks between two specific hexes, use GridUtil.IsVisible instead.

/* Allocate the buffer once. Radius 5 can see at most 91 hexes. */
Span<HexCoord> visible = stackalloc HexCoord[128];

var count = GridUtil.ComputeFieldOfView(
    center:    player.Hex,
    radius:    player.SightRange,
    isBlocked: coord => world.TryGet(coord, out var tile) && tile.BlocksSight,
    visible:   visible);

for (var i = 0; i < count; i++)
{
    RevealHex(visible[i]);
}

/* Spot check: can the player see a specific enemy? */
if (GridUtil.IsVisible(player.Hex, enemy.Hex,
        coord => world.TryGet(coord, out var tile) && tile.BlocksSight))
{
    MarkEnemyVisible(enemy);
}

Build a triangle-topology puzzle map

Problem. You are building a puzzle game or a geodesic tiling where three-way adjacency is the natural shape: trichotomy puzzles, triangulated terrain patches, or decorative triangle fills on top of a hex map. Standard square and hex grids do not fit; you need a third topology.

Solution. The triangle grid uses an (a, b, c) coord and alternates between “up” and “down” triangles in each row. Three edge neighbors are the natural adjacency; up to twelve vertex neighbors are also addressable. The layout takes an edge length.

var triLayout = new TriGridLayout(edgeLength: 1f);

var triMap = ScyllaTriGrid<int>.CreateBuilder()
    .WithSize(width: 16, height: 16)
    .WithLayout(triLayout)
    .Build();

/* Three edge neighbors of a given triangle. "Up" and "down" triangles
 * alternate by (col + row) parity, so the neighbor set changes with each cell. */
Span<TriCoord> triNeighbors = stackalloc TriCoord[3];
var count = triMap.GetNeighborsNonAlloc(
    coord: new TriCoord(4, 5, 6),
    buffer: triNeighbors);

/* Triangle distance is the topology's natural step count. */
var triDist = GridUtil.Distance(new TriCoord(0, 0, 0), new TriCoord(3, 2, 1));

Grow an unbounded world without fixed bounds

Problem. Sometimes a world is mostly empty or has no fixed extent at all: an infinite Minecraft-style chunk grid, a procedurally extended dungeon that grows as the player explores, a save file recording only the cells the player has touched. A dense grid preallocates for the full extent and would waste memory on large or unbounded maps.

Solution. Sparse grids store cells in a hash map and grow on demand. The API mirrors the dense grid; the only differences are that TryRemove is exposed (dense grids have nothing to remove) and that bounded vs unbounded mode is selected by constructor overload.

/* Unbounded sparse grid: you can set cells at any coordinate,
 * including negative ones, with no preallocated extent. */
var sparse = new ScyllaSparseSquareGrid<TerrainPatch>(layout);

sparse.TrySet(new SquareCoord(-50, 200),   TerrainPatch.Lake);
sparse.TrySet(new SquareCoord(1000, 1000), TerrainPatch.Mountain);

/* Bounded sparse grid: out-of-range writes return false, same as a dense grid.
 * Useful when you want sparse memory but still need to enforce map edges. */
var bounded = new ScyllaSparseSquareGrid<TerrainPatch>(
    layout,
    minCol: 0, minRow: 0,
    maxCol: 99, maxRow: 99);

var inRange  = bounded.TrySet(new SquareCoord(50, 50),  TerrainPatch.Lake);   /* true  */
var outRange = bounded.TrySet(new SquareCoord(100, 50), TerrainPatch.Lake);   /* false */

/* TryRemove erases a sparse cell and reports the previous value.
 * Use it when a chunk unloads and you want to free its memory. */
if (sparse.TryRemove(new SquareCoord(-50, 200), out var removed))
{
    Recycle(removed);
}

Store walls and doors between cells

Problem. There is always a system that wants to attach data not to a tile but to the wall between two tiles, or the corner where four tiles meet: a door between rooms, a fence segment, a Wang-tile match-marker, a river section running between two plains hexes. Storing these as flags on each cell creates a synchronization problem: if cell A says “wall north” but its neighbor says “no wall south”, one of them is wrong.

Solution. An EdgeMap<TData> or CornerMap<TData> holds data keyed by edge or corner address. Each edge or corner coord is unique, so the same wall, door, or fence is represented by a single entry regardless of which neighboring cell you approach it from.

/* A wall is data associated with an edge, not a cell. One entry in the edge
 * map describes the boundary between the two cells that share that edge. */
var walls = new SquareEdgeMap<WallType>();

walls.Set(
    coord: new SquareEdgeCoord(col: 4, row: 4, direction: SquareEdgeDirection.North),
    value: WallType.Stone);

/* Enumerate the four edges of a cell to check whether any side is walled.
 * Typical use: pre-render pass that bakes wall meshes around each tile. */
Span<SquareEdgeCoord> cellEdges = stackalloc SquareEdgeCoord[4];
var edgeCount = SquareEdgeCoord.GetEdgesOfCellNonAlloc(
    cell: new SquareCoord(4, 4),
    buffer: cellEdges);

for (var i = 0; i < edgeCount; i++)
{
    if (walls.TryGet(cellEdges[i], out var wallType))
    {
        HandleWall(cellEdges[i], wallType);
    }
}

/* Corner data: a fountain placed at a four-cell intersection, addressable
 * from any of the four cells that share that corner. */
var landmarks = new SquareCornerMap<LandmarkID>();
landmarks.Set(new SquareCornerCoord(col: 5, row: 5, corner: 0), LandmarkID.Fountain);

Share a grid across worker threads

Problem. You are fanning pathfinding work out to a job thread, running a background fog-of-war refresh, or loading chunks in parallel. The grid is shared state and you need it to be thread-safe without rewriting your access patterns.

Solution. Every grid exposes AsSynchronized(object syncRoot = null) that returns a thread-safe wrapper backed by a lock. The wrapper implements the same IScyllaGrid<TCoord, TCell> interface and forwards every call. Build with Synchronized() if you know at construction that the grid will be shared.

/* Wrap an existing grid for thread-safe access. The wrapper implements the
 * same interface, so callers do not need to know it is synchronized. */
var synced = map.AsSynchronized();

/* Or build with synchronization from the start. The builder's Synchronized()
 * call wraps the result in SynchronizedScyllaSquareGrid automatically. */
var sharedMap = ScyllaSquareGrid<TileType>.CreateBuilder()
    .WithSize(64, 64)
    .WithLayout(layout)
    .Synchronized()   /* Returns IScyllaGrid<...> wrapped by SynchronizedScyllaSquareGrid */
    .Build();

Find connected rooms and reachable tiles

Problem. Anyone who has shipped a paint bucket, a connected-region detector, or a “which tiles are reachable from this start” check has implemented flood fill at least once. You want it to work on any topology – square, hex, or triangle – without reimplementing it three times.

Solution. GridUtil.FloodFill<TCoord> runs a breadth-first fill from a start coord, treating cells as passable according to a caller-supplied predicate. It works on any coord type because the neighbor enumeration is also caller-supplied. Reuse the result and frontier containers across calls to stay allocation-free per frame.

/* Find the connected floor region that contains the player's starting cell.
 * This is the same logic a "paint bucket" editor tool would use for a room. */
var startCoord    = new SquareCoord(8, 8);
var roomCells     = new HashSet<SquareCoord>();
var frontier      = new Queue<SquareCoord>();
var neighborBuffer = new SquareCoord[8];

/* Predicate: the cell belongs to the same room when it is a floor tile. */
bool IsFloor(SquareCoord c) => map.TryGet(c, out var t) && t == TileType.Floor;

/* Neighbor writer: fills the buffer with adjacent cells and returns how many.
 * Von Neumann here because this dungeon only allows 4-way movement. */
int GetNeighbors(SquareCoord c, SquareCoord[] buf) =>
    map.GetNeighborsNonAlloc(c, buf, SquareAdjacency.VonNeumann);

var roomSize = GridUtil.FloodFill(
    start:          startCoord,
    isPassable:     IsFloor,
    getNeighbors:   GetNeighbors,
    neighborBuffer: neighborBuffer,
    result:         roomCells,
    frontier:       frontier);

API Sketch

The public surface across the three topologies. See the API reference for full signatures, remarks, and exception contracts on every member.

namespace Scylla.Core.Structures
{
    /* ------------------------------------------------------------------ */
    /* INTERFACE                                                          */
    /* ------------------------------------------------------------------ */

    public interface IScyllaGrid<TCoord, TCell> : IScyllaCollection
        where TCoord : struct, IEquatable<TCoord>
    {
        int CellCount { get; }
        bool TryGet(TCoord coord, out TCell value);
        bool TrySet(TCoord coord, TCell value);
        bool Contains(TCoord coord);
    }

    /* ------------------------------------------------------------------ */
    /* SQUARE                                                             */
    /* ------------------------------------------------------------------ */

    public enum SquareAdjacency { VonNeumann, Moore }
    public enum SquareDistanceMetric { Manhattan, Chebyshev, Euclidean, Octile }
    public enum SquareEdgeDirection { /* North, East, South, West */ }

    public readonly struct SquareCoord : IEquatable<SquareCoord>
    {
        public static readonly SquareCoord Zero, Up, Down, Left, Right, UpLeft, UpRight, DownLeft, DownRight;
        public SquareCoord(int col, int row);
        public int ManhattanDistanceTo(SquareCoord other);
        public int ChebyshevDistanceTo(SquareCoord other);
        public float DistanceTo(SquareCoord other, SquareDistanceMetric metric);
        /* Operators: +, -, *, unary -, ==, != */
    }

    public readonly struct SquareGridLayout : IEquatable<SquareGridLayout>
    {
        public SquareGridLayout(float cellWidth, float cellHeight, float originX = 0f, float originY = 0f);
        public Vector2 GridToWorld(SquareCoord coord);
        public SquareCoord WorldToGrid(Vector2 worldPos);
    }

    public sealed class ScyllaSquareGrid<TCell> : IScyllaGrid<SquareCoord, TCell>
    {
        public ScyllaSquareGrid(int width, int height, SquareGridLayout layout);
        public TCell this[int col, int row] { get; set; }
        public TCell this[SquareCoord coord] { get; set; }
        public bool IsInBounds(int col, int row);
        public void Fill(TCell value);
        public int GetNeighborsNonAlloc(SquareCoord coord, Span<SquareCoord> buffer, SquareAdjacency adjacency = SquareAdjacency.VonNeumann);
        public Vector2 GridToWorld(SquareCoord coord);
        public SquareCoord WorldToGrid(Vector2 worldPos);
        public SynchronizedScyllaSquareGrid AsSynchronized(object syncRoot = null);
        public Enumerator GetEnumerator();
        public static Builder CreateBuilder();
    }

    public sealed class ScyllaSparseSquareGrid<TCell> : IScyllaGrid<SquareCoord, TCell>
    {
        public ScyllaSparseSquareGrid(SquareGridLayout layout);                                /* unbounded */
        public ScyllaSparseSquareGrid(SquareGridLayout layout, int minCol, int minRow,
                                      int maxCol, int maxRow);                                /* bounded   */
        public bool TryRemove(SquareCoord coord, out TCell value);
        public int GetNeighborsNonAlloc(SquareCoord coord, Span<SquareCoord> buffer, SquareAdjacency adjacency = SquareAdjacency.VonNeumann);
        public SynchronizedScyllaSparseSquareGrid AsSynchronized(object syncRoot = null);
        public static Builder CreateBuilder();
    }

    public readonly struct SquareEdgeCoord : IEquatable<SquareEdgeCoord>
    {
        public SquareEdgeCoord(int col, int row, SquareEdgeDirection direction);
        public static int GetCellsNonAlloc(SquareEdgeCoord edge, Span<SquareCoord> buffer);
        public static int GetCornersNonAlloc(SquareEdgeCoord edge, Span<SquareCornerCoord> buffer);
        public static int GetEdgesOfCellNonAlloc(SquareCoord cell, Span<SquareEdgeCoord> buffer);
    }

    public sealed class SquareEdgeMap<TData>   { /* TryGet/Set/Contains/TryRemove/Clear/Enumerator */ }
    public sealed class SquareCornerMap<TData> { /* TryGet/Set/Contains/TryRemove/Clear/Enumerator */ }

    /* ------------------------------------------------------------------ */
    /* HEX                                                                */
    /* ------------------------------------------------------------------ */

    public enum HexOrientation { PointyTop, FlatTop }
    public enum HexEdgeDirection { /* NE, E, SE, SW, W, NW */ }
    public enum HexCornerPosition { /* N, NE, SE, S, SW, NW (pointy-top) */ }

    public readonly struct HexCoord : IEquatable<HexCoord>
    {
        public static readonly HexCoord Zero, NE, E, SE, SW, W, NW;
        public HexCoord(int q, int r);
        public static HexCoord Direction(int index);
        public static HexCoord Diagonal(int index);
        public static int Distance(HexCoord a, HexCoord b);
        public static HexCoord RotateCW(HexCoord coord);
        public static HexCoord RotateCCW(HexCoord coord);
        public static HexCoord ReflectQ(HexCoord coord);
        public static HexCoord ReflectR(HexCoord coord);
        public static HexCoord ReflectS(HexCoord coord);
        public static HexCoord ReflectQ(HexCoord coord, HexCoord center);
        public static HexCoord ReflectR(HexCoord coord, HexCoord center);
        public static HexCoord ReflectS(HexCoord coord, HexCoord center);
        public int DistanceTo(HexCoord other);
        public HexCoord GetNeighbor(int direction);
        public HexCoord DiagonalNeighbor(int direction);
        /* Operators: +, -, ==, != */
    }

    public readonly struct FractionalHexCoord : IEquatable<FractionalHexCoord> { /* interpolation support */ }

    public readonly struct HexGridLayout : IEquatable<HexGridLayout>
    {
        public HexGridLayout(float size, HexOrientation orientation, float originX = 0f, float originY = 0f);
        public HexGridLayout(float sizeX, float sizeY, HexOrientation orientation, float originX = 0f, float originY = 0f);
        public float Size   { get; }   /* X-axis circumradius */
        public float SizeX  { get; }   /* alias for Size */
        public float SizeY  { get; }   /* independent Y-axis circumradius */
        public Vector2 GridToWorld(HexCoord coord);
        public HexCoord WorldToGrid(Vector2 worldPos);
        public Vector2 GetCornerOffset(int corner);
    }

    public sealed class ScyllaHexGrid<TCell> : IScyllaGrid<HexCoord, TCell>
    {
        public ScyllaHexGrid(int width, int height, HexGridLayout layout, int qMin = 0, int rMin = 0);
        public TCell this[HexCoord coord] { get; set; }
        public bool IsInBounds(HexCoord coord);
        public void Fill(TCell value);
        public int GetNeighborsNonAlloc(HexCoord coord, Span<HexCoord> buffer);
        public int GetRange(HexCoord center, int range, Span<HexCoord> buffer);
        public int GetRing(HexCoord center, int radius, Span<HexCoord> buffer);
        public int DrawLine(HexCoord from, HexCoord to, Span<HexCoord> buffer);
        public Vector2 GridToWorld(HexCoord coord);
        public HexCoord WorldToGrid(Vector2 worldPos);
        public SynchronizedScyllaHexGrid AsSynchronized(object syncRoot = null);
        public Enumerator GetEnumerator();
        public static Builder CreateBuilder();
    }

    public sealed class ScyllaSparseHexGrid<TCell> : IScyllaGrid<HexCoord, TCell>
    {
        public int QMin { get; }    /* throws InvalidOperationException if unbounded */
        public int RMin { get; }    /* throws InvalidOperationException if unbounded */
        public int GetRange(HexCoord center, int range, Span<HexCoord> buffer);
        public int GetRing(HexCoord center, int radius, Span<HexCoord> buffer);
        public int GetSpiral(HexCoord center, int radius, Span<HexCoord> buffer);
        public int DrawLine(HexCoord from, HexCoord to, Span<HexCoord> buffer);
        /* mirrors dense + TryRemove + bounded ctor; range/ring/spiral/line filter to occupied cells */
    }

    public sealed class HexEdgeMap<TData>   { /* TryGet/Set/Contains/TryRemove/Clear/Enumerator */ }
    public sealed class HexCornerMap<TData> { /* TryGet/Set/Contains/TryRemove/Clear/Enumerator */ }

    /* ------------------------------------------------------------------ */
    /* TRIANGLE                                                           */
    /* ------------------------------------------------------------------ */

    public enum TriEdgeDirection { /* three edges per triangle */ }

    public readonly struct TriCoord : IEquatable<TriCoord>
    {
        public TriCoord(int a, int b, int c);
        public static int Distance(TriCoord a, TriCoord b);
        public static int GetEdgeNeighbors(TriCoord coord, Span<TriCoord> buffer);
        public int DistanceTo(TriCoord other);
        /* Operators: +, -, *, unary -, ==, != */
    }

    public readonly struct TriGridLayout : IEquatable<TriGridLayout>
    {
        public TriGridLayout(float edgeLength, float originX = 0f, float originY = 0f);
        public Vector2 GridToWorld(TriCoord coord);
        public TriCoord WorldToGrid(Vector2 worldPos);
    }

    public sealed class ScyllaTriGrid<TCell> : IScyllaGrid<TriCoord, TCell>
    {
        public ScyllaTriGrid(int width, int height, TriGridLayout layout);
        public TCell this[TriCoord coord] { get; set; }
        public bool IsInBounds(TriCoord coord);
        public void Fill(TCell value);
        public int GetNeighborsNonAlloc(TriCoord coord, Span<TriCoord> buffer);
        public Vector2 GridToWorld(TriCoord coord);
        public TriCoord WorldToGrid(Vector2 worldPos);
        public SynchronizedScyllaTriGrid AsSynchronized(object syncRoot = null);
        public Enumerator GetEnumerator();
        public static Builder CreateBuilder();
    }

    public sealed class ScyllaSparseTriGrid<TCell> : IScyllaGrid<TriCoord, TCell> { /* mirrors dense + TryRemove */ }

    public sealed class TriEdgeMap<TData>   { /* TryGet/Set/Contains/TryRemove/Clear/Enumerator */ }
    public sealed class TriCornerMap<TData> { /* TryGet/Set/Contains/TryRemove/Clear/Enumerator */ }

    /* ------------------------------------------------------------------ */
    /* GRID UTIL                                                          */
    /* ------------------------------------------------------------------ */

    public static class GridUtil
    {
        /* Square */
        public static float Distance(SquareCoord a, SquareCoord b, SquareDistanceMetric metric);
        public static int DrawLine(SquareCoord from, SquareCoord to, Span<SquareCoord> buffer);
        public static int DrawLineSupercover(SquareCoord from, SquareCoord to, Span<SquareCoord> buffer);

        /* Hex */
        public static int Distance(HexCoord a, HexCoord b);
        public static int DrawLine(HexCoord from, HexCoord to, Span<HexCoord> buffer);
        public static int GetRange(HexCoord center, int range, Span<HexCoord> buffer);
        public static int GetRing(HexCoord center, int radius, Span<HexCoord> buffer);
        public static int GetSpiral(HexCoord center, int radius, Span<HexCoord> buffer);
        public static int GetRangeIntersection(HexCoord a, int rangeA, HexCoord b, int rangeB, Span<HexCoord> buffer);
        public static HexCoord RotateCW(HexCoord coord, HexCoord center);
        public static HexCoord RotateCCW(HexCoord coord, HexCoord center);
        public static int SpiralRingStart(int radius);
        public static int SpiralIndexToRadius(int index);
        public static HexCoord SpiralIndexToCoord(HexCoord center, int index);
        public static int CoordToSpiralIndex(HexCoord center, HexCoord coord);
        public static int GetReachable(HexCoord start, int maxSteps, Func<HexCoord, bool> isBlocked,
                                       Dictionary<HexCoord, int> distances, Queue<HexCoord> frontier);
        public static bool IsVisible(HexCoord from, HexCoord to, Func<HexCoord, bool> isBlocked);
        public static int ComputeFieldOfView(HexCoord center, int radius, Func<HexCoord, bool> isBlocked,
                                             Span<HexCoord> visible);
        public static int GetHexagonalRegion(int radius, Span<HexCoord> buffer);
        public static int GetRectangularRegion(int radius, HexLayoutMode mode, HexOrientation orientation,
                                               Span<HexCoord> buffer);
        public static int GetTriangularRegion(int size, bool pointingUp, Span<HexCoord> buffer);
        public static int GetRhombusRegion(int width, int height, Span<HexCoord> buffer);

        /* Offset coordinate conversions for hex (odd/even rows or columns, doubled width/height) */
        public static HexCoord OddRToAxial(int col, int row);
        public static void AxialToOddR(HexCoord coord, out int col, out int row);
        public static HexCoord EvenRToAxial(int col, int row);
        public static void AxialToEvenR(HexCoord coord, out int col, out int row);
        public static HexCoord OddQToAxial(int col, int row);
        public static void AxialToOddQ(HexCoord coord, out int col, out int row);
        public static HexCoord EvenQToAxial(int col, int row);
        public static void AxialToEvenQ(HexCoord coord, out int col, out int row);
        public static HexCoord DoubledWidthToAxial(int col, int row);
        public static void AxialToDoubledWidth(HexCoord coord, out int col, out int row);
        public static HexCoord DoubledHeightToAxial(int col, int row);
        public static void AxialToDoubledHeight(HexCoord coord, out int col, out int row);
        public static int DoubledWidthDistance(int aCol, int aRow, int bCol, int bRow);
        public static int DoubledHeightDistance(int aCol, int aRow, int bCol, int bRow);

        /* Triangle */
        public static int Distance(TriCoord a, TriCoord b);

        /* Topology-agnostic */
        public delegate int NeighborWriter<TCoord>(TCoord coord, TCoord[] buffer);
        public static int FloodFill<TCoord>(
            TCoord start,
            Func<TCoord, bool> isPassable,
            NeighborWriter<TCoord> getNeighbors,
            TCoord[] neighborBuffer,
            HashSet<TCoord> result,
            Queue<TCoord> frontier)
            where TCoord : struct, IEquatable<TCoord>;
    }
}

See the API reference for full signatures, remarks, and exception contracts on every member.

Settings reference

Square grid builder

SetterDefaultRequiredEffect
WithSize(none)YesCell extent: (width, height) measured in cells, not world units.
WithLayout(none)YesWorld-space placement: cell size and origin via SquareGridLayout.
WithDefaultValuedefault(TCell)NoInitial value for every cell. Useful when default(TCell) is not a meaningful starting state.
SynchronizedunsynchronizedNoWrap the resulting grid in SynchronizedScyllaSquareGrid. Optional syncRoot lets callers share the lock.

Hex grid builder

Same shape as the square builder, with WithLayout taking a HexGridLayout and an additional qMin/rMin available via the positional constructor for shifting the addressing origin.

Triangle grid builder

Same shape as the square builder, with WithLayout taking a TriGridLayout.

Layouts

LayoutConstructorPurpose
SquareGridLayout(cellWidth, cellHeight, originX = 0, originY = 0)Independent X/Y cell sizes for non-square tile assets. Origin offsets the world position of cell (0, 0).
HexGridLayout(size, orientation, originX = 0, originY = 0) or (sizeX, sizeY, orientation, originX = 0, originY = 0)size is the distance from hex center to corner (not flat-to-flat). sizeX and sizeY may differ for elliptical hexes. orientation is PointyTop or FlatTop and determines world-space rotation and neighbor axes.
TriGridLayout(edgeLength, originX = 0, originY = 0)edgeLength is the length of one triangle edge in world units. Up and down triangles alternate by (col + row) parity.

Best Practices

  • Pick dense or sparse on populated-fraction, not on intuition. If less than roughly 25% of the cells will ever be written, sparse storage saves memory and warms the hot path. Above that, dense storage is faster on reads and simpler to reason about.
  • Allocate neighbor and range buffers once. stackalloc Span<TCoord> is allocation-free, but only inside the calling stack frame. For buffers that escape the method, allocate a TCoord[] field on a long-lived object and reuse it every frame.
  • Treat layouts as the single source of world-space truth. GridToWorld and WorldToGrid handle origin offsets and orientation automatically; hand-rolled coord.Col * tileSize math always drifts as the project grows.
  • Pick the line-of-sight rule before authoring data. Bresenham (DrawLine) skips corner-clipped cells; supercover (DrawLineSupercover) includes them. The choice changes which doorways the player can shoot through. Decide early.
  • Commit to hex orientation at the start of the project. Pointy-top and flat-top are not interchangeable. The choice determines neighbor directions, world-space rotation, and which corners face up. Switching mid-project means re-authoring art.
  • Store walls and doors as edge data, not cell flags. A SquareEdgeMap<WallType> describes the boundary between two cells with a single entry, which is the natural representation for two-way passability. A per-cell bitmask invariably drifts when one of the two cells is edited and the other is not.
  • Reach for GetNeighborsNonAlloc, not for repeated arithmetic. Even for square grids where coord + SquareCoord.Right is obvious, the non-alloc helper handles bounds checking and adjacency selection in one place. Hand-rolled iteration is where off-by-one and out-of-bounds bugs live.
  • Use IScyllaGrid<TCoord, TCell> for code that should work on both dense and sparse storage. Algorithms that depend only on cell access, neighbor counts, and adjacency belong on the interface. Concrete dependencies belong only in the level loader and the renderer.
  • Pair the grid with ScyllaGridGraphAdapter for pathfinding. The Graph module wraps any IScyllaGrid as a node set with weighted edges; A*, BFS (breadth-first search), and Dijkstra then operate uniformly across topologies.
  • Convert offset coordinates to axial at the boundary. Tilemap exporters and CAD-style editors usually export hex maps in offset coordinates. Use GridUtil.OddRToAxial (or the matching variant) on import and convert back only when serializing back out. Internal code should never see offset coordinates.
  • Hold a single SyncRoot across compound operations on synchronized grids. The synchronized wrapper protects each call but not sequences of calls. For read-modify-write or multi-cell transactions, lock (sharedMap.SyncRoot) { ... } is the only safe pattern.
  • Reuse the result and frontier containers across FloodFill invocations. FloodFill clears both at the start of each call, so the same HashSet<TCoord> and Queue<TCoord> can be reused every frame.

Pitfalls

Updated on July 9, 2026