Current section
Files
Jump to
Current section
Files
src/yog@builder@toroidal.erl
-module(yog@builder@toroidal).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch, inline]).
-define(FILEPATH, "src/yog/builder/toroidal.gleam").
-export([coord_to_id/3, from_2d_list_with_topology/4, id_to_coord/2, toroidal_manhattan_distance/4, toroidal_chebyshev_distance/4, toroidal_octile_distance/4, to_graph/1, to_grid/1, rows/1, cols/1, get_cell/3, find_node/2, rook/0, from_2d_list/3, bishop/0, queen/0, knight/0, avoiding/1, walkable/1, always/0, including/1]).
-export_type([toroidal_grid/2]).
-if(?OTP_RELEASE >= 27).
-define(MODULEDOC(Str), -moduledoc(Str)).
-define(DOC(Str), -doc(Str)).
-else.
-define(MODULEDOC(Str), -compile([])).
-define(DOC(Str), -compile([])).
-endif.
?MODULEDOC(
" Toroidal grid builder - grids where edges wrap around.\n"
"\n"
" A toroidal grid is like a regular grid, but movement wraps at the boundaries:\n"
" moving off the right edge brings you to the left edge, moving off the bottom\n"
" brings you to the top. This creates a torus topology (like Pac-Man or Asteroids).\n"
"\n"
" ## Use Cases\n"
"\n"
" - **Games**: Pac-Man, Civilization, roguelikes with wrapping maps\n"
" - **Cellular automata**: Conway's Game of Life without edge artifacts\n"
" - **Simulations**: Physics simulations where boundaries shouldn't matter\n"
"\n"
" ## Distance Heuristics for Toroidal Grids\n"
"\n"
" Regular distance functions don't account for wrapping. Use these instead:\n"
"\n"
" - **Rook (4-way)** → `toroidal_manhattan_distance`\n"
" - **Queen (8-way)** → `toroidal_chebyshev_distance`\n"
" - **Weighted diagonals** → `toroidal_octile_distance`\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" import yog/builder/toroidal\n"
" import yog/model.{Directed}\n"
"\n"
" pub fn main() {\n"
" let grid_data = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]\n"
"\n"
" // Create toroidal grid where all moves wrap\n"
" let grid = toroidal.from_2d_list(\n"
" grid_data,\n"
" Directed,\n"
" can_move: toroidal.always(),\n"
" )\n"
"\n"
" // Distance from (0,0) to (2,2) goes \"around\" the grid\n"
" // On 3x3: direct is 4, but wrapping is 2 (up 1 + left 1)\n"
" let start = toroidal.coord_to_id(0, 0, 3)\n"
" let goal = toroidal.coord_to_id(2, 2, 3)\n"
" let dist = toroidal.toroidal_manhattan_distance(start, goal, 3, 3)\n"
" // dist = 2\n"
" }\n"
" ```\n"
).
-opaque toroidal_grid(IUG, IUH) :: {toroidal_grid,
yog@model:graph(IUG, IUH),
integer(),
integer()}.
-file("src/yog/builder/toroidal.gleam", 178).
?DOC(
" Wraps a coordinate to stay within bounds [0, size).\n"
"\n"
" Handles negative values correctly for wrapping.\n"
).
-spec wrap_coordinate(integer(), integer()) -> integer().
wrap_coordinate(Coord, Size) ->
case case Size of
0 -> 0;
Gleam@denominator -> Coord rem Gleam@denominator
end of
N when N < 0 ->
N + Size;
N@1 ->
N@1
end.
-file("src/yog/builder/toroidal.gleam", 318).
?DOC(
" Converts grid coordinates (row, col) to a node ID.\n"
"\n"
" Uses row-major ordering: id = row * cols + col\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" toroidal.coord_to_id(0, 0, 3) // => 0\n"
" toroidal.coord_to_id(1, 2, 3) // => 5\n"
" toroidal.coord_to_id(2, 1, 3) // => 7\n"
" ```\n"
).
-spec coord_to_id(integer(), integer(), integer()) -> integer().
coord_to_id(Row, Col, Cols) ->
yog@builder@grid:coord_to_id(Row, Col, Cols).
-file("src/yog/builder/toroidal.gleam", 118).
?DOC(
" Creates a toroidal graph from a 2D list using a custom movement topology.\n"
"\n"
" Like `from_2d_list`, but allows custom movement patterns. All movement\n"
" wraps at boundaries.\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" // 8-way toroidal movement\n"
" let grid = toroidal.from_2d_list_with_topology(\n"
" data,\n"
" model.Directed,\n"
" toroidal.queen(),\n"
" can_move: toroidal.always(),\n"
" )\n"
" ```\n"
"\n"
" **Time Complexity:** O(rows × cols × |topology|)\n"
).
-spec from_2d_list_with_topology(
list(list(IUN)),
yog@model:graph_type(),
list({integer(), integer()}),
fun((IUN, IUN) -> boolean())
) -> toroidal_grid(IUN, integer()).
from_2d_list_with_topology(Grid_data, Graph_type, Topology, Can_move) ->
Rows = erlang:length(Grid_data),
Cols = case Grid_data of
[First_row | _] ->
erlang:length(First_row);
[] ->
0
end,
Mut_graph = yog@model:new(Graph_type),
Cells = begin
_pipe = Grid_data,
_pipe@2 = gleam@list:index_map(
_pipe,
fun(Row, Row_idx) -> _pipe@1 = Row,
gleam@list:index_map(
_pipe@1,
fun(Cell, Col_idx) -> {Row_idx, Col_idx, Cell} end
) end
),
lists:append(_pipe@2)
end,
Graph_with_nodes = begin
_pipe@3 = Cells,
gleam@list:fold(
_pipe@3,
Mut_graph,
fun(G, Cell@1) ->
{Row@1, Col, Data} = Cell@1,
Id = coord_to_id(Row@1, Col, Cols),
yog@model:add_node(G, Id, Data)
end
)
end,
Graph_with_edges = begin
gleam@list:fold(
Cells,
Graph_with_nodes,
fun(G@1, Cell@2) ->
{Row@2, Col@1, From_data} = Cell@2,
From_id = coord_to_id(Row@2, Col@1, Cols),
gleam@list:fold(
Topology,
G@1,
fun(Acc_g, Delta) ->
{D_row, D_col} = Delta,
N_row = wrap_coordinate(Row@2 + D_row, Rows),
N_col = wrap_coordinate(Col@1 + D_col, Cols),
To_id = coord_to_id(N_row, N_col, Cols),
To_data@1 = case gleam_stdlib:map_get(
erlang:element(3, Graph_with_nodes),
To_id
) of
{ok, To_data} -> To_data;
_assert_fail ->
erlang:error(#{gleam_error => let_assert,
message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
file => <<?FILEPATH/utf8>>,
module => <<"yog/builder/toroidal"/utf8>>,
function => <<"from_2d_list_with_topology"/utf8>>,
line => 161,
value => _assert_fail,
start => 4874,
'end' => 4938,
pattern_start => 4885,
pattern_end => 4896})
end,
case Can_move(From_data, To_data@1) of
true ->
G@3 = case yog@model:add_edge(
Acc_g,
From_id,
To_id,
1
) of
{ok, G@2} -> G@2;
_assert_fail@1 ->
erlang:error(
#{gleam_error => let_assert,
message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
file => <<?FILEPATH/utf8>>,
module => <<"yog/builder/toroidal"/utf8>>,
function => <<"from_2d_list_with_topology"/utf8>>,
line => 164,
value => _assert_fail@1,
start => 5003,
'end' => 5088,
pattern_start => 5014,
pattern_end => 5019}
)
end,
G@3;
false ->
Acc_g
end
end
)
end
)
end,
{toroidal_grid, Graph_with_edges, Rows, Cols}.
-file("src/yog/builder/toroidal.gleam", 331).
?DOC(
" Converts a node ID back to grid coordinates (row, col).\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" toroidal.id_to_coord(0, 3) // => #(0, 0)\n"
" toroidal.id_to_coord(5, 3) // => #(1, 2)\n"
" toroidal.id_to_coord(7, 3) // => #(2, 1)\n"
" ```\n"
).
-spec id_to_coord(integer(), integer()) -> {integer(), integer()}.
id_to_coord(Id, Cols) ->
yog@builder@grid:id_to_coord(Id, Cols).
-file("src/yog/builder/toroidal.gleam", 208).
?DOC(
" Calculates the Manhattan distance on a toroidal grid.\n"
"\n"
" Takes the shorter path, accounting for wrapping. For example, on a 10-wide\n"
" grid, the distance from column 1 to column 9 is 2 (wrapping left), not 8.\n"
"\n"
" **Use this for:** Rook (4-way) movement on toroidal grids\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" // On a 10x10 toroidal grid\n"
" let start = toroidal.coord_to_id(1, 1, 10)\n"
" let goal = toroidal.coord_to_id(9, 9, 10)\n"
"\n"
" // Regular Manhattan: 8 + 8 = 16\n"
" // Toroidal: min(8,2) + min(8,2) = 4 (wrap both ways)\n"
" toroidal.toroidal_manhattan_distance(start, goal, 10, 10)\n"
" // => 4\n"
" ```\n"
).
-spec toroidal_manhattan_distance(integer(), integer(), integer(), integer()) -> integer().
toroidal_manhattan_distance(From_id, To_id, Cols, Rows) ->
{From_row, From_col} = id_to_coord(From_id, Cols),
{To_row, To_col} = id_to_coord(To_id, Cols),
Row_diff = gleam@int:absolute_value(From_row - To_row),
Col_diff = gleam@int:absolute_value(From_col - To_col),
Min_row_dist = gleam@int:min(Row_diff, Rows - Row_diff),
Min_col_dist = gleam@int:min(Col_diff, Cols - Col_diff),
Min_row_dist + Min_col_dist.
-file("src/yog/builder/toroidal.gleam", 245).
?DOC(
" Calculates the Chebyshev distance on a toroidal grid.\n"
"\n"
" Like toroidal Manhattan, but uses max instead of sum. Optimal for\n"
" 8-way (queen) movement where wrapping is allowed.\n"
"\n"
" **Use this for:** Queen (8-way) movement on toroidal grids\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" // On a 10x10 toroidal grid\n"
" let start = toroidal.coord_to_id(1, 1, 10)\n"
" let goal = toroidal.coord_to_id(9, 9, 10)\n"
"\n"
" // Toroidal Chebyshev: max(min(8,2), min(8,2)) = 2\n"
" toroidal.toroidal_chebyshev_distance(start, goal, 10, 10)\n"
" // => 2\n"
" ```\n"
).
-spec toroidal_chebyshev_distance(integer(), integer(), integer(), integer()) -> integer().
toroidal_chebyshev_distance(From_id, To_id, Cols, Rows) ->
{From_row, From_col} = id_to_coord(From_id, Cols),
{To_row, To_col} = id_to_coord(To_id, Cols),
Row_diff = gleam@int:absolute_value(From_row - To_row),
Col_diff = gleam@int:absolute_value(From_col - To_col),
Min_row_dist = gleam@int:min(Row_diff, Rows - Row_diff),
Min_col_dist = gleam@int:min(Col_diff, Cols - Col_diff),
gleam@int:max(Min_row_dist, Min_col_dist).
-file("src/yog/builder/toroidal.gleam", 280).
?DOC(
" Calculates the Octile distance on a toroidal grid.\n"
"\n"
" For grids where diagonal moves cost √2 and orthogonal moves cost 1,\n"
" accounting for wrapping at boundaries.\n"
"\n"
" **Use this for:** Weighted 8-directional movement on toroidal grids\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" let start = toroidal.coord_to_id(1, 1, 10)\n"
" let goal = toroidal.coord_to_id(9, 9, 10)\n"
"\n"
" toroidal.toroidal_octile_distance(start, goal, 10, 10)\n"
" // => 2.828... (2 × √2)\n"
" ```\n"
).
-spec toroidal_octile_distance(integer(), integer(), integer(), integer()) -> float().
toroidal_octile_distance(From_id, To_id, Cols, Rows) ->
{From_row, From_col} = id_to_coord(From_id, Cols),
{To_row, To_col} = id_to_coord(To_id, Cols),
Row_diff = gleam@int:absolute_value(From_row - To_row),
Col_diff = gleam@int:absolute_value(From_col - To_col),
Min_row_dist = gleam@int:min(Row_diff, Rows - Row_diff),
Min_col_dist = gleam@int:min(Col_diff, Cols - Col_diff),
Min_d = gleam@int:min(Min_row_dist, Min_col_dist),
Max_d = gleam@int:max(Min_row_dist, Min_col_dist),
(erlang:float(Min_d) * 1.414213562373095) + erlang:float(Max_d - Min_d).
-file("src/yog/builder/toroidal.gleam", 350).
?DOC(
" Converts the toroidal grid to a standard `Graph`.\n"
"\n"
" The resulting graph can be used with all yog algorithms.\n"
" The wrapping connections are already encoded as edges.\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" let graph = toroidal.to_graph(grid)\n"
" // Now use with pathfinding, traversal, etc.\n"
" ```\n"
).
-spec to_graph(toroidal_grid(IUT, IUU)) -> yog@model:graph(IUT, IUU).
to_graph(Grid) ->
erlang:element(2, Grid).
-file("src/yog/builder/toroidal.gleam", 367).
?DOC(
" Converts the toroidal grid to a standard `Grid`.\n"
"\n"
" The resulting grid maintains the same graph structure with all\n"
" wrapping connections as edges. Useful for using grid-specific\n"
" functionality like ASCII rendering.\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" let toroidal_grid = // ... create toroidal grid\n"
" let grid = toroidal.to_grid(toroidal_grid)\n"
" io.println(ascii.grid_to_string(grid))\n"
" ```\n"
).
-spec to_grid(toroidal_grid(IUZ, IVA)) -> yog@builder@grid:grid(IUZ, IVA).
to_grid(Grid) ->
{grid,
erlang:element(2, Grid),
erlang:element(3, Grid),
erlang:element(4, Grid)}.
-file("src/yog/builder/toroidal.gleam", 372).
?DOC(" Gets the number of rows in the toroidal grid.\n").
-spec rows(toroidal_grid(any(), any())) -> integer().
rows(Grid) ->
erlang:element(3, Grid).
-file("src/yog/builder/toroidal.gleam", 377).
?DOC(" Gets the number of columns in the toroidal grid.\n").
-spec cols(toroidal_grid(any(), any())) -> integer().
cols(Grid) ->
erlang:element(4, Grid).
-file("src/yog/builder/toroidal.gleam", 393).
?DOC(
" Gets the cell data at the specified grid coordinate.\n"
"\n"
" Returns `Ok(cell_data)` if the coordinate is valid, `Error(Nil)` otherwise.\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" case toroidal.get_cell(grid, 1, 2) {\n"
" Ok(cell) -> // Use cell data\n"
" Error(_) -> // Out of bounds\n"
" }\n"
" ```\n"
).
-spec get_cell(toroidal_grid(IVN, any()), integer(), integer()) -> {ok, IVN} |
{error, nil}.
get_cell(Grid, Row, Col) ->
case (((Row >= 0) andalso (Row < erlang:element(3, Grid))) andalso (Col >= 0))
andalso (Col < erlang:element(4, Grid)) of
false ->
{error, nil};
true ->
Id = coord_to_id(Row, Col, erlang:element(4, Grid)),
gleam_stdlib:map_get(erlang:element(3, erlang:element(2, Grid)), Id)
end.
-file("src/yog/builder/toroidal.gleam", 420).
?DOC(
" Finds a node in the grid where the cell data matches a predicate.\n"
"\n"
" Returns the node ID of the first matching cell, or Error(Nil) if not found.\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" // Find the starting position marked with 'S'\n"
" case toroidal.find_node(grid, fn(cell) { cell == \"S\" }) {\n"
" Ok(start_id) -> // Use start_id\n"
" Error(_) -> // Not found\n"
" }\n"
" ```\n"
).
-spec find_node(toroidal_grid(IVT, any()), fun((IVT) -> boolean())) -> {ok,
integer()} |
{error, nil}.
find_node(Grid, Predicate) ->
Max_id = (erlang:element(3, Grid) * erlang:element(4, Grid)) - 1,
_pipe = yog@internal@util:range(0, Max_id),
gleam@list:find_map(
_pipe,
fun(Id) ->
case gleam_stdlib:map_get(
erlang:element(3, erlang:element(2, Grid)),
Id
) of
{ok, Data} ->
case Predicate(Data) of
true ->
{ok, Id};
false ->
{error, nil}
end;
{error, _} ->
{error, nil}
end
end
).
-file("src/yog/builder/toroidal.gleam", 451).
?DOC(
" Cardinal (4-way) movement: up, down, left, right.\n"
"\n"
" Named after the rook in chess. Wraps at boundaries on toroidal grids.\n"
"\n"
" ```\n"
" . ↑ .\n"
" ← · →\n"
" . ↓ .\n"
" ```\n"
).
-spec rook() -> list({integer(), integer()}).
rook() ->
yog@builder@grid:rook().
-file("src/yog/builder/toroidal.gleam", 92).
?DOC(
" Creates a toroidal graph from a 2D list using 4-directional (rook) movement.\n"
"\n"
" Movement wraps at boundaries: moving right from the rightmost column\n"
" brings you to the leftmost column, and similarly for vertical movement.\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" let data = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]\n"
"\n"
" let grid = toroidal.from_2d_list(\n"
" data,\n"
" model.Directed,\n"
" can_move: toroidal.always(),\n"
" )\n"
"\n"
" // Cell at (0, 2) connects to cell at (0, 0) via wrapping\n"
" ```\n"
"\n"
" **Time Complexity:** O(rows × cols)\n"
).
-spec from_2d_list(
list(list(IUI)),
yog@model:graph_type(),
fun((IUI, IUI) -> boolean())
) -> toroidal_grid(IUI, integer()).
from_2d_list(Grid_data, Graph_type, Can_move) ->
from_2d_list_with_topology(Grid_data, Graph_type, rook(), Can_move).
-file("src/yog/builder/toroidal.gleam", 464).
?DOC(
" Diagonal (4-way) movement: the four diagonal directions.\n"
"\n"
" Named after the bishop in chess. Wraps at boundaries on toroidal grids.\n"
"\n"
" ```\n"
" ↖ . ↗\n"
" . · .\n"
" ↙ . ↘\n"
" ```\n"
).
-spec bishop() -> list({integer(), integer()}).
bishop() ->
yog@builder@grid:bishop().
-file("src/yog/builder/toroidal.gleam", 477).
?DOC(
" All 8 surrounding directions: cardinal + diagonal.\n"
"\n"
" Named after the queen in chess. Wraps at boundaries on toroidal grids.\n"
"\n"
" ```\n"
" ↖ ↑ ↗\n"
" ← · →\n"
" ↙ ↓ ↘\n"
" ```\n"
).
-spec queen() -> list({integer(), integer()}).
queen() ->
yog@builder@grid:queen().
-file("src/yog/builder/toroidal.gleam", 492).
?DOC(
" L-shaped jumps in all 8 orientations.\n"
"\n"
" Named after the knight in chess. Wraps at boundaries on toroidal grids.\n"
"\n"
" ```\n"
" . ♞ . ♞ .\n"
" ♞ . . . ♞\n"
" . . · . .\n"
" ♞ . . . ♞\n"
" . ♞ . ♞ .\n"
" ```\n"
).
-spec knight() -> list({integer(), integer()}).
knight() ->
yog@builder@grid:knight().
-file("src/yog/builder/toroidal.gleam", 515).
?DOC(
" Allows movement between any cells except the specified wall value.\n"
"\n"
" Both the source and destination cells must not be the wall value.\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" let maze = [[\".\", \"#\", \".\"], [\".\", \".\", \".\"], [\"#\", \"#\", \".\"]]\n"
"\n"
" let g = toroidal.from_2d_list(\n"
" maze,\n"
" model.Directed,\n"
" can_move: toroidal.avoiding(\"#\"),\n"
" )\n"
" ```\n"
).
-spec avoiding(IWD) -> fun((IWD, IWD) -> boolean()).
avoiding(Wall_value) ->
yog@builder@grid:avoiding(Wall_value).
-file("src/yog/builder/toroidal.gleam", 534).
?DOC(
" Allows movement only between cells matching the specified value.\n"
"\n"
" Both the source and destination cells must match the valid value.\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" let terrain = [[\".\", \"~\", \"^\"], [\".\", \".\", \"^\"], [\"~\", \".\", \".\"]]\n"
"\n"
" let g = toroidal.from_2d_list(\n"
" terrain,\n"
" model.Directed,\n"
" can_move: toroidal.walkable(\".\"),\n"
" )\n"
" ```\n"
).
-spec walkable(IWE) -> fun((IWE, IWE) -> boolean()).
walkable(Valid_value) ->
yog@builder@grid:walkable(Valid_value).
-file("src/yog/builder/toroidal.gleam", 553).
?DOC(
" Always allows movement between adjacent cells.\n"
"\n"
" Every neighbor pair gets an edge regardless of cell data.\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" let labels = [[\"A\", \"B\"], [\"C\", \"D\"]]\n"
"\n"
" let g = toroidal.from_2d_list(\n"
" labels,\n"
" model.Undirected,\n"
" can_move: toroidal.always(),\n"
" )\n"
" ```\n"
).
-spec always() -> fun((IWF, IWF) -> boolean()).
always() ->
yog@builder@grid:always().
-file("src/yog/builder/toroidal.gleam", 572).
?DOC(
" Allows movement only between cells matching any of the specified values.\n"
"\n"
" Both the source and destination cells must be included in the valid values list.\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" let terrain = [[\".\", \"P\", \"#\"], [\"#\", \".\", \".\"]]\n"
"\n"
" let g = toroidal.from_2d_list(\n"
" terrain,\n"
" model.Directed,\n"
" can_move: toroidal.including([\".\", \"P\"]),\n"
" )\n"
" ```\n"
).
-spec including(list(IWG)) -> fun((IWG, IWG) -> boolean()).
including(Valid_values) ->
yog@builder@grid:including(Valid_values).