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
- Games: Pac-Man, Civilization, roguelikes with wrapping maps
- Cellular automata: Conway's Game of Life without edge artifacts
- Simulations: Physics simulations where boundaries shouldn't matter
Distance Heuristics for Toroidal Grids
Regular distance functions don't account for wrapping. Use these instead:
- Rook (4-way) →
toroidal_manhattan_distance/5 - Queen (8-way) →
toroidal_chebyshev_distance/5 - Weighted diagonals →
toroidal_octile_distance/5
Example Usage
# Create a 3x3 toroidal grid
data = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]
# Create toroidal grid where all moves wrap
grid = Yog.Builder.Toroidal.from_2d_list(
data,
:directed,
Yog.Builder.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)
start = Yog.Builder.Toroidal.coord_to_id(0, 0, 3)
goal = Yog.Builder.Toroidal.coord_to_id(2, 2, 3)
dist = Yog.Builder.Toroidal.toroidal_manhattan_distance(start, goal, 3, 3)
# dist = 2Summary
Types
Topology is a list of {row_delta, col_delta} movement offsets
Toroidal grid type (now using ToroidalGraph)
Functions
Always allows movement between adjacent cells.
Creates a predicate that allows movement into any cell except wall_value.
4-way diagonal movement with wrapping.
Converts grid coordinates {row, col} to a node ID.
Finds a node in the grid where the cell data matches a predicate.
Creates a toroidal graph from a 2D list using 4-directional (rook) movement.
Creates a toroidal graph from a 2D list using a custom movement topology.
Gets the cell data at a specific row and column.
Converts a node ID back to grid coordinates {row, col}.
Creates a predicate that allows movement into any of the specified values.
L-shaped knight jumps in all 8 orientations with wrapping.
8-way movement (cardinal + diagonal) with wrapping.
4-way cardinal movement (up, down, left, right) with wrapping.
Converts a toroidal grid into a standard Graph.
Calculates the toroidal Chebyshev distance between two grid node IDs.
Calculates the toroidal Manhattan distance between two grid node IDs.
Calculates the toroidal Octile distance between two grid node IDs.
Creates a predicate that only allows movement into cells matching valid_value.
Types
Topology is a list of {row_delta, col_delta} movement offsets
@type toroidal_grid() :: Yog.Builder.ToroidalGraph.t()
Toroidal grid type (now using ToroidalGraph)
Functions
Always allows movement between adjacent cells.
Creates a predicate that allows movement into any cell except wall_value.
@spec bishop() :: topology()
4-way diagonal movement with wrapping.
Movement offsets: {-1,-1}, {-1,1}, {1,-1}, {1,1}
@spec coord_to_id(integer(), integer(), integer()) :: Yog.node_id()
Converts grid coordinates {row, col} to a node ID.
Delegates to Yog.Builder.Grid.coord_to_id/3.
@spec find_node( toroidal_grid() | Yog.Builder.GridGraph.t() | {:toroidal_grid, Yog.graph(), integer(), integer()}, (term() -> boolean()) ) :: {:ok, Yog.node_id()} | {:error, nil}
Finds a node in the grid where the cell data matches a predicate.
Returns {:ok, node_id} or {:error, nil}.
@spec from_2d_list([[term()]], Yog.Model.graph_type(), (term(), term() -> boolean())) :: Yog.Builder.ToroidalGraph.t()
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.
Examples
data = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
grid = Yog.Builder.Toroidal.from_2d_list(
data,
:directed,
Yog.Builder.Toroidal.always()
)Time Complexity
O(rows × cols)
@spec from_2d_list_with_topology( [[term()]], Yog.Model.graph_type(), topology(), (term(), term() -> boolean()) ) :: Yog.Builder.ToroidalGraph.t()
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.
Examples
# 8-way movement on a toroidal grid
grid = Yog.Builder.Toroidal.from_2d_list_with_topology(
data,
:directed,
Yog.Builder.Toroidal.queen(),
Yog.Builder.Toroidal.always()
)@spec get_cell( toroidal_grid() | Yog.Builder.GridGraph.t() | {:toroidal_grid, Yog.graph(), integer(), integer()}, integer(), integer() ) :: {:ok, term()} | {:error, nil}
Gets the cell data at a specific row and column.
Returns {:ok, cell_data} or {:error, nil} if out of bounds.
@spec id_to_coord(Yog.node_id(), integer()) :: {integer(), integer()}
Converts a node ID back to grid coordinates {row, col}.
Delegates to Yog.Builder.Grid.id_to_coord/2.
Creates a predicate that allows movement into any of the specified values.
@spec knight() :: topology()
L-shaped knight jumps in all 8 orientations with wrapping.
Chess knight movement: {-2,-1}, {-2,1}, {-1,-2}, {-1,2}, {1,-2}, {1,2}, {2,-1}, {2,1}
@spec queen() :: topology()
8-way movement (cardinal + diagonal) with wrapping.
@spec rook() :: topology()
4-way cardinal movement (up, down, left, right) with wrapping.
Default for from_2d_list/3. Movement offsets: {-1,0}, {1,0}, {0,-1}, {0,1}
@spec to_graph( toroidal_grid() | Yog.Builder.GridGraph.t() | {:toroidal_grid, Yog.graph(), integer(), integer()} ) :: Yog.graph()
Converts a toroidal grid into a standard Graph.
@spec toroidal_chebyshev_distance(Yog.node_id(), Yog.node_id(), integer(), integer()) :: integer()
Calculates the toroidal Chebyshev distance between two grid node IDs.
For 8-way (queen) movement on a wrapping grid where diagonal costs equal cardinal costs.
Formula
dx = min(|col1 - col2|, cols - |col1 - col2|)
dy = min(|row1 - row2|, rows - |row1 - row2|)
distance = max(dx, dy)@spec toroidal_manhattan_distance(Yog.node_id(), Yog.node_id(), integer(), integer()) :: integer()
Calculates the toroidal Manhattan distance between two grid node IDs.
For 4-way (rook) movement on a wrapping grid.
Formula
Accounts for wrapping by considering the shorter path around the torus:
dx = min(|col1 - col2|, cols - |col1 - col2|)
dy = min(|row1 - row2|, rows - |row1 - row2|)
distance = dx + dy@spec toroidal_octile_distance(Yog.node_id(), Yog.node_id(), integer(), integer()) :: float()
Calculates the toroidal Octile distance between two grid node IDs.
For 8-way movement on a wrapping grid where diagonal costs are √2 × cardinal cost.
Formula
dx = min(|col1 - col2|, cols - |col1 - col2|)
dy = min(|row1 - row2|, rows - |row1 - row2|)
distance = max(dx, dy) + (√2 - 1) × min(dx, dy)Creates a predicate that only allows movement into cells matching valid_value.