gwg_pathfinding

-module(gwg@pathfinding).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch, inline]).
-define(FILEPATH, "src/gwg/pathfinding.gleam").
-export([astar/3, flowfield/2]).
-export_type([action/2, astarstate/2, flowfieldstate/1]).

-if(?OTP_RELEASE >= 27).
-define(MODULEDOC(Str), -moduledoc(Str)).
-define(DOC(Str), -doc(Str)).
-else.
-define(MODULEDOC(Str), -compile([])).
-define(DOC(Str), -compile([])).
-endif.

-type action(DQR, DQS) :: {action, DQR, DQS, float()}.

-type astarstate(DQT, DQU) :: {astarstate, DQT, DQU, float(), float()}.

-type flowfieldstate(DQV) :: {flowfieldstate, DQV, float(), float()}.

-file("src/gwg/pathfinding.gleam", 206).
-spec lowest_f_score_state(
    gleam@set:set(DRW),
    gleam@dict:dict(DRW, astarstate(DRW, any()))
) -> {ok, DRW} | {error, nil}.
lowest_f_score_state(Queue, Flowfield) ->
    _pipe = Queue,
    _pipe@1 = gleam@set:to_list(_pipe),
    gleam@list:max(
        _pipe@1,
        fun(A, B) ->
            case {gleam_stdlib:map_get(Flowfield, A),
                gleam_stdlib:map_get(Flowfield, B)} of
                {{ok, A@1}, {ok, B@1}} ->
                    gleam@float:compare(
                        erlang:element(5, B@1),
                        erlang:element(5, A@1)
                    );

                {{ok, A@2}, {error, nil}} ->
                    gleam@float:compare(+0.0, erlang:element(5, A@2));

                {{error, nil}, {ok, B@2}} ->
                    gleam@float:compare(erlang:element(5, B@2), +0.0);

                {{error, nil}, {error, nil}} ->
                    eq
            end
        end
    ).

-file("src/gwg/pathfinding.gleam", 222).
-spec astar_actions_folder(
    list(action(DSF, DSG)),
    DSG,
    float(),
    fun((DSG) -> float()),
    gleam@dict:dict(DSG, astarstate(DSG, DSF))
) -> gleam@dict:dict(DSG, astarstate(DSG, DSF)).
astar_actions_folder(
    Actions,
    From_state,
    From_g_score,
    Heuristic_fun,
    Flowfield
) ->
    _pipe = Actions,
    gleam@list:fold(
        _pipe,
        maps:new(),
        fun(Acc, Action) ->
            G_score = From_g_score + erlang:element(4, Action),
            case begin
                _pipe@1 = Flowfield,
                _pipe@2 = maps:merge(_pipe@1, Acc),
                gleam_stdlib:map_get(_pipe@2, erlang:element(3, Action))
            end of
                {ok, Old} when erlang:element(4, Old) =< G_score ->
                    Acc;

                _ ->
                    F_score = G_score + Heuristic_fun(erlang:element(3, Action)),
                    _pipe@3 = {astarstate,
                        From_state,
                        erlang:element(2, Action),
                        G_score,
                        F_score},
                    gleam@dict:insert(Acc, erlang:element(3, Action), _pipe@3)
            end
        end
    ).

-file("src/gwg/pathfinding.gleam", 244).
-spec closest_state(gleam@dict:dict(DSS, astarstate(DSS, any()))) -> {ok, DSS} |
    {error, nil}.
closest_state(Flowfield) ->
    _pipe = Flowfield,
    _pipe@1 = maps:to_list(_pipe),
    _pipe@2 = gleam@list:max(
        _pipe@1,
        fun(A, B) ->
            {_, A@1} = A,
            {_, B@1} = B,
            gleam@float:compare(
                erlang:element(5, B@1) - erlang:element(4, B@1),
                erlang:element(5, A@1) - erlang:element(4, A@1)
            )
        end
    ),
    gleam@result:map(_pipe@2, fun gleam@pair:first/1).

-file("src/gwg/pathfinding.gleam", 264).
-spec do_reconstruct_actions(
    DTH,
    gleam@dict:dict(DTH, astarstate(DTH, DTI)),
    list(DTI)
) -> list(DTI).
do_reconstruct_actions(State, Flowfield, Actions) ->
    case begin
        _pipe = Flowfield,
        gleam_stdlib:map_get(_pipe, State)
    end of
        {ok, {astarstate, From_state, Action, _, _}} ->
            do_reconstruct_actions(From_state, Flowfield, [Action | Actions]);

        {error, nil} ->
            Actions
    end.

-file("src/gwg/pathfinding.gleam", 257).
-spec reconstruct_actions(DTA, gleam@dict:dict(DTA, astarstate(DTA, DTB))) -> list(DTB).
reconstruct_actions(State, Flowfield) ->
    do_reconstruct_actions(State, Flowfield, []).

-file("src/gwg/pathfinding.gleam", 169).
-spec do_astar(
    DRJ,
    fun((DRJ, float()) -> list(action(DRK, DRJ))),
    fun((DRJ) -> float()),
    gleam@set:set(DRJ),
    gleam@dict:dict(DRJ, astarstate(DRJ, DRK))
) -> {ok, list(DRK)} | {error, list(DRK)}.
do_astar(Init_state, Successor_fun, Heuristic_fun, Queue, Flowfield) ->
    case lowest_f_score_state(Queue, Flowfield) of
        {ok, State} ->
            {G_score@1, F_score@1} = case begin
                _pipe = Flowfield,
                gleam_stdlib:map_get(_pipe, State)
            end of
                {ok, {astarstate, _, _, G_score, F_score}} ->
                    {G_score, F_score};

                {error, nil} ->
                    {+0.0, 1.0}
            end,
            gleam@bool:lazy_guard(
                (F_score@1 - G_score@1) =< +0.0,
                fun() ->
                    {ok,
                        begin
                            _pipe@1 = State,
                            reconstruct_actions(
                                _pipe@1,
                                begin
                                    _pipe@2 = Flowfield,
                                    gleam@dict:delete(_pipe@2, Init_state)
                                end
                            )
                        end}
                end,
                fun() ->
                    Queue@1 = begin
                        _pipe@3 = Queue,
                        gleam@set:delete(_pipe@3, State)
                    end,
                    Actions = begin
                        _pipe@4 = Successor_fun(State, G_score@1),
                        astar_actions_folder(
                            _pipe@4,
                            State,
                            G_score@1,
                            Heuristic_fun,
                            Flowfield
                        )
                    end,
                    Queue@2 = begin
                        _pipe@5 = Actions,
                        _pipe@6 = maps:keys(_pipe@5),
                        _pipe@7 = gleam@set:from_list(_pipe@6),
                        gleam@set:union(_pipe@7, Queue@1)
                    end,
                    Flowfield@1 = begin
                        _pipe@8 = Flowfield,
                        maps:merge(_pipe@8, Actions)
                    end,
                    do_astar(
                        Init_state,
                        Successor_fun,
                        Heuristic_fun,
                        Queue@2,
                        Flowfield@1
                    )
                end
            );

        {error, nil} ->
            _pipe@9 = closest_state(Flowfield),
            _pipe@10 = gleam@result:unwrap(_pipe@9, Init_state),
            _pipe@12 = reconstruct_actions(
                _pipe@10,
                begin
                    _pipe@11 = Flowfield,
                    gleam@dict:delete(_pipe@11, Init_state)
                end
            ),
            {error, _pipe@12}
    end.

-file("src/gwg/pathfinding.gleam", 155).
?DOC(
    " Performs an A* search to find the optimal path from an initial `state`.\n"
    "\n"
    " This function returns a the sequence of actions to reach the goal when the\n"
    " `heuristic_fun` returns 0.0 (or less), signaling the goal has been\n"
    " reached.\n"
    "\n"
    " If the goal can not be reach, it will returns the sequence of actions to\n"
    " the \"closest\" state reached.\n"
    "\n"
    " ## Examples\n"
    "\n"
    " ```gleam\n"
    " let actions = [\n"
    "   Vec2(-1, 0),\n"
    "   Vec2(1, 0),\n"
    "   Vec2(0, -1),\n"
    "   Vec2(0, 1),\n"
    "   Vec2(-1, -1),\n"
    "   Vec2(-1, 1),\n"
    "   Vec2(1, -1),\n"
    "   Vec2(1, 1),\n"
    " ]\n"
    "\n"
    " let world0 =\n"
    "   vec2i_dict.from_string(\n"
    "     \"\"\n"
    "     <> \"###########\\n\"\n"
    "     <> \"#   #     #\\n\"\n"
    "     <> \"#   #     #\\n\"\n"
    "     <> \"#   #     #\\n\"\n"
    "     <> \"#   ## ####\\n\"\n"
    "     <> \"#   #     #\\n\"\n"
    "     <> \"#   #     #\\n\"\n"
    "     <> \"## ##### ##\\n\"\n"
    "     <> \"#   # #   #\\n\"\n"
    "     <> \"#         #\\n\"\n"
    "     <> \"###########\\n\",\n"
    "   )\n"
    "\n"
    " let world1 =\n"
    "   vec2i_dict.from_string(\n"
    "     \"\"\n"
    "     <> \"###########\\n\"\n"
    "     <> \"#   #     #\\n\"\n"
    "     <> \"#   #     #\\n\"\n"
    "     <> \"#   #     #\\n\"\n"
    "     <> \"#   ##x####\\n\"\n"
    "     <> \"#   #     #\\n\"\n"
    "     <> \"#   #     #\\n\"\n"
    "     <> \"## ##### ##\\n\"\n"
    "     <> \"#   # #   #\\n\"\n"
    "     <> \"#         #\\n\"\n"
    "     <> \"###########\\n\",\n"
    "   )\n"
    "\n"
    " let init = Vec2(2, 2)\n"
    " let target = Vec2(7, 2)\n"
    "\n"
    " fn successor(\n"
    "   state: Vec2i,\n"
    "   g_score: Float,\n"
    "   world: Dict(Vec2i, String),\n"
    " ) -> List(Action(Vec2i, Vec2i)) {\n"
    "   actions\n"
    "   |> list.filter_map(fn(action) {\n"
    "     let weight = action |> vec2i.length\n"
    "\n"
    "     use <- bool.guard(g_score +. weight >. 32.0, Error(Nil))\n"
    "\n"
    "     let state = state |> vec2i.add(action)\n"
    "\n"
    "     case world |> dict.has_key(state) {\n"
    "       True -> Error(Nil)\n"
    "       False -> Ok(Action(action:, state:, weight:))\n"
    "     }\n"
    "   })\n"
    " }\n"
    "\n"
    " fn heuristic(state: Vec2i) -> Float {\n"
    "   vec2i.distance(state, target)\n"
    " }\n"
    "\n"
    " astar(\n"
    "   init:,\n"
    "   successor: fn(state, g_score) {\n"
    "     successor(state, g_score, world0)\n"
    "   },\n"
    "   heuristic:,\n"
    " )\n"
    " // Ok:\n"
    " // ###########\n"
    " // #   #     #\n"
    " // # @ #  *  #\n"
    " // # ↓ # ↗   #\n"
    " // # ↓ ##↑####\n"
    " // # ↓ #  ↖  #\n"
    " // # ↓ #   ↖ #\n"
    " // ##↘#####↑##\n"
    " // #  ↘# #↗  #\n"
    " // #   →→↗   #\n"
    " // ###########\n"
    "\n"
    " astar(\n"
    "   init:,\n"
    "   successor: fn(state, g_score) {\n"
    "     successor(state, g_score, world1)\n"
    "   },\n"
    "   heuristic:,\n"
    " )\n"
    " // Error:\n"
    " // ###########\n"
    " // #   #     #\n"
    " // # @ #  *  #\n"
    " // # ↓ #     #\n"
    " // # ↓ ##x####\n"
    " // # ↓ #     #\n"
    " // # ↓ #   ↖ #\n"
    " // ##↘#####↑##\n"
    " // #  ↘# #↗  #\n"
    " // #   →→↗   #\n"
    " // ###########\n"
    " ```\n"
).
-spec astar(
    DRB,
    fun((DRB, float()) -> list(action(DRC, DRB))),
    fun((DRB) -> float())
) -> {ok, list(DRC)} | {error, list(DRC)}.
astar(State, Successor_fun, Heuristic_fun) ->
    do_astar(
        State,
        Successor_fun,
        Heuristic_fun,
        gleam@set:from_list([State]),
        maps:new()
    ).

-file("src/gwg/pathfinding.gleam", 381).
-spec flowfield_actions_folder(
    list(action(DUF, DUG)),
    float(),
    gleam@dict:dict(DUG, flowfieldstate(DUF))
) -> gleam@dict:dict(DUG, flowfieldstate(DUF)).
flowfield_actions_folder(Actions, From_g_score, Flowfield) ->
    _pipe = Actions,
    gleam@list:fold(
        _pipe,
        maps:new(),
        fun(Acc, Action) ->
            G_score = From_g_score + erlang:element(4, Action),
            case begin
                _pipe@1 = Flowfield,
                _pipe@2 = maps:merge(_pipe@1, Acc),
                gleam_stdlib:map_get(_pipe@2, erlang:element(3, Action))
            end of
                {ok, Old} when (erlang:element(4, Old) < G_score) orelse ((erlang:element(
                    4,
                    Old
                ) =< G_score) andalso (erlang:element(3, Old) =< erlang:element(
                    4,
                    Action
                ))) ->
                    Acc;

                _ ->
                    _pipe@3 = {flowfieldstate,
                        erlang:element(2, Action),
                        erlang:element(4, Action),
                        G_score},
                    gleam@dict:insert(Acc, erlang:element(3, Action), _pipe@3)
            end
        end
    ).

-file("src/gwg/pathfinding.gleam", 348).
-spec do_flowfield(
    DTV,
    fun((DTV, float()) -> list(action(DTW, DTV))),
    list(DTV),
    gleam@dict:dict(DTV, flowfieldstate(DTW))
) -> gleam@dict:dict(DTV, DTW).
do_flowfield(Start_state, Successor_fun, Queue, Flowfield) ->
    case Queue of
        [State | Queue@1] ->
            G_score@1 = case begin
                _pipe = Flowfield,
                gleam_stdlib:map_get(_pipe, State)
            end of
                {ok, {flowfieldstate, _, _, G_score}} ->
                    G_score;

                {error, nil} ->
                    +0.0
            end,
            Actions = begin
                _pipe@1 = Successor_fun(State, G_score@1),
                flowfield_actions_folder(_pipe@1, G_score@1, Flowfield)
            end,
            Queue@2 = begin
                _pipe@2 = Actions,
                _pipe@4 = gleam@dict:drop(
                    _pipe@2,
                    begin
                        _pipe@3 = Flowfield,
                        maps:keys(_pipe@3)
                    end
                ),
                _pipe@5 = maps:keys(_pipe@4),
                lists:append(Queue@1, _pipe@5)
            end,
            Flowfield@1 = begin
                _pipe@6 = Flowfield,
                maps:merge(_pipe@6, Actions)
            end,
            do_flowfield(Start_state, Successor_fun, Queue@2, Flowfield@1);

        _ ->
            _pipe@7 = Flowfield,
            _pipe@8 = gleam@dict:delete(_pipe@7, Start_state),
            gleam@dict:map_values(
                _pipe@8,
                fun(_, Value) -> erlang:element(2, Value) end
            )
    end.

-file("src/gwg/pathfinding.gleam", 341).
?DOC(
    " Generates a flowfield (also known as vector field or Dijkstra map).\n"
    "\n"
    " ## Examples\n"
    "\n"
    " ```gleam\n"
    " let actions = [\n"
    "   Vec2(-1, 0),\n"
    "   Vec2(1, 0),\n"
    "   Vec2(0, -1),\n"
    "   Vec2(0, 1),\n"
    "   Vec2(-1, -1),\n"
    "   Vec2(-1, 1),\n"
    "   Vec2(1, -1),\n"
    "   Vec2(1, 1),\n"
    " ]\n"
    "\n"
    " let world =\n"
    "   vec2i_dict.from_string(\n"
    "     \"\"\n"
    "     <> \"     #     \\n\"\n"
    "     <> \" ###   ### \\n\"\n"
    "     <> \"           \\n\"\n"
    "     <> \"### ##### #\\n\"\n"
    "     <> \"# # #   # #\\n\"\n"
    "     <> \"# # # # # #\\n\"\n"
    "     <> \"# # ### # #\\n\"\n"
    "     <> \"# #     # #\\n\"\n"
    "     <> \"# ####### #\\n\"\n"
    "     <> \"#         #\\n\"\n"
    "     <> \"###########\\n\",\n"
    "   )\n"
    "\n"
    " let target = Vec2(5, 5)\n"
    "\n"
    " fn successor(state: Vec2i, g_score: Float) -> List(Action(Vec2i, Vec2i)) {\n"
    "   actions\n"
    "   |> list.filter_map(fn(action) {\n"
    "     let weight = action |> vec2i.length\n"
    "\n"
    "     use <- bool.guard(g_score +. weight >. 32.0, Error(Nil))\n"
    "     use <- bool.guard(vec2i.distance(state, target) >. 16.0, Error(Nil))\n"
    "\n"
    "     let state = state |> vec2i.subtract(action)\n"
    "\n"
    "     case world |> dict.has_key(state) {\n"
    "       True -> Error(Nil)\n"
    "       False -> Ok(Action(action:, state:, weight:))\n"
    "     }\n"
    "   })\n"
    " }\n"
    "\n"
    " astar(init:, successor:)\n"
    " // ↓↙→↘↓#↙←←←←\n"
    " // ↘###↓↙←###↙\n"
    " // →→↘↓↙←←←←←←\n"
    " // ###↓#####↖#\n"
    " // # #↓#↓↙←#↑#\n"
    " // # #↓#*#↖#↑#\n"
    " // # #↘###↑#↑#\n"
    " // # #→→→↗↑#↑#\n"
    " // # #######↑#\n"
    " // #→→→→→→→↗↑#\n"
    " // ###########\n"
    " ```\n"
).
-spec flowfield(DTP, fun((DTP, float()) -> list(action(DTQ, DTP)))) -> gleam@dict:dict(DTP, DTQ).
flowfield(State, Successor_fun) ->
    do_flowfield(State, Successor_fun, [State], maps:new()).