Grids

Square and hex grid coordinates, movement ranges, line of sight and fog of war.

Commands

Import blitz.grids As G gives your program these, with G. in front. Each name leads to its part of the reference.

Functions

• CreateGrid:Grid(kind:Int, width:Int, height:Int, size:Double = 1D)
• CreateVisibility:Visibility(grid:Grid)
• CellVisibility:Int(view:Visibility, x:Int, y:Int)
• CellPosition(grid:Grid, x:Int, y:Int, output:Point)
• CellAt:Int(grid:Grid, worldX:Double, worldZ:Double, output:Cell)
• CellDistance:Int(grid:Grid, x1:Int, y1:Int, x2:Int, y2:Int)
• Neighbours:CellSet(grid:Grid, x:Int, y:Int)
• ReachableCells:CellSet(grid:Grid, x:Int, y:Int, steps:Int, blockers:Blockers)
• LineOfSight:Int(grid:Grid, x1:Int, y1:Int, x2:Int, y2:Int, blockers:Blockers)
• UpdateVisibility(view:Visibility, x:Int, y:Int, radius:Int, blockers:Blockers)

Types

• Cell
  Fields x:Int, y:Int
• Point
  Fields x:Double, z:Double
• Grid
• CellSet
  Methods Count:Int(), CopyCell(index:Int, output:Cell)
• Visibility

Interfaces

• Blockers
  Methods you write Blocked:Int(x:Int, y:Int)

Enums

• GridKind
  Values Square4, Square8, HexPointy, HexFlat
• VisibilityState
  Values Unseen, Explored, Visible

Guide

Grids looks after the board in a board game or a tactics game, made of squares or hexes. It finds the cell under the mouse and where to draw each cell, counts the steps between cells, finds every cell a unit can walk to in so many steps, and works out what a unit can see past walls, with a fog of war that remembers where it has been. Your game draws the board and says where the walls are.

Try it

Open tactics.bb and run it. Click a cell with a dot to walk the scout there. Walk through the gap in the rocks, and watch what the scout can see change.

; A scout on a hex board. Click a cell with a dot to walk there, up to three
; steps. Rocks block both walking and sight. Escape quits.
Dialect "modern"
Import blitz.grids As G

Dim rock:Int(9, 8)  ; True where there's a rock.
Dim reach:Int(9, 8) ; True where the scout can walk to.

; The module asks the game which cells are blocked.
Type Rocks Implements G.Blockers
    Method Blocked:Int(x:Int, y:Int)
        Return rock(x, y)
    End Method
End Type

Graphics 640, 400, 0, 2
SetBuffer BackBuffer()
ClsColor 18, 52, 79

; Ten cells across and nine down, with corners 24 pixels from each centre.
Local board:G.Grid = G.CreateGrid(G.GridKind.HexPointy, 10, 9, 24D)
Local rocks:Rocks = New Rocks
Local sight:G.Visibility = G.CreateVisibility(board)
Local cell:G.Cell = New G.Cell
Local point:G.Point = New G.Point
Local scoutX:Int = 1
Local scoutY:Int = 4
Local changed:Int = True
Local x:Int
Local y:Int
Local index:Int
For index = 1 To 9 ; Nine rocks, from the Data at the end.
    Read x, y
    rock(x, y) = True
Next

While Not KeyDown(1)
    ; Cell 0, 0 is drawn at 40, 40, so CellAt needs the mouse relative to that.
    If MouseHit(1)
        If G.CellAt(board, MouseX() - 40, MouseY() - 40, cell)
            If reach(cell.x, cell.y)
                scoutX = cell.x
                scoutY = cell.y
                changed = True
            EndIf
        EndIf
    EndIf

    If changed
        ; Where can the scout walk in three steps, and what can it see?
        Local range:G.CellSet = G.ReachableCells(board, scoutX, scoutY, 3, rocks)
        G.UpdateVisibility sight, scoutX, scoutY, 5, rocks
        Dim reach:Int(9, 8) ; Dim it again to clear it.
        For index = 0 To range.Count() - 1
            range.CopyCell(index, cell)
            reach(cell.x, cell.y) = True
        Next
        Delete range
        changed = False
    EndIf

    Cls
    For y = 0 To 8
        For x = 0 To 9
            Color 27, 66, 98
            If G.CellVisibility(sight, x, y) = G.VisibilityState.Explored Then Color 46, 96, 134
            If G.CellVisibility(sight, x, y) = G.VisibilityState.Visible Then Color 90, 150, 190
            If rock(x, y) Then Color 140, 125, 105
            G.CellPosition board, x, y, point ; Where the cell's centre is.
            Oval 21 + point.x, 21 + point.z, 38, 38, True
            Color 255, 220, 0
            If reach(x, y) Then Oval 36 + point.x, 36 + point.z, 8, 8, True
        Next
    Next
    G.CellPosition board, scoutX, scoutY, point
    Color 255, 255, 255
    Oval 30 + point.x, 30 + point.z, 20, 20, True
    Text 16, 376, "Bright: in sight now.  Dim: seen before.  Dark: not seen yet."
    Flip
Wend
Delete sight ; Delete a grid's visibility before the grid.
Delete board
Delete rocks
Delete cell
Delete point
End

Data 5, 0, 5, 1, 4, 2, 4, 3, 3, 5, 2, 6, 2, 7, 1, 8, 7, 4

The module never looks at the rocks itself. Whenever it needs to know whether a cell is blocked, it asks the Blocked method of Rocks, so your game can keep its map however it likes. The program only asks for the scout's range and sight when the scout moves, not every frame, and keeps the answers to draw.

How do I...

Use squares instead of hexes?

Choose Square4, where units move across and up and down, or Square8, where they can move diagonally too. The size is then the width of a square.

Local board:G.Grid = G.CreateGrid(G.GridKind.Square8, 12, 9, 44D)

A diagonal step is only allowed when neither of the cells beside it is blocked, so units never cut across the corner of a rock.

Find the cell under the mouse?

CellAt turns a position into a cell. Positions are measured from the centre of cell 0, 0, so take away wherever you draw that cell. It returns False when the position is off the board.

If G.CellAt(board, MouseX() - 40, MouseY() - 40, cell)
    Text 10, 10, "Cell " + cell.x + ", " + cell.y
EndIf

Find where to draw a cell?

CellPosition gives the centre of a cell. It calls the two directions x and z, because in 3D the board lies flat on the ground. In 2D, use z for down the screen.

G.CellPosition board, 3, 2, point
Oval 40 + point.x - 10, 40 + point.z - 10, 20, 20, True ; In 2D.
PositionEntity counter, point.x, 0, point.z            ; In 3D.

Check whether one unit can see another?

If G.LineOfSight(board, scoutX, scoutY, enemyX, enemyY, rocks)
    ; Draw the enemy.
EndIf

Sight works both ways: if the scout can see the enemy, the enemy can see the scout. Pass Null instead of rocks for a board with nothing in the way.

Give each player a fog of war?

Make a Visibility for each player, and update each one from its own player. Updating one again replaces what it can see now, but it still remembers the cells it has seen before.

Local redFog:G.Visibility = G.CreateVisibility(board)
Local blueFog:G.Visibility = G.CreateVisibility(board)
G.UpdateVisibility redFog, redX, redY, 5, rocks
G.UpdateVisibility blueFog, blueX, blueY, 5, rocks
If G.CellVisibility(redFog, blueX, blueY) = G.VisibilityState.Visible
    ; Red can see blue, so draw blue on red's screen.
EndIf

Count the steps between two cells?

Local steps:Int = G.CellDistance(board, scoutX, scoutY, 7, 4)

This counts the steps across an empty board, without going round any rocks.

Find the cells next to a cell?

Neighbours gives you a set of cells, which is yours to delete.

Local around:G.CellSet = G.Neighbours(board, 3, 3)
Local index:Int
For index = 0 To around.Count() - 1
    around.CopyCell(index, cell)
    ; Do something with cell.x and cell.y.
Next
Delete around

Cells off the edge of the board are left out.

Blip's tip

A hex board isn't a rectangle. With points at the top, each row starts half a cell further right than the row above (with flat tops, each column starts half a cell lower), so the board leans over, as in the program above. For a board of another shape, make it bigger, block the cells you don't want, and don't draw them.

Good to know

• Cells are numbered from 0, with x across and y down the board.
• Ranges are in steps, not distance. A sight range of 5 makes a hexagon on a hex board and a diamond or a square on a square one, not a circle.
• Sight is careful. A rock that touches the straight line between two cells' centres, even only at a corner, blocks the view along it.
• Answers don't change by themselves. A set of cells stays as it was when you asked for it, so ask again after a door opens. Change your map between calls, never while Blocked is being asked.
• Delete what you're given, and delete each Visibility before its grid: deleting the grid first stops the program.

More examples

Three more complete programs come with the module:

• hex_board.bb has two players on a hex board, each with their own fog of war. Click to move, Tab changes player, D opens and closes a door, and Space starts again with hexes that have flat tops instead of points, or back again.
• quick_start.bb finds the cell at a position, lists the cells within two steps, and shows that cells which have been seen are remembered. It prints what it finds.
• square_board.bb is a square tactics board. Click to move up to three steps, and Space opens and closes a door. The enemy behind the door appears only when you can see it.

The reference below has every function and rule.

Reference

Needs

No other modules

Examples

hex_board.bb, quick_start.bb, square_board.bb

0.1.0 unpublished preview. Square4/Square8 and pointy/flat axial hex boards, unit-cost reachable cells, symmetric conservative sight and remembered fog. Requires Extended object-lifecycle-v1 (runtime 1114 / module ABI 5 or newer). No package dependency, renderer, global game loop, clock or import side effect.

Blitz3D+ comes with this module, so any Extended program can Import blitz.grids. Open an example and run it.

Dialect "modern"
Import blitz.grids
Local board:Grids.Grid = Grids.CreateGrid(Grids.GridKind.HexPointy, 12, 10)
Local cells:Grids.CellSet = Grids.ReachableCells(board, 3, 3, 2, Null)
Local cell:Grids.Cell = New Grids.Cell
Local index:Int
For index = 0 To cells.Count() - 1
    cells.CopyCell(index, cell)
    Print cell.x + "," + cell.y
Next
Delete cells
Delete cell
Delete board
End

Coordinates and API

World coordinates use the XZ ground plane, with cell (0,0) at the origin. Square size is side length; hex size is centre-to-corner radius. Hex public x/y mean axial q/r, not staggered offset rows. Bounds are the parallelogram 0 <= q < width, 0 <= r < height. Both orientations share topology; only the world conversion changes. Add/subtract your scene's origin in game code.

Commands without a documented return value are used as statements; their compiler-displayed default Int result has no semantic meaning. Read is a reserved language keyword, so the proposed result method is named CopyCell. The public world values/size use Double rather than the plan's Float notation to avoid discarding precision before flooring/rounding. Dimensions and scale bounds prevent overflow and unreasonable unbounded allocations; they are validated before constructing resources. Null Interface defaults are unsupported by this compiler, so the nullable blockers argument is explicitly supplied.

There is no recoverable load or I/O operation and hence no redundant LastError. Invalid dimensions, kind, size, negative radius/steps, out-of-bounds cells, non-finite world values, Null/deleted resources and invalid callback actions are contextual RuntimeErrors. An outside pick, empty neighbour set or blocked sight is a normal result. Example error: Grids.ReachableCells(board,0,0,-1,Null).

Deterministic geometry and ordering

Square picking uses FloorD(world/size + 0.5D), including negative positions. Halfway boundaries belong to the positive coordinate: -0.5 picks zero, +0.5 picks one at size one. Picking does not clamp to board edges.

Hex picking converts world coordinates to fractional cube (q,r,s=-q-r). Each scalar rounds upward at halves, with an explicit 1e-10-cell tie band to absorb inverse-matrix rounding at ideal edges/vertices. Repair the component with largest rounding error so the sum is zero; errors within 2e-10 tie in q, then r, then s order. For example (q=.5,r=0) selects (0,0), while (-.5,0) selects (-1,0) and is outside this finite board. The tiny tie band is part of this preview's picking contract: points inside it are treated as boundary points. It is far below a rendered pixel at ordinary scales and above Double conversion noise within the supported coordinate bounds. LOS still uses exact integer intersection tests and no directional epsilon.

Neighbour order is fixed, with out-of-bounds entries dropped:

• Square: E (1,0), S (0,1), W (-1,0), N (0,-1); Square8 then adds SE (1,1), SW (-1,1), NW (-1,-1), NE (1,-1).
• Hex: (1,0), (0,1), (-1,1), (-1,0), (0,-1), (1,-1).

Reachability uses a bounded unit-cost BFS, then a stable counting pass: shortest distance, y, x order, not discovery order. A diagonal Square8 move requires both orthogonal side cells to be open; a single blocking side forbids slipping past its corner. The origin may be opaque and is still included. Coordinate snapshots are unaffected by later map changes or deletion of their grid.

Sight traces the closed centre-to-centre segment. Every cell touched by the segment, even at a single corner or along a shared edge, is considered. Either endpoint is visible regardless of its own opacity; opaque cells block farther points. Thus an opaque origin sees itself and its neighbours, and LOS is symmetric for a fixed map: A sees B exactly when B sees A. Outside-board cells are opaque. This intentionally conservative policy can hide a diagonal target when a side cell only touches the segment at a corner.

Square sight compares integer boundary crossing times. Hex sight samples cube coordinates and tests each sample's one-ring using exact rational segment/hex clipping. This covers shared edges/vertices without choosing a privileged side. All integer geometry stays within Long bounds. The source explains coverage and termination.

Fog, ownership and callbacks

Local fog:Grids.Visibility = Grids.CreateVisibility(board)
Grids.UpdateVisibility fog, playerX, playerY, 8, walls
If Grids.CellVisibility(fog, enemyX, enemyY) = Grids.VisibilityState.Visible
    ; Draw the enemy here. Do not draw it merely because its cell is Explored.
EndIf
Delete fog ; Do this before Delete board.

The fragment assumes existing game coordinates, board and walls; complete standalone examples are below. The module never renders, polls input, advances time, saves, or changes game-owned objects. Fog updates consume no delta/time. Changing doors/terrain between queries takes effect on the next query/update. For multiple players, allocate one view each. Updating one view twice replaces its observer; it does not union observers. A game may explicitly OR separate Visible states when combining allies. No hidden global union is performed.

Delete is explicit; leaving scope/assigning Null is not cleanup. Typed Null and already deleted aliases are harmless to Delete. Do not Delete Each to clean up an instance: it would also delete unrelated game-owned objects.

During one query/update each in-bounds cell's opacity is sampled at most once, and that answer is cached. Blockers must provide a stable map until the outer operation returns: no mutation of map answers, deletion of the blocker itself, or deletion of the active Grid/Visibility in its callback. No arbitrary rollback or callback-error recovery is promised: RuntimeError terminates the program. Destructors cannot cancel/veto deletion, so a lifetime violation is fatal.

A grid rejects nested ReachableCells/LineOfSight/UpdateVisibility/CreateVisibility while a blocker query is active. A view rejects reads/updates while it is being updated. Pure immutable topology reads (CellAt, CellPosition, CellDistance, Neighbours) are allowed in callbacks; the caller still owns any returned result. Queries on a different grid are independent. Change game state after the outer call returns. There are no Stop/Cancel/Save/Commit aliases to conflate with Delete.

Examples and performance

• examples/quick_start.bb: cell conversion, ordered range, exploration memory and result lifetime. Finite without input.
• examples/square_board.bb: click a lit outlined tile to move; Space opens or closes the door; Escape exits. The closed door conceals the red enemy. The --verify sequence moves, opens, closes and asserts actual draw suppression.
• examples/hex_board.bb: two players with separate fog; click to move, Tab to switch player, D to operate the door, Space to switch pointy/flat (resets board and exploration), Escape to exit. --verify performs those actions and checks hidden-unit rendering. All polygon tiles/units are generated in source.

For N board cells, a standalone range is O(N+V+E) time/storage, with E <= 8V; counting-sort distance is at most V-1. Standalone LOS uses O(N) temporary cached opacity initialisation plus O(distance) traversal. Visibility retains and reuses its O(N) buffers: an update is O(N + radius³) simple LOS, with each blocker cell sampled at most once across its rays. Query when selection or map state changes; do not recompute the whole board every draw. For much larger sight radii, shadowcasting would need a reviewed implementation matching these exact corner and endpoint rules, not a silent change of visible sets.

Explicitly deferred: weighted movement/routes and the optional blitz.grids.pathfinding adapter (a later integration in the original plan), weighted reachable nodes there, batch observers, fog persistence helpers, shadowcasting and worker adapters. A game can save explored stable coordinates in its own JSON.