defmodule Scurry.PolygonMap do
  @moduledoc """
  Utility functions to work on a polygon map.

  A polygon map is a set of a primary polygon - the **main** boundary that
  outlines the world - and a list of polygons that make **holes** in the main
  polygon.

  See `Polygon` for details on how polygons are composed.

  The use case is eg. making a map (the **main** polygon) with obstacles (the
  **holes**), and use the `Astar` module to find the shortest path between
  points in the map.

  See [Quickstart](quickstart.html) for a concrete end-to-end example of
  defining a world and holes/obstacles, then using `PolygonMap` and `Astar`
  modules to do path finding within this.
  """

  alias Scurry.Polygon
  alias Scurry.Vector
  use Scurry.Types
  use Scurry.Astar.Types

  @doc """
  Given a polygon map (`world` & `holes`), returns a list of vertices for a
  walkmap for A-star search


  ## Params

  * `world` (`t:polygon/0`), the polygon that defines the outer boundary.
  * `holes` (`t:list/0`), a list of `t:polygon/0` that define holes/obstacles inside `world`.

  ## Returns

  The walkmap as a `t:list/0` of `t:vector/0` that are the `worlds`'s concave
  vertices and the convex ones of the `holes`.

  These are used when generating the walk map, since only the `world`'s concave
  and the `holes`' convex ones limit where you can traverse in a 2D map. Any
  path has to walk around the holes' convex points and the world's concave.

  See [Quickstart](quickstart.html) for a concrete example.
  """
  @spec get_vertices(polygon(), list(polygon())) :: list(vector())
  def get_vertices(world, holes) do
    {concave, _convex} = Polygon.classify_vertices(world)

    convex =
      Enum.reduce(holes, [], fn points, acc ->
        {_concave, convex} = Polygon.classify_vertices(points)
        acc ++ convex
      end)

    concave ++ convex
  end

  @doc """
  Given a polygon map (`world` & `holes`) and list of vertices, makes the walk
  graph for a A-star search.

  ## Params

  * `world` (`t:polygon/0`) the polygon that defines the outer boundary.
  * `holes` (`t:list/0`), a list of `t:polygon/0` that define holes/obstacles inside `world`.
  * `vertices` (`t:list/0`), the result of `get_vertices/2`.
  * `cost_fun` (`t:cost_fun/0`) a "cost" function.

  The `cost_fun` is a function that indicates the of traversing between to
  points. It defaults to `Scurry.Vector.distance/2`, which is suitable for
  basic 2D map walking.

  ## Returns

  A `t:graph/0`, which is a map of all node to node reachable edges and their
  cost. This graphs is one of the parameters for a call to `Astar.search/4`.

  > ## Todo
  >
  > This should ideally take `line_of_sight/3` as a function so users can
  > customise which vertices can reach each other. But for now, users can make
  > the graph themselves just as easily.

  """
  @spec create_graph(polygon(), list(polygon()), list(vector()), cost_fun() | nil) :: graph()
  def create_graph(world, holes, vertices, cost_fun \\ nil)

  def create_graph(world, holes, vertices, nil) do
    create_graph(world, holes, vertices, &Vector.distance/2)
  end

  def create_graph(world, holes, vertices, cost_fun) do
    get_edges(world, holes, vertices, vertices, cost_fun)
  end

  @doc """
  Given a polygon map (main & holes), list of vertices and the initial graph
  from `create_graph/4`, extend the graph with extra `points`.

  This is used to "temporarily" expand the created walk graph with a start and
  end-point. This is a minor performance optimisation that saves work by
  reusing the fixed nodes and extend it with the moveable points.

  ## Params

  * `graph` (`t:graph/0`) the walk graph, as created by `create_graph/4`. This is used to return a new graph that's extended with `points`.
  * `world` (`t:polygon/0`) the polygon that defines the outer boundary.
  * `holes` (`t:list/0`), a list of `t:polygon/0` that define holes/obstacles inside `world`.
  * `vertices` (`t:list/0`) the list of vertices returned by `get_vertices/4`
    and used for `create_graph/4` to get `graph`.
  * `points` (`t:list/0`) a list of vectors (`t:vector/0`), `[{x, y}, {x, y}...]`, to extend with. Eg. a stop
  * `cost_fun` (`t:cost_fun/0`) a "cost" function.

  `world` and `holes` need to be passed in in addition to `graph`, so the
  function can determine line-of-sights between the existing graph and new
  points from `points`.

  The `cost_fun` is a function that indicates the of traversing between to
  points. It defaults to `Scurry.Vector.distance/2`, which is suitable for
  basic 2D map walking.

  ## Returns

  A tuple with the extended graph plus the combined list of vertices and new
  points, `{new_graph, new_vertices}`. The `new_graph` is intended to be used
  in calls to `Astar.search/4`, and `new_vertices` is solely provided as
  informational, eg. for displaying the graphs visually.
  """
  def extend_graph(graph, world, holes, vertices, points, cost_fun \\ nil)

  def extend_graph(graph, world, holes, vertices, points, nil) do
    extend_graph(graph, world, holes, vertices, points, &Vector.distance/2)
  end

  def extend_graph(graph, world, holes, vertices, points, cost_fun) do
    # To extend the graph `graph` made up up `vertices` with new points
    # `points`, we need to find three sets of edges (sub-graphs). The ones from
    # the new points to the existing vertices, vice-versa, and between the new
    # points.
    set_a = get_edges(world, holes, points, vertices, cost_fun)
    set_b = get_edges(world, holes, vertices, points, cost_fun)
    set_c = get_edges(world, holes, points, points, cost_fun)

    # Merge the three new sub-graphs into graph. This uses Map.merge with a
    # merge func that combines values for identical keys to extend them instead
    # of replacing, and dedupes.
    merge_fun = fn _k, v1, v2 ->
      Enum.dedup(v1 ++ v2)
    end

    graph =
      graph
      |> Map.merge(set_a, merge_fun)
      |> Map.merge(set_b, merge_fun)
      |> Map.merge(set_c, merge_fun)

    {graph, vertices ++ points}
  end

  @doc """

  Find the nearest point on the line that is inside the world polygion and
  outside all hole polygons.

  The purpose of this function is to determine compute a suitable end for the
  `points` parameter for `extend_graph/6`. Imagine a UI in which the users
  clicks on a point to walk to. If that click is outside the world map or
  inside a hole/obstacle, we can either refuse to compute a path, or we can use
  `nearest_point/3` to find the closest reachable point to the click.

  ## Params

  * `world` (`t:polygon/0`) the polygon that defines the outer boundary.
  * `holes` (`t:list/0`), a list of `t:polygon/0` that define holes/obstacles inside `world`.
  * `point` (`t:vector/0`) the point for which to find the nearst point.

  ## Returns

  A new point (`t:vector/0`) `p={x, y}` such that;

  * if `point` is _outside_ the world polygon, the new `p` is the closest point *on*
    the edge of the `world` polygon.

  * if `point` is _inside_ the world polygon, but also *inside* any hole
  polygon, the `p` the closest point on the edge of the hole it's in.

  """
    def nearest_point([], _, point) do point end

  def nearest_point(world, holes, point) do
    nearest_point_helper(world, holes, point, Polygon.is_inside?(world, point))
  end

  defp nearest_point_helper(_, holes, point, true) do
    nearest_point_in_holes(holes, point)
  end

  defp nearest_point_helper(points, _holes, point, false) do
    nearest_boundary_point_helper(points, point)
  end

  defp nearest_point_in_holes([], point) do
    point
  end

  defp nearest_point_in_holes([hole | holes], point) do
    nearest_point_in_holes_helper(
      [hole | holes],
      point,
      Polygon.is_inside?(hole, point, allow_border: false)
    )
  end

  defp nearest_point_in_holes_helper([_hole | holes], point, false) do
    nearest_point_in_holes(holes, point)
  end

  defp nearest_point_in_holes_helper([hole | _holes], point, true) do
    nearest_boundary_point_helper(hole, point)
  end

  defp nearest_boundary_point_helper(world, point) do
    {x, y} = Polygon.nearest_point_on_edge(world, point)

    # This is a problematic area - we want to round towards the start of the
    # line Eg. in complex.json scene, clicking {62, 310} yields {64.4, 308.8},
    # which naive rounding makes {64, 309}. This however places us *back*
    # *inside* the hole.

    # Some options are; try all four combos or floor/ceil and see which yields
    # the minimal distance - wrong, since the start might be on the far side of
    # a hole.

    # Shorten towards start? Same thing.

    # Actually run A-star to compute all four rounding and pick the shortest
    # path - that's a bit cpu heavy.

    # Compute all four rounding options and pick one that's *not* inside the
    # hole, and don't allow it to be on the border.

    p = {round(x), round(y)}
    a = {ceil(x), ceil(y)}
    b = {ceil(x), floor(y)}
    c = {floor(x), ceil(y)}
    d = {floor(x), floor(y)}

    cond do
      Polygon.is_outside?(world, p, allow_border: false) ->
        p

      Polygon.is_outside?(world, a, allow_border: false) ->
        a

      Polygon.is_outside?(world, b, allow_border: false) ->
        b

      Polygon.is_outside?(world, c, allow_border: false) ->
        c

      Polygon.is_outside?(world, d, allow_border: false) ->
        d
    end

    # If none of the points are outside, we'll pleasantly crash and we should
    # improve this to continuously move outwards a reasonable amount until
    # we're outside.
  end

  @doc """
  Checks if there's a line-of-sight (LOS) from `start` to `stop` within the map.

  ## Params
  * `polygon`, a list of `{x, y}` vertices. This is the main boundary map.
  * `holes`, a list of lists of `{x, y}` vertices. These are holes within
    `polygon`.
  * `line` a tuple of points (`{{ax, ay}, {bx, by}}`) describing a line.

  Returns `true` if there's a line-of-sight and none of the main polygon or
  holes obstruct the path. `false` otherwise.

  As the map consists of a boundary polygon with holes, LOS implies a few things;

  * If either `start` or `stop` is outside `polygon`, the result will be
    false. Even if both are outside, that's not considered a valid LOS.
  * If the distance between `start` and `stop` is tiny (< 0.1 arbitrarily), LOS
    is true.
  * Next, it checks that the line between `start` and `stop` has no
    intersections with `polygon` or `holes`.
  * Finally it checks if the middle of the line between `start` and `stop` is
    inside `polygon` and outside all holes - this ensures that corner-to-corner
    across a hole isn't considered a LOS.
  """
  def is_line_of_sight?(polygon, holes, line) do
    {start, stop} = line

    cond do
      not Polygon.is_inside?(polygon, start) or not Polygon.is_inside?(polygon, stop) ->
        false

      Vector.distance(start, stop) < 0.1 ->
        true

      not Enum.all?([polygon] ++ holes, fn points -> is_line_of_sight_helper(points, line) end) ->
        false

      true ->
        # This part ensures that two vertices across from each other are not
        # considered LOS. Without this, eg. a box-shaped hole would have
        # opposing corners be a LOS, except that the middle of the line falls
        # inside the hole per this check.
        middle = Vector.div(Vector.add(start, stop), 2)

        cond do
          not Polygon.is_inside?(polygon, middle) ->
            false

          Enum.all?(holes, fn hole -> Polygon.is_outside?(hole, middle, allow_border: false) end) ->
            true

          true ->
            false
        end
    end
  end

  defp is_line_of_sight_helper(polygon, {x, y} = line) do
    # We get all intersections and reject the ones that are identical to the
    # line. This allows us to enable "allow_points: true", but only see
    # intersections with other lines and _other_ polygon vertices (points).
    # This is necessary since we're always calling this with a line between two
    # polygon vertices. Without this, having "allow_points: true", every such
    # line would immediately intersect at both ends.

    Polygon.intersections(polygon, line, allow_points: true)
    |> Enum.map(fn {x, y} -> {round(x), round(y)} end)
    |> Enum.reject(fn p -> p == x or p == y end) ==
      []
  end

  # Get all edges from points_a and point_b for which there's line-of-sight.
  defp get_edges(world, holes, points_a, points_b, cost_fun) do
    is_reachable? = fn a, b -> is_line_of_sight?(world, holes, {a, b}) end

    # O(n^2) check all vertice combos for reachability...
    {_, all_edges} =
      Enum.reduce(points_a, {0, %{}}, fn a, {a_idx, acc1} ->
        {_, inner_edges} =
          Enum.reduce(points_b, {0, []}, fn b, {b_idx, acc2} ->
            # NOTE: this is where the edge value is becomes the key in the
            # graph. This is why a_idx and b_idx are available here, in case we
            # want to change it up to be the indexes into points. Unless those
            # two sets are the same, using the indexes makes no sense.
            if a != b and is_reachable?.(a, b) do
              {b_idx + 1, acc2 ++ [{b, cost_fun.(a, b)}]}
            else
              {b_idx + 1, acc2}
            end
          end)

        {a_idx + 1, Map.put(acc1, a, inner_edges)}
      end)

    Map.new(all_edges)
  end
end