Grid (yog-fsharp) | Yog.FSharp

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):

1: 
2: 
3:

. 

.

Bishop (4-way diagonal):

1:

Queen (8-way):

Knight (L-shaped):

1: 
2: 
3: 
4: 
5:

. 

. . 

.

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 array2D: rows: #('T seq) seq -> 'T array2d

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>

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

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.

1:

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

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).

1: 
2: 
3: 
4: 
5:

. 

. . 

.

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

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

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.

1: 
2: 
3:

. 

.

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