yog

-module(yog@pathfinding@a_star).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch, inline]).
-define(FILEPATH, "src/yog/pathfinding/a_star.gleam").
-export([a_star/7, implicit_a_star_by/8, implicit_a_star/7, a_star_int/4, a_star_float/4]).

-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* (A-Star)](https://en.wikipedia.org/wiki/A*_search_algorithm) search algorithm \n"
    " for optimal pathfinding with heuristic guidance.\n"
    "\n"
    " A* is an informed search algorithm that finds the shortest path from a start node\n"
    " to a goal node using a heuristic function to guide exploration. It combines the\n"
    " completeness of Dijkstra's algorithm with the efficiency of greedy best-first search.\n"
    "\n"
    " ## Algorithm\n"
    "\n"
    " | Algorithm | Function | Complexity | Best For |\n"
    " |-----------|----------|------------|----------|\n"
    " | [A* Search](https://en.wikipedia.org/wiki/A*_search_algorithm) | `a_star/7` | O((V + E) log V) | Pathfinding with good heuristics |\n"
    " | Implicit A* | `implicit_a_star/7` | O((V + E) log V) | Large/infinite graphs generated on-demand |\n"
    "\n"
    " ## Key Concepts\n"
    "\n"
    " - **Evaluation Function**: f(n) = g(n) + h(n)\n"
    "   - g(n): Actual cost from start to node n\n"
    "   - h(n): Heuristic estimate from n to goal\n"
    "   - f(n): Estimated total cost through n\n"
    " - **Admissible Heuristic**: h(n) ≤ actual cost (never overestimates)\n"
    " - **Consistent Heuristic**: h(n) ≤ cost(n→n') + h(n') (triangle inequality)\n"
    "\n"
    " ## When to Use A*\n"
    "\n"
    " **Use A* when:**\n"
    " - You have a specific goal node (not single-source to all)\n"
    " - You can provide a good heuristic estimate\n"
    " - The heuristic is admissible (underestimates)\n"
    "\n"
    " **Use Dijkstra when:**\n"
    " - No good heuristic available (h(n) = 0 reduces A* to Dijkstra)\n"
    " - You need shortest paths to all nodes from a source\n"
    "\n"
    " ## Heuristic Examples\n"
    "\n"
    " | Domain | Heuristic | Admissible? |\n"
    " |--------|-----------|-------------|\n"
    " | Grid (4-way) | Manhattan distance | Yes |\n"
    " | Grid (8-way) | Chebyshev distance | Yes |\n"
    " | Geospatial | Haversine/great-circle | Yes |\n"
    " | Road networks | Precomputed landmarks | Yes |\n"
    "\n"
    " ## Use Cases\n"
    "\n"
    " - **Video games**: NPC pathfinding on game maps\n"
    " - **GPS navigation**: Route planning with distance estimates\n"
    " - **Robotics**: Motion planning with obstacle avoidance\n"
    " - **Puzzle solving**: Sliding puzzles, mazes, labyrinths\n"
    "\n"
    " ## References\n"
    "\n"
    " - [Wikipedia: A* Search Algorithm](https://en.wikipedia.org/wiki/A*_search_algorithm)\n"
    " - [Red Blob Games: A* Implementation](https://www.redblobgames.com/pathfinding/a-star/introduction.html)\n"
    " - [Stanford CS161: A* Lecture](https://web.stanford.edu/class/cs161/lectures/lecture20.pdf)\n"
    " - [CP-Algorithms: A*](https://cp-algorithms.com/graph/A-star.html)\n"
).

-file("src/yog/pathfinding/a_star.gleam", 104).
-spec do_a_star(
    yog@model:graph(any(), JKZ),
    integer(),
    yog@internal@pairing_heap:heap({JIR, JIR, list(integer())}),
    gleam@dict:dict(integer(), JIR),
    fun((JIR, JKZ) -> JIR),
    fun((JIR, JIR) -> gleam@order:order()),
    fun((integer(), integer()) -> JKZ)
) -> gleam@option:option({JIR, list(integer())}).
do_a_star(Graph, Goal, Frontier, Visited, Add, Compare, H) ->
    case yog@internal@priority_queue:pop(Frontier) of
        {ok, {{_, Dist, [Current | _] = Path}, _}} when Current =:= Goal ->
            {some, {Dist, Path}};

        {ok, {{_, Dist@1, [Current@1 | _] = Path@1}, Rest_frontier}} ->
            case yog@internal@util:should_explore_node(
                Visited,
                Current@1,
                Dist@1,
                Compare
            ) of
                false ->
                    do_a_star(
                        Graph,
                        Goal,
                        Rest_frontier,
                        Visited,
                        Add,
                        Compare,
                        H
                    );

                true ->
                    New_visited = gleam@dict:insert(Visited, Current@1, Dist@1),
                    Successors = yog@model:successors(Graph, Current@1),
                    Next_frontier = begin
                        gleam@list:fold(
                            Successors,
                            Rest_frontier,
                            fun(Acc_h, Neighbor) ->
                                {Next_id, Weight} = Neighbor,
                                Next_dist = Add(Dist@1, Weight),
                                case yog@internal@util:should_explore_node(
                                    New_visited,
                                    Next_id,
                                    Next_dist,
                                    Compare
                                ) of
                                    true ->
                                        F_score = Add(
                                            Next_dist,
                                            H(Next_id, Goal)
                                        ),
                                        yog@internal@priority_queue:push(
                                            Acc_h,
                                            {F_score,
                                                Next_dist,
                                                [Next_id | Path@1]}
                                        );

                                    false ->
                                        Acc_h
                                end
                            end
                        )
                    end,
                    do_a_star(
                        Graph,
                        Goal,
                        Next_frontier,
                        New_visited,
                        Add,
                        Compare,
                        H
                    )
            end;

        _ ->
            none
    end.

-file("src/yog/pathfinding/a_star.gleam", 83).
?DOC(
    " Finds the shortest path using A* search with a heuristic function.\n"
    "\n"
    " A* is more efficient than Dijkstra when you have a good heuristic estimate\n"
    " of the remaining distance to the goal.\n"
    "\n"
    " **Time Complexity:** O((V + E) log V)\n"
    "\n"
    " ## Parameters\n"
    "\n"
    " - `zero`: The identity element for addition (e.g., 0 for integers)\n"
    " - `add`: Function to add two weights\n"
    " - `compare`: Function to compare two weights\n"
    " - `heuristic`: A function that estimates distance from any node to the goal.\n"
    "   Must be admissible (h(n) ≤ actual distance).\n"
).
-spec a_star(
    yog@model:graph(any(), JIF),
    integer(),
    integer(),
    JIF,
    fun((JIF, JIF) -> JIF),
    fun((JIF, JIF) -> gleam@order:order()),
    fun((integer(), integer()) -> JIF)
) -> gleam@option:option(yog@pathfinding@path:path(JIF)).
a_star(Graph, Start, Goal, Zero, Add, Compare, H) ->
    Initial_f = H(Start, Goal),
    Frontier = begin
        _pipe = yog@internal@priority_queue:new(
            fun(A, B) ->
                yog@internal@util:compare_a_star_frontier(A, B, Compare)
            end
        ),
        yog@internal@priority_queue:push(_pipe, {Initial_f, Zero, [Start]})
    end,
    _pipe@1 = do_a_star(Graph, Goal, Frontier, maps:new(), Add, Compare, H),
    gleam@option:map(
        _pipe@1,
        fun(Res) ->
            {Dist, Path} = Res,
            {path, lists:reverse(Path), Dist}
        end
    ).

-file("src/yog/pathfinding/a_star.gleam", 216).
-spec do_implicit_a_star_by(
    yog@internal@pairing_heap:heap({JJD, JJD, JJE}),
    gleam@dict:dict(JJG, JJD),
    fun((JJE) -> list({JJE, JJD})),
    fun((JJE) -> JJG),
    fun((JJE) -> boolean()),
    fun((JJE) -> JJD),
    fun((JJD, JJD) -> JJD),
    fun((JJD, JJD) -> gleam@order:order())
) -> gleam@option:option(JJD).
do_implicit_a_star_by(
    Frontier,
    Distances,
    Successors,
    Key_fn,
    Is_goal,
    H,
    Add,
    Compare
) ->
    case yog@internal@priority_queue:pop(Frontier) of
        {ok, {{_, Dist, Current}, Rest_frontier}} ->
            case Is_goal(Current) of
                true ->
                    {some, Dist};

                false ->
                    Current_key = Key_fn(Current),
                    case yog@internal@util:should_explore_node(
                        Distances,
                        Current_key,
                        Dist,
                        Compare
                    ) of
                        false ->
                            do_implicit_a_star_by(
                                Rest_frontier,
                                Distances,
                                Successors,
                                Key_fn,
                                Is_goal,
                                H,
                                Add,
                                Compare
                            );

                        true ->
                            New_distances = gleam@dict:insert(
                                Distances,
                                Current_key,
                                Dist
                            ),
                            Next_frontier = begin
                                gleam@list:fold(
                                    Successors(Current),
                                    Rest_frontier,
                                    fun(Frontier_acc, Neighbor) ->
                                        {Next_state, Edge_cost} = Neighbor,
                                        Next_dist = Add(Dist, Edge_cost),
                                        Next_key = Key_fn(Next_state),
                                        case yog@internal@util:should_explore_node(
                                            New_distances,
                                            Next_key,
                                            Next_dist,
                                            Compare
                                        ) of
                                            true ->
                                                F_score = Add(
                                                    Next_dist,
                                                    H(Next_state)
                                                ),
                                                yog@internal@priority_queue:push(
                                                    Frontier_acc,
                                                    {F_score,
                                                        Next_dist,
                                                        Next_state}
                                                );

                                            false ->
                                                Frontier_acc
                                        end
                                    end
                                )
                            end,
                            do_implicit_a_star_by(
                                Next_frontier,
                                New_distances,
                                Successors,
                                Key_fn,
                                Is_goal,
                                H,
                                Add,
                                Compare
                            )
                    end
            end;

        _ ->
            none
    end.

-file("src/yog/pathfinding/a_star.gleam", 187).
?DOC(
    " Like `implicit_a_star`, but deduplicates visited states by a custom key.\n"
    "\n"
    " Essential when your state carries extra data beyond what defines identity.\n"
    " The `visited_by` function extracts the deduplication key from each state.\n"
    "\n"
    " **Time Complexity:** O((V + E) log V) where V and E are measured in unique *keys*\n"
).
-spec implicit_a_star_by(
    JIY,
    fun((JIY) -> list({JIY, JIZ})),
    fun((JIY) -> any()),
    fun((JIY) -> boolean()),
    fun((JIY) -> JIZ),
    JIZ,
    fun((JIZ, JIZ) -> JIZ),
    fun((JIZ, JIZ) -> gleam@order:order())
) -> gleam@option:option(JIZ).
implicit_a_star_by(Start, Successors, Key_fn, Is_goal, H, Zero, Add, Compare) ->
    Initial_f = H(Start),
    Frontier = begin
        _pipe = yog@internal@priority_queue:new(
            fun(A, B) -> Compare(erlang:element(1, A), erlang:element(1, B)) end
        ),
        yog@internal@priority_queue:push(_pipe, {Initial_f, Zero, Start})
    end,
    do_implicit_a_star_by(
        Frontier,
        maps:new(),
        Successors,
        Key_fn,
        Is_goal,
        H,
        Add,
        Compare
    ).

-file("src/yog/pathfinding/a_star.gleam", 160).
?DOC(
    " Finds the shortest path in an implicit graph using A* search with a heuristic.\n"
    "\n"
    " **Time Complexity:** O((V + E) log V)\n"
    "\n"
    " ## Parameters\n"
    "\n"
    " - `zero`: The identity element for addition (e.g., 0 for integers)\n"
    " - `add`: Function to add two costs\n"
    " - `compare`: Function to compare two costs\n"
    " - `heuristic`: Function that estimates remaining cost from any state to goal.\n"
    "   Must be admissible.\n"
).
-spec implicit_a_star(
    JIU,
    fun((JIU) -> list({JIU, JIV})),
    fun((JIU) -> boolean()),
    fun((JIU) -> JIV),
    JIV,
    fun((JIV, JIV) -> JIV),
    fun((JIV, JIV) -> gleam@order:order())
) -> gleam@option:option(JIV).
implicit_a_star(Start, Successors, Is_goal, H, Zero, Add, Compare) ->
    implicit_a_star_by(
        Start,
        Successors,
        fun(S) -> S end,
        Is_goal,
        H,
        Zero,
        Add,
        Compare
    ).

-file("src/yog/pathfinding/a_star.gleam", 321).
?DOC(
    " Finds the shortest path using A* with **integer weights**.\n"
    "\n"
    " This is a convenience wrapper around `a_star` that uses:\n"
    " - `0` as the zero element\n"
    " - `int.add` for addition\n"
    " - `int.compare` for comparison\n"
    "\n"
    " You still need to provide a heuristic function.\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " // Grid distance heuristic (Manhattan distance)\n"
    " let heuristic = fn(from, to) {\n"
    "   let dx = int.absolute_value(from.x - to.x)\n"
    "   let dy = int.absolute_value(from.y - to.y)\n"
    "   dx + dy\n"
    " }\n"
    "\n"
    " a_star.a_star_int(graph, from: start, to: goal, with_heuristic: heuristic)\n"
    " ```\n"
).
-spec a_star_int(
    yog@model:graph(any(), integer()),
    integer(),
    integer(),
    fun((integer(), integer()) -> integer())
) -> gleam@option:option(yog@pathfinding@path:path(integer())).
a_star_int(Graph, Start, Goal, H) ->
    a_star(
        Graph,
        Start,
        Goal,
        0,
        fun gleam@int:add/2,
        fun gleam@int:compare/2,
        H
    ).

-file("src/yog/pathfinding/a_star.gleam", 346).
?DOC(
    " Finds the shortest path using A* with **float weights**.\n"
    "\n"
    " This is a convenience wrapper around `a_star` that uses:\n"
    " - `0.0` as the zero element\n"
    " - `float.add` for addition\n"
    " - `float.compare` for comparison\n"
    "\n"
    " You still need to provide a heuristic function.\n"
).
-spec a_star_float(
    yog@model:graph(any(), float()),
    integer(),
    integer(),
    fun((integer(), integer()) -> float())
) -> gleam@option:option(yog@pathfinding@path:path(float())).
a_star_float(Graph, Start, Goal, H) ->
    a_star(
        Graph,
        Start,
        Goal,
        +0.0,
        fun gleam@float:add/2,
        fun gleam@float:compare/2,
        H
    ).