-- | Common definitions for the Field of View algorithms.
-- See <https://github.com/LambdaHack/LambdaHack/wiki/Fov-and-los>
-- for some more context and references.
module Game.LambdaHack.Server.Fov.Common
  ( -- * Current scan parameters
    Distance, Progress
    -- * Scanning coordinate system
  , Bump(..)
    -- * Geometry in system @Bump@
  , Line(..), ConvexHull, Edge, EdgeInterval
    -- * Assorted minor operations
  , maximal, steeper, addHull
  ) where

import Data.List

-- | Distance from the (0, 0) point where FOV originates.
type Distance = Int
-- | Progress along an arc with a constant distance from (0, 0).
type Progress = Int

-- | Rotated and translated coordinates of 2D points, so that the points fit
-- in a single quadrant area (e, g., quadrant I for Permissive FOV, hence both
-- coordinates positive; adjacent diagonal halves of quadrant I and II
-- for Digital FOV, hence y positive).
-- The special coordinates are written using the standard mathematical
-- coordinate setup, where quadrant I, with x and y positive,
-- is on the upper right.
data Bump = B
  { bx :: !Int
  , by :: !Int
  }
  deriving Show

-- | Straight line between points.
data Line = Line !Bump !Bump
  deriving Show

-- | Convex hull represented as a list of points.
type ConvexHull   = [Bump]
-- | An edge (comprising of a line and a convex hull)
-- of the area to be scanned.
type Edge         = (Line, ConvexHull)
-- | The area left to be scanned, delimited by edges.
type EdgeInterval = (Edge, Edge)

-- | Maximal element of a non-empty list. Prefers elements from the rear,
-- which is essential for PFOV, to avoid ill-defined lines.
maximal :: (a -> a -> Bool) -> [a] -> a
{-# INLINE maximal #-}
maximal gte = foldl1' (\acc e -> if gte e acc then e else acc)

-- | Check if the line from the second point to the first is more steep
-- than the line from the third point to the first. This is related
-- to the formal notion of gradient (or angle), but hacked wrt signs
-- to work fast in this particular setup. Returns True for ill-defined lines.
steeper :: Bump -> Bump -> Bump -> Bool
{-# INLINE steeper #-}
steeper (B xf yf) (B x1 y1) (B x2 y2) =
  (yf - y1)*(xf - x2) >= (yf - y2)*(xf - x1)

-- | Extends a convex hull of bumps with a new bump. Nothing needs to be done
-- if the new bump already lies within the hull. The first argument is
-- typically `steeper`, optionally negated, applied to the second argument.
addHull :: (Bump -> Bump -> Bool)  -- ^ a comparison function
        -> Bump                    -- ^ a new bump to consider
        -> ConvexHull  -- ^ a convex hull of bumps represented as a list
        -> ConvexHull
{-# INLINE addHull #-}
addHull gte new = (new :) . go
 where
  go (a:b:cs) | gte a b = go (b:cs)
  go l = l