yog - v1.2.3

yog/builder/grid

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.

Example

import yog/builder/grid
import yog/model.{Directed}
import yog/traversal.{BreadthFirst}

pub fn main() {
  // A simple heightmap where you can only climb up by 1
  let heightmap = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
  ]

  // Build a graph where edges exist only if height diff <= 1
  let grid = grid.from_2d_list(
    heightmap,
    Directed,
    can_move: fn(from_height, to_height) {
      to_height - from_height <= 1
    }
  )

  // Convert to graph and use with algorithms
  let graph = grid.to_graph(grid)
  let start = grid.coord_to_id(0, 0, grid.cols)
  let goal = grid.coord_to_id(2, 2, grid.cols)

  traversal.walk_until(
    from: start,
    in: graph,
    using: BreadthFirst,
    until: fn(node) { node == goal }
  )
}

Types

Grid

</>

A grid builder that wraps a graph and maintains grid dimensions.

The grid uses row-major ordering: node_id = row * cols + col

pub type Grid(cell_data, edge_data) {
  Grid(
    graph: model.Graph(cell_data, edge_data),
    rows: Int,
    cols: Int,
  )
}

Constructors 

  • Grid(
  graph: model.Graph(cell_data, edge_data),
  rows: Int,
  cols: Int,
)

    Arguments

    graph

    The underlying graph structure

    rows

    Number of rows in the grid

    cols

    Number of columns in the grid

Values

coord_to_id

</> 
pub fn coord_to_id(row: Int, col: Int, cols: Int) -> Int

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

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

Example

grid.coord_to_id(0, 0, 3)  // => 0
grid.coord_to_id(1, 2, 3)  // => 5
grid.coord_to_id(2, 1, 3)  // => 7

find_node

</> 
pub fn find_node(
  grid: Grid(cell_data, e),
  predicate: fn(cell_data) -> Bool,
) -> Result(Int, Nil)

Finds a node in the grid where the cell data matches a predicate.

Returns the node ID of the first matching cell, or Error(Nil) if not found.

Example

// Find the starting position marked with 'S'
case grid.find_node(grid, fn(cell) { cell == "S" }) {
  Ok(start_id) -> // Use start_id
  Error(_) -> // Not found
}

from_2d_list

</> 
pub fn from_2d_list(
  grid_data: List(List(cell_data)),
  graph_type: model.GraphType,
  can_move can_move: fn(cell_data, cell_data) -> Bool,
) -> Grid(cell_data, Int)

Creates a graph from a 2D list (list of rows).

Each cell becomes a node, and edges are added between adjacent cells (up/down/left/right) if the can_move predicate returns True.

Example

// A heightmap where you can only climb 1 unit at a time
let heightmap = [[1, 2, 3], [2, 3, 4], [3, 4, 5]]

let grid = grid.from_2d_list(
  heightmap,
  model.Directed,
  can_move: fn(from, to) { to - from <= 1 }
)

Time Complexity: O(rows * cols)

get_cell

</> 
pub fn get_cell(
  grid: Grid(cell_data, e),
  row: Int,
  col: Int,
) -> Result(cell_data, Nil)

Gets the cell data at the specified grid coordinate.

Returns Ok(cell_data) if the coordinate is valid, Error(Nil) otherwise.

Example

case grid.get_cell(grid, 1, 2) {
  Ok(cell) -> // Use cell data
  Error(_) -> // Out of bounds
}

id_to_coord

</> 
pub fn id_to_coord(id: Int, cols: Int) -> #(Int, Int)

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

Example

grid.id_to_coord(0, 3)  // => #(0, 0)
grid.id_to_coord(5, 3)  // => #(1, 2)
grid.id_to_coord(7, 3)  // => #(2, 1)

manhattan_distance

</> 
pub fn manhattan_distance(
  from_id: Int,
  to_id: Int,
  cols: Int,
) -> 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

let start = grid.coord_to_id(0, 0, 10)
let goal = grid.coord_to_id(3, 4, 10)
let distance = grid.manhattan_distance(start, goal, 10)
// => 7 (3 + 4)

to_graph

</> 
pub fn to_graph(
  grid: Grid(cell_data, e),
) -> model.Graph(cell_data, e)

Converts the grid to a standard Graph.

The resulting graph can be used with all yog algorithms.

Example

let graph = grid.to_graph(grid)
// Now use with pathfinding, traversal, etc.
✨ Search Document