yog

-module(yog@builder@grid).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch, inline]).
-define(FILEPATH, "src/yog/builder/grid.gleam").
-export([rook/0, bishop/0, queen/0, knight/0, coord_to_id/3, from_2d_list_with_topology/4, from_2d_list/3, id_to_coord/2, get_cell/3, to_graph/1, manhattan_distance/3, chebyshev_distance/3, octile_distance/3, find_node/2, avoiding/1, walkable/1, always/0, including/1]).
-export_type([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(
    " A builder for creating graphs from 2D grids.\n"
    "\n"
    " This module provides convenient ways to convert 2D grids (like heightmaps,\n"
    " mazes, or game boards) into graphs for pathfinding and traversal algorithms.\n"
    "\n"
    " ## Choosing the Right Distance Heuristic\n"
    "\n"
    " For optimal A* pathfinding, use the heuristic that matches your topology:\n"
    "\n"
    " - **Rook (4-way)** → `manhattan_distance` - sum of absolute differences\n"
    " - **Queen (8-way)** → `chebyshev_distance` - maximum of absolute differences\n"
    " - **Weighted diagonals** → `octile_distance` - when diagonal moves cost √2\n"
    " - **Bishop or Knight** → `chebyshev_distance` (admissible but may be loose)\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " import yog/builder/grid\n"
    " import yog/model.{Directed}\n"
    " import yog/traversal.{BreadthFirst}\n"
    "\n"
    " pub fn main() {\n"
    "   // A simple heightmap where you can only climb up by 1\n"
    "   let heightmap = [\n"
    "     [1, 2, 3],\n"
    "     [4, 5, 6],\n"
    "     [7, 8, 9]\n"
    "   ]\n"
    "\n"
    "   // Build a graph where edges exist only if height diff <= 1\n"
    "   let grid = grid.from_2d_list(\n"
    "     heightmap,\n"
    "     Directed,\n"
    "     can_move: fn(from_height, to_height) {\n"
    "       to_height - from_height <= 1\n"
    "     }\n"
    "   )\n"
    "\n"
    "   // Convert to graph and use with algorithms\n"
    "   let graph = grid.to_graph(grid)\n"
    "   let start = grid.coord_to_id(0, 0, grid.cols)\n"
    "   let goal = grid.coord_to_id(2, 2, grid.cols)\n"
    "\n"
    "   traversal.walk_until(\n"
    "     from: start,\n"
    "     in: graph,\n"
    "     using: BreadthFirst,\n"
    "     until: fn(node) { node == goal }\n"
    "   )\n"
    " }\n"
    " ```\n"
).

-type grid(HSU, HSV) :: {grid, yog@model:graph(HSU, HSV), integer(), integer()}.

-file("src/yog/builder/grid.gleam", 222).
?DOC(
    " Cardinal (4-way) movement: up, down, left, right.\n"
    "\n"
    " Named after the rook in chess, which moves along ranks and files.\n"
    " This is the default topology used by `from_2d_list`.\n"
    "\n"
    " ```\n"
    " . ↑ .\n"
    " ← · →\n"
    " . ↓ .\n"
    " ```\n"
).
-spec rook() -> list({integer(), integer()}).
rook() ->
    [{-1, 0}, {1, 0}, {0, -1}, {0, 1}].

-file("src/yog/builder/grid.gleam", 235).
?DOC(
    " Diagonal (4-way) movement: the four diagonal directions.\n"
    "\n"
    " Named after the bishop in chess, which moves along diagonals.\n"
    "\n"
    " ```\n"
    " ↖ . ↗\n"
    " . · .\n"
    " ↙ . ↘\n"
    " ```\n"
).
-spec bishop() -> list({integer(), integer()}).
bishop() ->
    [{-1, -1}, {-1, 1}, {1, -1}, {1, 1}].

-file("src/yog/builder/grid.gleam", 248).
?DOC(
    " All 8 surrounding directions: cardinal + diagonal.\n"
    "\n"
    " Named after the queen in chess, which combines rook and bishop movement.\n"
    "\n"
    " ```\n"
    " ↖ ↑ ↗\n"
    " ← · →\n"
    " ↙ ↓ ↘\n"
    " ```\n"
).
-spec queen() -> list({integer(), integer()}).
queen() ->
    [{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}].

-file("src/yog/builder/grid.gleam", 264).
?DOC(
    " L-shaped jumps in all 8 orientations.\n"
    "\n"
    " Named after the knight in chess, which jumps in an L-shape\n"
    " (2 squares in one direction, 1 square perpendicular).\n"
    "\n"
    " ```\n"
    " . ♞ . ♞ .\n"
    " ♞ . . . ♞\n"
    " . . · . .\n"
    " ♞ . . . ♞\n"
    " . ♞ . ♞ .\n"
    " ```\n"
).
-spec knight() -> list({integer(), integer()}).
knight() ->
    [{-2, -1}, {-2, 1}, {-1, -2}, {-1, 2}, {1, -2}, {1, 2}, {2, -1}, {2, 1}].

-file("src/yog/builder/grid.gleam", 292).
?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"
    " grid.coord_to_id(0, 0, 3)  // => 0\n"
    " grid.coord_to_id(1, 2, 3)  // => 5\n"
    " grid.coord_to_id(2, 1, 3)  // => 7\n"
    " ```\n"
).
-spec coord_to_id(integer(), integer(), integer()) -> integer().
coord_to_id(Row, Col, Cols) ->
    (Row * Cols) + Col.

-file("src/yog/builder/grid.gleam", 148).
?DOC(
    " Creates a graph from a 2D list using a custom movement topology.\n"
    "\n"
    " The `topology` parameter is a list of `#(row_delta, col_delta)` offsets\n"
    " that define which neighbors each cell can reach. Use the built-in\n"
    " presets — `rook()`, `bishop()`, `queen()`, `knight()` — or define\n"
    " your own.\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " // 8-way movement (queen topology) on a maze\n"
    " let maze = [[\".\", \"#\", \".\"], [\".\", \".\", \".\"], [\"#\", \".\", \".\"]]\n"
    "\n"
    " let g = grid.from_2d_list_with_topology(\n"
    "   maze,\n"
    "   model.Directed,\n"
    "   grid.queen(),\n"
    "   can_move: grid.avoiding(\"#\"),\n"
    " )\n"
    " ```\n"
    "\n"
    " ```gleam\n"
    " // Knight jumps on a chessboard\n"
    " let board = [\n"
    "   [0, 0, 0, 0, 0],\n"
    "   [0, 0, 0, 0, 0],\n"
    "   [0, 0, 0, 0, 0],\n"
    "   [0, 0, 0, 0, 0],\n"
    "   [0, 0, 0, 0, 0],\n"
    " ]\n"
    "\n"
    " let g = grid.from_2d_list_with_topology(\n"
    "   board,\n"
    "   model.Directed,\n"
    "   grid.knight(),\n"
    "   can_move: grid.always(),\n"
    " )\n"
    " ```\n"
    "\n"
    " **Time Complexity:** O(rows × cols × |topology|)\n"
).
-spec from_2d_list_with_topology(
    list(list(HTB)),
    yog@model:graph_type(),
    list({integer(), integer()}),
    fun((HTB, HTB) -> boolean())
) -> grid(HTB, 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 = Row@2 + D_row,
                        N_col = Col@1 + D_col,
                        case (((N_row >= 0) andalso (N_row < Rows)) andalso (N_col
                        >= 0))
                        andalso (N_col < Cols) of
                            false ->
                                Acc_g;

                            true ->
                                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/grid"/utf8>>,
                                                    function => <<"from_2d_list_with_topology"/utf8>>,
                                                    line => 192,
                                                    value => _assert_fail,
                                                    start => 5533,
                                                    'end' => 5597,
                                                    pattern_start => 5544,
                                                    pattern_end => 5555}
                                            )
                                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/grid"/utf8>>,
                                                            function => <<"from_2d_list_with_topology"/utf8>>,
                                                            line => 195,
                                                            value => _assert_fail@1,
                                                            start => 5674,
                                                            'end' => 5763,
                                                            pattern_start => 5685,
                                                            pattern_end => 5690}
                                                    )
                                        end,
                                        G@3;

                                    false ->
                                        Acc_g
                                end
                        end
                    end
                )
            end
        )
    end,
    {grid, Graph_with_edges, Rows, Cols}.

-file("src/yog/builder/grid.gleam", 100).
?DOC(
    " Creates a graph from a 2D list using 4-directional (rook) movement.\n"
    "\n"
    " Each cell becomes a node, and edges are added between adjacent cells\n"
    " (up/down/left/right) if the `can_move` predicate returns True.\n"
    " This is equivalent to `from_2d_list_with_topology` with `rook()`.\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " let heightmap = [[1, 2, 3], [2, 3, 4], [3, 4, 5]]\n"
    "\n"
    " let g = grid.from_2d_list(\n"
    "   heightmap,\n"
    "   model.Directed,\n"
    "   can_move: fn(from, to) { to - from <= 1 },\n"
    " )\n"
    " ```\n"
    "\n"
    " **Time Complexity:** O(rows × cols)\n"
).
-spec from_2d_list(
    list(list(HSW)),
    yog@model:graph_type(),
    fun((HSW, HSW) -> boolean())
) -> grid(HSW, 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/grid.gleam", 305).
?DOC(
    " Converts a node ID back to grid coordinates (row, col).\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " grid.id_to_coord(0, 3)  // => #(0, 0)\n"
    " grid.id_to_coord(5, 3)  // => #(1, 2)\n"
    " grid.id_to_coord(7, 3)  // => #(2, 1)\n"
    " ```\n"
).
-spec id_to_coord(integer(), integer()) -> {integer(), integer()}.
id_to_coord(Id, Cols) ->
    {case Cols of
            0 -> 0;
            Gleam@denominator -> Id div Gleam@denominator
        end, case Cols of
            0 -> 0;
            Gleam@denominator@1 -> Id rem Gleam@denominator@1
        end}.

-file("src/yog/builder/grid.gleam", 325).
?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 grid.get_cell(grid, 1, 2) {\n"
    "   Ok(cell) -> // Use cell data\n"
    "   Error(_) -> // Out of bounds\n"
    " }\n"
    " ```\n"
).
-spec get_cell(grid(HTL, any()), integer(), integer()) -> {ok, HTL} |
    {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/grid.gleam", 349).
?DOC(
    " Converts the grid to a standard `Graph`.\n"
    "\n"
    " The resulting graph can be used with all yog algorithms.\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " let graph = grid.to_graph(grid)\n"
    " // Now use with pathfinding, traversal, etc.\n"
    " ```\n"
).
-spec to_graph(grid(HTR, HTS)) -> yog@model:graph(HTR, HTS).
to_graph(Grid) ->
    erlang:element(2, Grid).

-file("src/yog/builder/grid.gleam", 371).
?DOC(
    " Calculates the Manhattan distance between two node IDs.\n"
    "\n"
    " This is useful as a heuristic for A* pathfinding on grids.\n"
    " Manhattan distance is the sum of absolute differences in coordinates:\n"
    " |x1 - x2| + |y1 - y2|\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " let start = grid.coord_to_id(0, 0, 10)\n"
    " let goal = grid.coord_to_id(3, 4, 10)\n"
    " let distance = grid.manhattan_distance(start, goal, 10)\n"
    " // => 7 (3 + 4)\n"
    " ```\n"
).
-spec manhattan_distance(integer(), integer(), integer()) -> integer().
manhattan_distance(From_id, To_id, Cols) ->
    {From_row, From_col} = id_to_coord(From_id, Cols),
    {To_row, To_col} = id_to_coord(To_id, Cols),
    gleam@int:absolute_value(From_row - To_row) + gleam@int:absolute_value(
        From_col - To_col
    ).

-file("src/yog/builder/grid.gleam", 395).
?DOC(
    " Calculates the Chebyshev distance between two node IDs.\n"
    "\n"
    " This is the optimal heuristic for A* pathfinding on grids with 8-way\n"
    " (queen) movement, where diagonal moves have the same cost as orthogonal moves.\n"
    " Chebyshev distance is the maximum of absolute differences in coordinates:\n"
    " max(|x1 - x2|, |y1 - y2|)\n"
    "\n"
    " **Use this for:** `queen()` topology, or any 8-directional movement\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " let start = grid.coord_to_id(0, 0, 10)\n"
    " let goal = grid.coord_to_id(3, 4, 10)\n"
    " let distance = grid.chebyshev_distance(start, goal, 10)\n"
    " // => 4 (max of 3 and 4)\n"
    " ```\n"
).
-spec chebyshev_distance(integer(), integer(), integer()) -> integer().
chebyshev_distance(From_id, To_id, Cols) ->
    {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),
    gleam@int:max(Row_diff, Col_diff).

-file("src/yog/builder/grid.gleam", 423).
?DOC(
    " Calculates the Octile distance between two node IDs.\n"
    "\n"
    " This is the optimal heuristic for A* pathfinding on grids with 8-way\n"
    " movement where diagonal moves cost √2 (approximately 1.414) and orthogonal\n"
    " moves cost 1. This represents true Euclidean-style movement on a grid.\n"
    "\n"
    " The formula is: min(dx, dy) × √2 + |dx - dy|\n"
    "\n"
    " **Use this for:** Weighted 8-directional movement with realistic diagonal costs\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " let start = grid.coord_to_id(0, 0, 10)\n"
    " let goal = grid.coord_to_id(3, 4, 10)\n"
    " let distance = grid.octile_distance(start, goal, 10)\n"
    " // => 5.242... (3 × √2 + 1)\n"
    " ```\n"
).
-spec octile_distance(integer(), integer(), integer()) -> float().
octile_distance(From_id, To_id, Cols) ->
    {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_d = gleam@int:min(Row_diff, Col_diff),
    Max_d = gleam@int:max(Row_diff, Col_diff),
    (erlang:float(Min_d) * 1.414213562373095) + erlang:float(Max_d - Min_d).

-file("src/yog/builder/grid.gleam", 454).
?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 grid.find_node(grid, fn(cell) { cell == \"S\" }) {\n"
    "   Ok(start_id) -> // Use start_id\n"
    "   Error(_) -> // Not found\n"
    " }\n"
    " ```\n"
).
-spec find_node(grid(HTX, any()), fun((HTX) -> 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/grid.gleam", 494).
?DOC(
    " Allows movement between any cells except the specified wall value.\n"
    "\n"
    " Useful for maze-style grids where `\"#\"` or similar marks a wall.\n"
    " Both the source and destination cells must not be the wall value.\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " // Maze where \"#\" is impassable\n"
    " let maze = [\n"
    "   [\".\", \"#\", \".\"],\n"
    "   [\".\", \".\", \".\"],\n"
    "   [\"#\", \"#\", \".\"],\n"
    " ]\n"
    "\n"
    " let g = grid.from_2d_list(maze, model.Directed, can_move: grid.avoiding(\"#\"))\n"
    " // Edges only connect non-wall cells\n"
    " ```\n"
).
-spec avoiding(HUD) -> fun((HUD, HUD) -> boolean()).
avoiding(Wall_value) ->
    fun(From, To) -> (From /= Wall_value) andalso (To /= Wall_value) end.

-file("src/yog/builder/grid.gleam", 517).
?DOC(
    " Allows movement only between cells matching the specified value.\n"
    "\n"
    " The inverse of `avoiding` — instead of blacklisting one value,\n"
    " this whitelists exactly one value. Both the source and destination\n"
    " cells must match the valid value.\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " // Grid with varied terrain — only \".\" is walkable\n"
    " let terrain = [\n"
    "   [\".\", \"~\", \"^\"],\n"
    "   [\".\", \".\", \"^\"],\n"
    "   [\"~\", \".\", \".\"],\n"
    " ]\n"
    "\n"
    " let g = grid.from_2d_list(terrain, model.Directed, can_move: grid.walkable(\".\"))\n"
    " // Only \".\" → \".\" edges exist\n"
    " ```\n"
).
-spec walkable(HUE) -> fun((HUE, HUE) -> boolean()).
walkable(Valid_value) ->
    fun(From, To) -> (From =:= Valid_value) andalso (To =:= Valid_value) end.

-file("src/yog/builder/grid.gleam", 535).
?DOC(
    " Always allows movement between adjacent cells.\n"
    "\n"
    " Every 4-directional neighbor pair gets an edge regardless of cell data.\n"
    " Useful for fully connected grids or when the cell data is purely\n"
    " informational (e.g., storing coordinates or labels).\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " let labels = [[\"A\", \"B\"], [\"C\", \"D\"]]\n"
    "\n"
    " let g = grid.from_2d_list(labels, model.Undirected, can_move: grid.always())\n"
    " // All adjacent cells are connected\n"
    " ```\n"
).
-spec always() -> fun((HUF, HUF) -> boolean()).
always() ->
    fun(_, _) -> true end.

-file("src/yog/builder/grid.gleam", 556).
?DOC(
    " Allows movement only between cells matching any of the specified values.\n"
    "\n"
    " A multi-value version of `walkable`. Both the source and destination\n"
    " cells must be included in the valid values list.\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " // Grid where both \".\" and \"P\" are walkable\n"
    " let terrain = [\n"
    "   [\".\", \"P\", \"#\"],\n"
    "   [\"#\", \".\", \".\"],\n"
    " ]\n"
    "\n"
    " let g = grid.from_2d_list(terrain, model.Directed, can_move: grid.including([\".\", \"P\"]))\n"
    " // Edges exist between any combination of \".\" and \"P\"\n"
    " ```\n"
).
-spec including(list(HUG)) -> fun((HUG, HUG) -> boolean()).
including(Valid_values) ->
    fun(From, To) ->
        gleam@list:contains(Valid_values, From) andalso gleam@list:contains(
            Valid_values,
            To
        )
    end.