Yog.FSharp
Getting Started Examples API Reference GitHub

Grid Module

Namespace: Yog.Builder
Assembly: Yog.FSharp.dll

A builder for creating graphs from 2D grids.

This module provides convenient ways to convert 2D grids (like heightmaps, mazes, or game boards) into graphs for pathfinding and traversal algorithms.

Key Concepts

  • Row-Major Ordering: Node ID = row × cols + col
  • Topology: Movement patterns (rook/bishop/queen/knight)
  • Predicate: Function that determines if movement is allowed

Movement Topologies

The module provides 4 chess-inspired movement patterns:

Rook (4-way cardinal):

. ↑ . ← · → . ↓ .

Bishop (4-way diagonal):

↖ . ↗ . · . ↙ . ↘

Queen (8-way):

↖ ↑ ↗ ← · → ↙ ↓ ↘

Knight (L-shaped):

. ♞ . ♞ . ♞ . . . ♞ . . · . . ♞ . . . ♞ . ♞ . ♞ .

Example Usage

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 

open Yog.Builder

// A simple heightmap where you can only climb up by 1
let heightmap = array2D [[1; 2; 3]
                         [4; 5; 6]
                         [7; 8; 9]]

// Build a graph with rook movement, can move if height diff <= 1
let grid = Grid.fromArray2D heightmap Directed Grid.rook
    (fun fromHeight toHeight -> toHeight - fromHeight <= 1)

// Convert to graph and use with algorithms
let graph = Grid.toGraph grid
let start = Grid.coordToId 0 0 grid.Cols  // Top-left
let goal = Grid.coordToId 2 2 grid.Cols   // Bottom-right

// Use with pathfinding
Yog.Pathfinding.AStar.aStarInt
    (fun from to' -> Grid.manhattanDistance from to' grid.Cols)
    start goal graph

Use Cases

  • Game pathfinding: Character movement on tile-based maps
  • Maze solving: Finding paths through grid-based mazes
  • Heightmap navigation: Terrain traversal with elevation constraints
  • Puzzle solving: Grid-based puzzles like Sokoban, sliding puzzles
namespace Yog
namespace Yog.Builder
val heightmap: int array2d
val array2D: rows: #('T seq) seq -> 'T array2d
val grid: ((int -> int -> bool) -> Grid<int,int>)
Multiple items
module Grid from Yog.Builder
<summary> A builder for creating graphs from 2D grids. This module provides convenient ways to convert 2D grids (like heightmaps, mazes, or game boards) into graphs for pathfinding and traversal algorithms. ## Key Concepts - **Row-Major Ordering**: Node ID = row × cols + col - **Topology**: Movement patterns (rook/bishop/queen/knight) - **Predicate**: Function that determines if movement is allowed ## Movement Topologies The module provides 4 chess-inspired movement patterns: **Rook (4-way cardinal):** . ↑ . ← · → . ↓ . **Bishop (4-way diagonal):** ↖ . ↗ . · . ↙ . ↘ **Queen (8-way):** ↖ ↑ ↗ ← · → ↙ ↓ ↘ **Knight (L-shaped):** . ♞ . ♞ . ♞ . . . ♞ . . · . . ♞ . . . ♞ . ♞ . ♞ . ## Example Usage open Yog.Builder // A simple heightmap where you can only climb up by 1 let heightmap = array2D [[1; 2; 3] [4; 5; 6] [7; 8; 9]] // Build a graph with rook movement, can move if height diff &lt;= 1 let grid = Grid.fromArray2D heightmap Directed Grid.rook (fun fromHeight toHeight -&gt; toHeight - fromHeight &lt;= 1) // Convert to graph and use with algorithms let graph = Grid.toGraph grid let start = Grid.coordToId 0 0 grid.Cols // Top-left let goal = Grid.coordToId 2 2 grid.Cols // Bottom-right // Use with pathfinding Yog.Pathfinding.AStar.aStarInt (fun from to' -&gt; Grid.manhattanDistance from to' grid.Cols) start goal graph ## Use Cases - **Game pathfinding**: Character movement on tile-based maps - **Maze solving**: Finding paths through grid-based mazes - **Heightmap navigation**: Terrain traversal with elevation constraints - **Puzzle solving**: Grid-based puzzles like Sokoban, sliding puzzles </summary>

--------------------
type Grid<'CellData,'EdgeData> = { Graph: Graph<'CellData,'EdgeData> Rows: int Cols: int }
<summary> A grid builder that wraps a graph and maintains grid dimensions. The grid uses row-major ordering: node_id = row × cols + col ## Type Parameters - 'CellData: The data stored in each grid cell (becomes node data) - 'EdgeData: The data stored on edges (typically int for weights) </summary>
val fromArray2D: gridData: 'n array2d -> kind: Yog.Model.GraphType -> topology: (int32 * int32) seq -> canMove: ('n -> 'n -> bool) -> Grid<'n,int>
<summary> Builds a grid-graph from a 2D array and a custom movement topology. Each cell becomes a node, and edges are added between cells based on the topology and the canMove predicate. ## Parameters - gridData: 2D array of cell data - kind: Directed or Undirected - topology: List of (row_delta, col_delta) offsets (e.g., rook, queen) - canMove: Predicate function (fromData -&gt; toData -&gt; bool) ## Returns Grid with the underlying graph and dimensions ## Time Complexity O(rows × cols × |topology|) ## Example // 8-way movement on a maze let maze = array2D [[".";"#";"."] [".";".";"."] ["#";".";"."] ] let grid = fromArray2D maze Undirected queen (avoiding "#") </summary>
val rook: (int * int) list
<summary> Cardinal (4-way) movement: up, down, left, right. Named after the rook in chess, which moves along ranks and files. . ↑ . ← · → . ↓ . </summary>
val fromHeight: int
val toHeight: int
val toGraph: grid: Grid<'a,'b> -> Yog.Model.Graph<'a,'b>
<summary> Converts the grid to a standard Graph. The resulting graph can be used with all yog algorithms. ## Example let graph = toGraph grid // Now use with pathfinding, traversal, etc. </summary>
val coordToId: row: int32 -> col: int32 -> cols: int -> int32
<summary> Converts grid coordinates (row, col) to a node ID. Uses row-major ordering: id = row × cols + col ## Example coordToId 0 0 3 // =&gt; 0 coordToId 1 2 3 // =&gt; 5 coordToId 2 1 3 // =&gt; 7 </summary>
namespace Yog.Pathfinding
module AStar from Yog.Pathfinding
<summary> A* (A-Star) search algorithm for optimal pathfinding with heuristic guidance. A* is an informed search algorithm that finds the shortest path from a start node to a goal node using a heuristic function to guide exploration. It combines the completeness of Dijkstra's algorithm with the efficiency of greedy best-first search. ## Algorithm | Algorithm | Function | Complexity | Best For | |-----------|----------|------------|----------| | A* Search | aStar | O((V + E) log V) | Pathfinding with good heuristics | | Implicit A* | implicitAStar | O((V + E) log V) | Large/infinite graphs generated on-demand | ## Key Concepts - **Evaluation Function**: f(n) = g(n) + h(n) - g(n): Actual cost from start to node n - h(n): Heuristic estimate from n to goal - f(n): Estimated total cost through n - **Admissible Heuristic**: h(n) ≤ actual cost (never overestimates) - **Consistent Heuristic**: h(n) ≤ cost(n→n') + h(n') (triangle inequality) ## When to Use A* **Use A* when:** - You have a specific goal node (not single-source to all) - You can provide a good heuristic estimate - The heuristic is admissible (underestimates) **Use Dijkstra when:** - No good heuristic available (h(n) = 0 reduces A* to Dijkstra) - You need shortest paths to all nodes from a source ## Heuristic Examples | Domain | Heuristic | Admissible? | |--------|-----------|-------------| | Grid (4-way) | Manhattan distance | Yes | | Grid (8-way) | Chebyshev distance | Yes | | Geospatial | Haversine/great-circle | Yes | | Road networks | Precomputed landmarks | Yes | ## Use Cases - Video games: NPC pathfinding on game maps - GPS navigation: Route planning with distance estimates - Robotics: Motion planning with obstacle avoidance - Puzzle solving: Sliding puzzles, mazes, labyrinths </summary>
val aStarInt: heuristic: (Yog.Model.NodeId -> Yog.Model.NodeId -> int) -> start: Yog.Model.NodeId -> goal: Yog.Model.NodeId -> graph: Yog.Model.Graph<'n,int> -> Yog.Pathfinding.Utils.Path<int> option
<summary> Finds the shortest path using A* with integer weights. </summary>
val manhattanDistance: fromId: int -> toId: int -> cols: int -> int
<summary> Calculates the Manhattan distance between two node IDs. This is useful as a heuristic for A* pathfinding on grids. Manhattan distance is the sum of absolute differences in coordinates: |x1 - x2| + |y1 - y2| ## Example let start = coordToId 0 0 10 let goal = coordToId 3 4 10 let distance = manhattanDistance start goal 10 // =&gt; 7 (3 + 4) </summary>

Functions and values

Function or value Description

always arg1 arg2

Full Usage: always arg1 arg2

Parameters:
    arg0 : 'a
    arg1 : 'b

Returns: bool

Always allows movement between adjacent cells.

Every neighbor pair gets an edge regardless of cell data. Useful for fully connected grids or when the cell data is purely informational (e.g., storing coordinates or labels).

Example

1: 
2: 
3: 
4: 
5: 

let labels = array2D [["A"; "B"]
                      ["C"; "D"]]

let grid = fromArray2D labels Undirected rook always
// All adjacent cells are connected
val labels: string array2d
val array2D: rows: #('T seq) seq -> 'T array2d
val grid: obj

arg0 : 'a
arg1 : 'b
Returns: bool

avoiding wallValue from to'

Full Usage: avoiding wallValue from to'

Parameters:
    wallValue : 'a
    from : 'a
    to' : 'a

Returns: bool

Allows movement between any cells except the specified wall value.

Useful for maze-style grids where "#" or similar marks a wall. Both the source and destination cells must not be the wall value.

Example

1: 
2: 
3: 
4: 
5: 
6: 
7: 

// Maze where "#" is impassable
let maze = array2D [["."; "#"; "."]
                    ["."; "."; "."]
                    ["#"; "#"; "."]]

let grid = fromArray2D maze Directed rook (avoiding "#")
// Edges only connect non-wall cells
val maze: string array2d
val array2D: rows: #('T seq) seq -> 'T array2d
val grid: obj

wallValue : 'a
from : 'a
to' : 'a
Returns: bool

bishop

Full Usage: bishop

Returns: (int * int) list

Diagonal (4-way) movement: the four diagonal directions.

Named after the bishop in chess, which moves along diagonals.

↖ . ↗ . · . ↙ . ↘
Returns: (int * int) list

coordToId row col cols

Full Usage: coordToId row col cols

Parameters:
    row : int32
    col : int32
    cols : int

Returns: int32

Converts grid coordinates (row, col) to a node ID.

Uses row-major ordering: id = row × cols + col

Example

1: 
2: 
3: 

coordToId 0 0 3  // => 0
coordToId 1 2 3  // => 5
coordToId 2 1 3  // => 7

row : int32
col : int32
cols : int
Returns: int32

fromArray2D gridData kind topology canMove

Full Usage: fromArray2D gridData kind topology canMove

Parameters:
    gridData : 'n[,]
    kind : GraphType
    topology : (int32 * int32) seq
    canMove : 'n -> 'n -> bool

Returns: Grid<'n, int>

Grid with the underlying graph and dimensions

Builds a grid-graph from a 2D array and a custom movement topology.

Each cell becomes a node, and edges are added between cells based on the topology and the canMove predicate.

Parameters

  • gridData: 2D array of cell data
  • kind: Directed or Undirected
  • topology: List of (row_delta, col_delta) offsets (e.g., rook, queen)
  • canMove: Predicate function (fromData -> toData -> bool)

Time Complexity

O(rows × cols × |topology|)

Example

1: 
2: 
3: 
4: 
5: 
6: 

// 8-way movement on a maze
let maze = array2D [[".";"#";"."]
                    [".";".";"."]
                    ["#";".";"."] ]

let grid = fromArray2D maze Undirected queen (avoiding "#")
val maze: string array2d
val array2D: rows: #('T seq) seq -> 'T array2d
val grid: obj

gridData : 'n[,]
kind : GraphType
topology : (int32 * int32) seq
canMove : 'n -> 'n -> bool
Returns: Grid<'n, int>

Grid with the underlying graph and dimensions

getCell row col grid

Full Usage: getCell row col grid

Parameters:
    row : int
    col : int
    grid : Grid<'a, 'b>

Returns: 'a option

Gets the cell data at the specified grid coordinate.

Returns Some(cell_data) if the coordinate is valid, None otherwise.

Example

1: 
2: 
3: 

match getCell 1 2 grid with
| Some cell -> // Use cell data
| None -> // Out of bounds
union case Option.Some: Value: 'T -> Option<'T>
val cell: obj
union case Option.None: Option<'T>

row : int
col : int
grid : Grid<'a, 'b>
Returns: 'a option

idToCoord id cols

Full Usage: idToCoord id cols

Parameters:
    id : int
    cols : int

Returns: int * int

Converts a node ID back to grid coordinates (row, col).

Example

1: 
2: 
3: 

idToCoord 0 3  // => (0, 0)
idToCoord 5 3  // => (1, 2)
idToCoord 7 3  // => (2, 1)

id : int
cols : int
Returns: int * int

knight

Full Usage: knight

Returns: (int * int) list

L-shaped jumps in all 8 orientations.

Named after the knight in chess, which jumps in an L-shape (2 squares in one direction, 1 square perpendicular).

. ♞ . ♞ . ♞ . . . ♞ . . · . . ♞ . . . ♞ . ♞ . ♞ .
Returns: (int * int) list

manhattanDistance fromId toId cols

Full Usage: manhattanDistance fromId toId cols

Parameters:
    fromId : int
    toId : int
    cols : int

Returns: int

Calculates the Manhattan distance between two node IDs.

This is useful as a heuristic for A* pathfinding on grids. Manhattan distance is the sum of absolute differences in coordinates: |x1 - x2| + |y1 - y2|

Example

1: 
2: 
3: 
4: 

let start = coordToId 0 0 10
let goal = coordToId 3 4 10
let distance = manhattanDistance start goal 10
// => 7 (3 + 4)
val start: obj
val goal: obj
val distance: obj

fromId : int
toId : int
cols : int
Returns: int

queen

Full Usage: queen

Returns: (int * int) list

All 8 surrounding directions: cardinal + diagonal.

Named after the queen in chess, which combines rook and bishop movement.

↖ ↑ ↗ ← · → ↙ ↓ ↘
Returns: (int * int) list

rook

Full Usage: rook

Returns: (int * int) list

Cardinal (4-way) movement: up, down, left, right.

Named after the rook in chess, which moves along ranks and files.

. ↑ . ← · → . ↓ .
Returns: (int * int) list

toGraph grid

Full Usage: toGraph grid

Parameters:
    grid : Grid<'a, 'b>

Returns: Graph<'a, 'b>

Converts the grid to a standard Graph.

The resulting graph can be used with all yog algorithms.

Example

1: 
2: 

let graph = toGraph grid
// Now use with pathfinding, traversal, etc.
val graph: obj

grid : Grid<'a, 'b>
Returns: Graph<'a, 'b>

walkable validValue from to'

Full Usage: walkable validValue from to'

Parameters:
    validValue : 'a
    from : 'a
    to' : 'a

Returns: bool

Allows movement only between cells matching the specified value.

The inverse of avoiding — instead of blacklisting one value, this whitelists exactly one value. Both the source and destination cells must match the valid value.

Example

1: 
2: 
3: 
4: 
5: 
6: 
7: 

// Grid with varied terrain — only "." is walkable
let terrain = array2D [["."; "~"; "^"]
                       ["."; "."; "^"]
                       ["~"; "."; "."]]

let grid = fromArray2D terrain Directed rook (walkable ".")
// Only "." → "." edges exist
val terrain: string array2d
val array2D: rows: #('T seq) seq -> 'T array2d
val grid: obj

validValue : 'a
from : 'a
to' : 'a
Returns: bool