yog - v6.0.0

yog/builder/toroidal

Toroidal grid builder - grids where edges wrap around.

A toroidal grid is like a regular grid, but movement wraps at the boundaries: moving off the right edge brings you to the left edge, moving off the bottom brings you to the top. This creates a torus topology (like Pac-Man or Asteroids).

Use Cases

Distance Heuristics for Toroidal Grids

Regular distance functions don’t account for wrapping. Use these instead:

Example

import yog/builder/toroidal
import yog/model.{Directed}

pub fn main() {
  let grid_data = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]

  // Create toroidal grid where all moves wrap
  let grid = toroidal.from_2d_list(
    grid_data,
    Directed,
    can_move: toroidal.always(),
  )

  // Distance from (0,0) to (2,2) goes "around" the grid
  // On 3x3: direct is 4, but wrapping is 2 (up 1 + left 1)
  let start = toroidal.coord_to_id(0, 0, 3)
  let goal = toroidal.coord_to_id(2, 2, 3)
  let dist = toroidal.toroidal_manhattan_distance(start, goal, 3, 3)
  // dist = 2
}

Types

ToroidalGrid

opaque </>

A toroidal grid where edges wrap around to opposite sides.

Internally wraps a regular Grid, but uses different construction and distance calculation logic.

pub opaque type ToroidalGrid(cell_data, edge_data)

Values

always

</> 
pub fn always() -> fn(cell_data, cell_data) -> Bool

Always allows movement between adjacent cells.

Every neighbor pair gets an edge regardless of cell data.

Example

let labels = [["A", "B"], ["C", "D"]]

let g = toroidal.from_2d_list(
  labels,
  model.Undirected,
  can_move: toroidal.always(),
)

avoiding

</> 
pub fn avoiding(
  wall_value: cell_data,
) -> fn(cell_data, cell_data) -> Bool

Allows movement between any cells except the specified wall value.

Both the source and destination cells must not be the wall value.

Example

let maze = [[".", "#", "."], [".", ".", "."], ["#", "#", "."]]

let g = toroidal.from_2d_list(
  maze,
  model.Directed,
  can_move: toroidal.avoiding("#"),
)

bishop

</> 
pub fn bishop() -> List(#(Int, Int))

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

Named after the bishop in chess. Wraps at boundaries on toroidal grids.

↖ . ↗
. · .
↙ . ↘

cols

</> 
pub fn cols(grid: ToroidalGrid(cell_data, e)) -> Int

Gets the number of columns in the toroidal grid.

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

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

find_node

</> 
pub fn find_node(
  grid: ToroidalGrid(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 toroidal.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,
) -> ToroidalGrid(cell_data, Int)

Creates a toroidal graph from a 2D list using 4-directional (rook) movement.

Movement wraps at boundaries: moving right from the rightmost column brings you to the leftmost column, and similarly for vertical movement.

Example

let data = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]

let grid = toroidal.from_2d_list(
  data,
  model.Directed,
  can_move: toroidal.always(),
)

// Cell at (0, 2) connects to cell at (0, 0) via wrapping

Time Complexity: O(rows × cols)

from_2d_list_with_topology

</> 
pub fn from_2d_list_with_topology(
  grid_data: List(List(cell_data)),
  graph_type: model.GraphType,
  topology: List(#(Int, Int)),
  can_move can_move: fn(cell_data, cell_data) -> Bool,
) -> ToroidalGrid(cell_data, Int)

Creates a toroidal graph from a 2D list using a custom movement topology.

Like from_2d_list, but allows custom movement patterns. All movement wraps at boundaries.

Example

// 8-way toroidal movement
let grid = toroidal.from_2d_list_with_topology(
  data,
  model.Directed,
  toroidal.queen(),
  can_move: toroidal.always(),
)

Time Complexity: O(rows × cols × |topology|)

get_cell

</> 
pub fn get_cell(
  grid: ToroidalGrid(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 toroidal.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

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

including

</> 
pub fn including(
  valid_values: List(cell_data),
) -> fn(cell_data, cell_data) -> Bool

Allows movement only between cells matching any of the specified values.

Both the source and destination cells must be included in the valid values list.

Example

let terrain = [[".", "P", "#"], ["#", ".", "."]]

let g = toroidal.from_2d_list(
  terrain,
  model.Directed,
  can_move: toroidal.including([".", "P"]),
)

knight

</> 
pub fn knight() -> List(#(Int, Int))

L-shaped jumps in all 8 orientations.

Named after the knight in chess. Wraps at boundaries on toroidal grids.

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

queen

</> 
pub fn queen() -> List(#(Int, Int))

All 8 surrounding directions: cardinal + diagonal.

Named after the queen in chess. Wraps at boundaries on toroidal grids.

↖ ↑ ↗
← · →
↙ ↓ ↘

rook

</> 
pub fn rook() -> List(#(Int, Int))

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

Named after the rook in chess. Wraps at boundaries on toroidal grids.

. ↑ .
← · →
. ↓ .

rows

</> 
pub fn rows(grid: ToroidalGrid(cell_data, e)) -> Int

Gets the number of rows in the toroidal grid.

to_graph

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

Converts the toroidal grid to a standard Graph.

The resulting graph can be used with all yog algorithms. The wrapping connections are already encoded as edges.

Example

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

to_grid

</> 
pub fn to_grid(
  grid: ToroidalGrid(cell_data, e),
) -> grid.Grid(cell_data, e)

Converts the toroidal grid to a standard Grid.

The resulting grid maintains the same graph structure with all wrapping connections as edges. Useful for using grid-specific functionality like ASCII rendering.

Example

let toroidal_grid = // ... create toroidal grid
let grid = toroidal.to_grid(toroidal_grid)
io.println(ascii.grid_to_string(grid))

toroidal_chebyshev_distance

</> 
pub fn toroidal_chebyshev_distance(
  from_id: Int,
  to_id: Int,
  cols: Int,
  rows: Int,
) -> Int

Calculates the Chebyshev distance on a toroidal grid.

Like toroidal Manhattan, but uses max instead of sum. Optimal for 8-way (queen) movement where wrapping is allowed.

Use this for: Queen (8-way) movement on toroidal grids

Example

// On a 10x10 toroidal grid
let start = toroidal.coord_to_id(1, 1, 10)
let goal = toroidal.coord_to_id(9, 9, 10)

// Toroidal Chebyshev: max(min(8,2), min(8,2)) = 2
toroidal.toroidal_chebyshev_distance(start, goal, 10, 10)
// => 2

toroidal_manhattan_distance

</> 
pub fn toroidal_manhattan_distance(
  from_id: Int,
  to_id: Int,
  cols: Int,
  rows: Int,
) -> Int

Calculates the Manhattan distance on a toroidal grid.

Takes the shorter path, accounting for wrapping. For example, on a 10-wide grid, the distance from column 1 to column 9 is 2 (wrapping left), not 8.

Use this for: Rook (4-way) movement on toroidal grids

Example

// On a 10x10 toroidal grid
let start = toroidal.coord_to_id(1, 1, 10)
let goal = toroidal.coord_to_id(9, 9, 10)

// Regular Manhattan: 8 + 8 = 16
// Toroidal: min(8,2) + min(8,2) = 4 (wrap both ways)
toroidal.toroidal_manhattan_distance(start, goal, 10, 10)
// => 4

toroidal_octile_distance

</> 
pub fn toroidal_octile_distance(
  from_id: Int,
  to_id: Int,
  cols: Int,
  rows: Int,
) -> Float

Calculates the Octile distance on a toroidal grid.

For grids where diagonal moves cost √2 and orthogonal moves cost 1, accounting for wrapping at boundaries.

Use this for: Weighted 8-directional movement on toroidal grids

Example

let start = toroidal.coord_to_id(1, 1, 10)
let goal = toroidal.coord_to_id(9, 9, 10)

toroidal.toroidal_octile_distance(start, goal, 10, 10)
// => 2.828... (2 × √2)

walkable

</> 
pub fn walkable(
  valid_value: cell_data,
) -> fn(cell_data, cell_data) -> Bool

Allows movement only between cells matching the specified value.

Both the source and destination cells must match the valid value.

Example

let terrain = [[".", "~", "^"], [".", ".", "^"], ["~", ".", "."]]

let g = toroidal.from_2d_list(
  terrain,
  model.Directed,
  can_move: toroidal.walkable("."),
)
✨ Search Document