viva_aion

-module(viva_aion@pathfinding).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch, inline]).
-define(FILEPATH, "src/viva_aion/pathfinding.gleam").
-export([retrocausal_pull/3, rank_moves/3, distance_to_goal/2, find_path/3, expand_light_cone/3]).
-export_type([path_result/0, path_error/0]).

-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(
    " Pathfinding - Navigation through the labyrinth\n"
    "\n"
    " ## Light Cone Expansion\n"
    "\n"
    " In Block Universe physics, the future already exists.\n"
    " Light cone expansion reveals all reachable positions within\n"
    " a given number of steps - the \"possible futures\" from a point.\n"
    "\n"
    " ## Retrocausality\n"
    "\n"
    " The Core (goal) exerts a \"pull\" on the present. We calculate\n"
    " which move minimizes distance to the inevitable singularity.\n"
).

-type path_result() :: {path_result,
        list(viva_aion@position:position()),
        integer()}.

-type path_error() :: no_path | invalid_start | invalid_goal.

-file("src/viva_aion/pathfinding.gleam", 184).
?DOC(
    " Retrocausal pull - which direction minimizes distance to goal?\n"
    "\n"
    " The future (goal) exerts influence on the present decision.\n"
).
-spec retrocausal_pull(
    viva_aion@grid:grid(),
    viva_aion@position:position(),
    viva_aion@position:position()
) -> {ok, viva_aion@position:direction()} | {error, nil}.
retrocausal_pull(G, Current, Goal) ->
    viva_aion@log:pathfinding(
        <<"Calculating retrocausal pull from "/utf8,
            (viva_aion@log:fmt_pos(
                erlang:element(2, Current),
                erlang:element(3, Current)
            ))/binary>>
    ),
    Directions = viva_aion@position:all_directions(),
    Scored = begin
        _pipe = Directions,
        gleam@list:filter_map(
            _pipe,
            fun(Dir) ->
                Next = viva_aion@position:move(Current, Dir),
                case viva_aion@grid:is_passable(G, Next) orelse viva_aion@grid:is_core(
                    G,
                    Next
                ) of
                    false ->
                        {error, nil};

                    true ->
                        Dist = viva_aion@position:manhattan_distance(Next, Goal),
                        {ok, {Dir, Dist}}
                end
            end
        )
    end,
    case Scored of
        [] ->
            {error, nil};

        _ ->
            _pipe@1 = Scored,
            _pipe@2 = gleam@list:sort(
                _pipe@1,
                fun(A, B) ->
                    gleam@int:compare(
                        erlang:element(2, A),
                        erlang:element(2, B)
                    )
                end
            ),
            _pipe@3 = gleam@list:first(_pipe@2),
            (fun(R) -> case R of
                    {ok, {Dir@1, _}} ->
                        {ok, Dir@1};

                    {error, _} ->
                        {error, nil}
                end end)(_pipe@3)
    end.

-file("src/viva_aion/pathfinding.gleam", 224).
?DOC(" Get all moves sorted by distance to goal (best first)\n").
-spec rank_moves(
    viva_aion@grid:grid(),
    viva_aion@position:position(),
    viva_aion@position:position()
) -> list({viva_aion@position:direction(), integer()}).
rank_moves(G, Current, Goal) ->
    _pipe = viva_aion@position:all_directions(),
    _pipe@1 = gleam@list:filter_map(
        _pipe,
        fun(Dir) ->
            Next = viva_aion@position:move(Current, Dir),
            case viva_aion@grid:is_passable(G, Next) orelse viva_aion@grid:is_core(
                G,
                Next
            ) of
                false ->
                    {error, nil};

                true ->
                    Dist = viva_aion@position:manhattan_distance(Next, Goal),
                    {ok, {Dir, Dist}}
            end
        end
    ),
    gleam@list:sort(
        _pipe@1,
        fun(A, B) ->
            gleam@int:compare(erlang:element(2, A), erlang:element(2, B))
        end
    ).

-file("src/viva_aion/pathfinding.gleam", 244).
?DOC(" Distance to goal from position (Manhattan)\n").
-spec distance_to_goal(
    viva_aion@position:position(),
    viva_aion@position:position()
) -> integer().
distance_to_goal(Pos, Goal) ->
    viva_aion@position:manhattan_distance(Pos, Goal).

-file("src/viva_aion/pathfinding.gleam", 249).
-spec pos_key(viva_aion@position:position(), integer()) -> integer().
pos_key(Pos, Width) ->
    viva_aion@position:to_key(Pos, Width).

-file("src/viva_aion/pathfinding.gleam", 80).
-spec do_bfs(
    viva_aion@grid:grid(),
    viva_aion@position:position(),
    list({viva_aion@position:position(), list(viva_aion@position:position())}),
    gleam@dict:dict(integer(), boolean())
) -> {ok, path_result()} | {error, path_error()}.
do_bfs(G, Goal, Queue, Visited) ->
    case Queue of
        [] ->
            {error, no_path};

        [{Current, Path} | Rest] ->
            case viva_aion@position:equals(Current, Goal) of
                true ->
                    {ok,
                        {path_result,
                            lists:reverse(Path),
                            erlang:length(Path) - 1}};

                false ->
                    Neighbors = begin
                        _pipe = viva_aion@grid:passable_neighbors(G, Current),
                        gleam@list:filter(
                            _pipe,
                            fun(P) ->
                                case gleam_stdlib:map_get(
                                    Visited,
                                    pos_key(P, erlang:element(2, G))
                                ) of
                                    {ok, _} ->
                                        false;

                                    {error, _} ->
                                        true
                                end
                            end
                        )
                    end,
                    {New_queue, New_visited} = gleam@list:fold(
                        Neighbors,
                        {Rest, Visited},
                        fun(Acc, Neighbor) ->
                            {Q, V} = Acc,
                            New_path = [Neighbor | Path],
                            {lists:append(Q, [{Neighbor, New_path}]),
                                gleam@dict:insert(
                                    V,
                                    pos_key(Neighbor, erlang:element(2, G)),
                                    true
                                )}
                        end
                    ),
                    do_bfs(G, Goal, New_queue, New_visited)
            end
    end.

-file("src/viva_aion/pathfinding.gleam", 68).
?DOC(" BFS implementation\n").
-spec bfs(
    viva_aion@grid:grid(),
    viva_aion@position:position(),
    viva_aion@position:position()
) -> {ok, path_result()} | {error, path_error()}.
bfs(G, Start, Goal) ->
    Initial_queue = [{Start, [Start]}],
    Visited = maps:from_list([{pos_key(Start, erlang:element(2, G)), true}]),
    do_bfs(G, Goal, Initial_queue, Visited).

-file("src/viva_aion/pathfinding.gleam", 39).
?DOC(" BFS to find shortest path\n").
-spec find_path(
    viva_aion@grid:grid(),
    viva_aion@position:position(),
    viva_aion@position:position()
) -> {ok, path_result()} | {error, path_error()}.
find_path(G, Start, Goal) ->
    viva_aion@log:pathfinding(
        <<<<<<"BFS from "/utf8,
                    (viva_aion@log:fmt_pos(
                        erlang:element(2, Start),
                        erlang:element(3, Start)
                    ))/binary>>/binary,
                " to "/utf8>>/binary,
            (viva_aion@log:fmt_pos(
                erlang:element(2, Goal),
                erlang:element(3, Goal)
            ))/binary>>
    ),
    case viva_aion@grid:is_passable(G, Start) of
        false ->
            viva_aion@log:warn(
                <<"pathfinding"/utf8>>,
                <<"Invalid start position"/utf8>>
            ),
            {error, invalid_start};

        true ->
            case viva_aion@grid:is_passable(G, Goal) orelse viva_aion@grid:is_core(
                G,
                Goal
            ) of
                false ->
                    viva_aion@log:warn(
                        <<"pathfinding"/utf8>>,
                        <<"Invalid goal position"/utf8>>
                    ),
                    {error, invalid_goal};

                true ->
                    bfs(G, Start, Goal)
            end
    end.

-file("src/viva_aion/pathfinding.gleam", 143).
-spec do_expand_light_cone(
    viva_aion@grid:grid(),
    list({viva_aion@position:position(), integer()}),
    gleam@dict:dict(integer(), integer()),
    integer()
) -> gleam@dict:dict(integer(), integer()).
do_expand_light_cone(G, Queue, Visited, Max_radius) ->
    case Queue of
        [] ->
            Visited;

        [{Current, Dist} | Rest] ->
            case Dist >= Max_radius of
                true ->
                    do_expand_light_cone(G, Rest, Visited, Max_radius);

                false ->
                    Neighbors = begin
                        _pipe = viva_aion@grid:passable_neighbors(G, Current),
                        gleam@list:filter(
                            _pipe,
                            fun(P) ->
                                case gleam_stdlib:map_get(
                                    Visited,
                                    pos_key(P, erlang:element(2, G))
                                ) of
                                    {ok, _} ->
                                        false;

                                    {error, _} ->
                                        true
                                end
                            end
                        )
                    end,
                    New_dist = Dist + 1,
                    {New_queue, New_visited} = gleam@list:fold(
                        Neighbors,
                        {Rest, Visited},
                        fun(Acc, Neighbor) ->
                            {Q, V} = Acc,
                            {lists:append(Q, [{Neighbor, New_dist}]),
                                gleam@dict:insert(
                                    V,
                                    pos_key(Neighbor, erlang:element(2, G)),
                                    New_dist
                                )}
                        end
                    ),
                    do_expand_light_cone(G, New_queue, New_visited, Max_radius)
            end
    end.

-file("src/viva_aion/pathfinding.gleam", 125).
?DOC(" Expand light cone - all reachable positions within radius\n").
-spec expand_light_cone(
    viva_aion@grid:grid(),
    viva_aion@position:position(),
    integer()
) -> list({viva_aion@position:position(), integer()}).
expand_light_cone(G, Origin, Radius) ->
    Initial = [{Origin, 0}],
    Visited = maps:from_list([{pos_key(Origin, erlang:element(2, G)), 0}]),
    _pipe = do_expand_light_cone(G, Initial, Visited, Radius),
    _pipe@1 = maps:to_list(_pipe),
    _pipe@2 = gleam@list:map(
        _pipe@1,
        fun(Pair) ->
            {Key, Dist} = Pair,
            {viva_aion@position:from_key(Key, erlang:element(2, G)), Dist}
        end
    ),
    gleam@list:sort(
        _pipe@2,
        fun(A, B) ->
            gleam@int:compare(erlang:element(2, A), erlang:element(2, B))
        end
    ).