Game.LambdaHack.Server.FovDigital

DFOV (Digital Field of View) implemented according to specification at http://roguebasin.roguelikedevelopment.org/index.php?title=Digital_field_of_view_implementation. This fast version of the algorithm, based on PFOV, has AFAIK never been described nor implemented before.

Documentation

scan

Arguments

:: EnumSet Point

-> Distance

visiblity distance

-> Array Bool

-> (Bump -> Point)

coordinate transformation

-> EnumSet Point

Calculates the list of tiles, in Bump coordinates, visible from (0, 0), within the given sight range.

Scanning coordinate system

data Bump

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.

Constructors

B

Fields

• bx :: !Int
• by :: !Int

Instances

Show Bump

Methods

showsPrec :: Int -> Bump -> ShowS

show :: Bump -> String

showList :: [Bump] -> ShowS

Assorted minor operations

Current scan parameters

type Distance = Int

Distance from the (0, 0) point where FOV originates.

type Progress = Int

Progress along an arc with a constant distance from (0, 0).

Geometry in system Bump

data Line

Straight line between points.

Constructors

Line !Bump !Bump

Instances

Show Line

Methods

showsPrec :: Int -> Line -> ShowS

show :: Line -> String

showList :: [Line] -> ShowS

type ConvexHull = [Bump]

Convex hull represented as a list of points.

type Edge = (Line, ConvexHull)

An edge (comprising of a line and a convex hull) of the area to be scanned.

type EdgeInterval = (Edge, Edge)

The area left to be scanned, delimited by edges.

Internal operations

steeper :: Bump -> Bump -> Bump -> Ordering

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.

addHull

Arguments

:: (Bump -> Bump -> Ordering)

a comparison function

-> Bump

a new bump to consider

-> ConvexHull

a convex hull of bumps represented as a list

-> ConvexHull

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.

dline :: Bump -> Bump -> Line

Create a line from two points. Debug: check if well-defined.

dsteeper :: Bump -> Bump -> Bump -> Ordering

Compare steepness of (p1, f) and (p2, f). Debug: Verify that the results of 2 independent checks are equal.

intersect :: Line -> Distance -> (Int, Int)

The X coordinate, represented as a fraction, of the intersection of a given line and the line of diagonals of diamonds at distance d from (0, 0).

_debugSteeper :: Bump -> Bump -> Bump -> Ordering

Debug functions for DFOV:

Debug: calculate steeper for DFOV in another way and compare results.

_debugLine :: Line -> (Bool, String)

Debug: check if a view border line for DFOV is legal.