Game.LambdaHack.Client.Bfs

Breadth first search algorithms.

Documentation

data BfsDistance

Weighted distance between points along shortest paths.

Instances

Bounded BfsDistance

Methods

minBound :: BfsDistance

maxBound :: BfsDistance

Enum BfsDistance

Methods

succ :: BfsDistance -> BfsDistance

pred :: BfsDistance -> BfsDistance

toEnum :: Int -> BfsDistance

fromEnum :: BfsDistance -> Int

enumFrom :: BfsDistance -> [BfsDistance]

enumFromThen :: BfsDistance -> BfsDistance -> [BfsDistance]

enumFromTo :: BfsDistance -> BfsDistance -> [BfsDistance]

enumFromThenTo :: BfsDistance -> BfsDistance -> BfsDistance -> [BfsDistance]

Eq BfsDistance

Methods

(==) :: BfsDistance -> BfsDistance -> Bool

(/=) :: BfsDistance -> BfsDistance -> Bool

Ord BfsDistance

Methods

compare :: BfsDistance -> BfsDistance -> Ordering

(<) :: BfsDistance -> BfsDistance -> Bool

(<=) :: BfsDistance -> BfsDistance -> Bool

(>) :: BfsDistance -> BfsDistance -> Bool

(>=) :: BfsDistance -> BfsDistance -> Bool

max :: BfsDistance -> BfsDistance -> BfsDistance

min :: BfsDistance -> BfsDistance -> BfsDistance

Show BfsDistance

Methods

showsPrec :: Int -> BfsDistance -> ShowS

show :: BfsDistance -> String

showList :: [BfsDistance] -> ShowS

Bits BfsDistance

Methods

(.&.) :: BfsDistance -> BfsDistance -> BfsDistance

(.|.) :: BfsDistance -> BfsDistance -> BfsDistance

xor :: BfsDistance -> BfsDistance -> BfsDistance

complement :: BfsDistance -> BfsDistance

shift :: BfsDistance -> Int -> BfsDistance

rotate :: BfsDistance -> Int -> BfsDistance

zeroBits :: BfsDistance

bit :: Int -> BfsDistance

setBit :: BfsDistance -> Int -> BfsDistance

clearBit :: BfsDistance -> Int -> BfsDistance

complementBit :: BfsDistance -> Int -> BfsDistance

testBit :: BfsDistance -> Int -> Bool

bitSizeMaybe :: BfsDistance -> Maybe Int

bitSize :: BfsDistance -> Int

isSigned :: BfsDistance -> Bool

shiftL :: BfsDistance -> Int -> BfsDistance

unsafeShiftL :: BfsDistance -> Int -> BfsDistance

shiftR :: BfsDistance -> Int -> BfsDistance

unsafeShiftR :: BfsDistance -> Int -> BfsDistance

rotateL :: BfsDistance -> Int -> BfsDistance

rotateR :: BfsDistance -> Int -> BfsDistance

popCount :: BfsDistance -> Int

data MoveLegal

State of legality of moves between adjacent points.

Constructors

MoveBlocked

MoveToOpen

MoveToClosed

MoveToUnknown

Instances

Eq MoveLegal

Methods

(==) :: MoveLegal -> MoveLegal -> Bool

(/=) :: MoveLegal -> MoveLegal -> Bool

minKnownBfs :: BfsDistance

The minimal distance value assigned to paths that don't enter any unknown tiles.

apartBfs :: BfsDistance

The distance value that denotes no legal path between points, either due to blocked tiles or pathfinding aborted at earlier tiles, e.g., due to unknown tiles.

fillBfs

Arguments

:: Array Word8

-> Word8

-> Point

starting position

-> Array BfsDistance

initial array, with apartBfs

-> ()

Fill out the given BFS array. Unsafe PointArray operations are OK here, because the intermediate values of the vector don't leak anywhere outside nor are kept unevaluated and so they can't be overwritten by the unsafe side-effect.

When computing move cost, we assume doors openable at no cost, because other actors use them, too, so the cost is shared and the extra visiblity is valuable, too. We treat unknown tiles specially. Whether suspect tiles are considered openable depends on smarkSuspect.

data AndPath

Constructors

AndPath

Fields

• pathList :: ![Point]
• pathGoal :: !Point
• pathLen :: !Int

NoPath

Instances

Show AndPath

Methods

showsPrec :: Int -> AndPath -> ShowS

show :: AndPath -> String

showList :: [AndPath] -> ShowS

Generic AndPath

Associated Types

type Rep AndPath :: * -> *

Methods

from :: AndPath -> Rep AndPath x

to :: Rep AndPath x -> AndPath

Binary AndPath

Methods

put :: AndPath -> Put

get :: Get AndPath

putList :: [AndPath] -> Put

type Rep AndPath

type Rep AndPath = D1 (MetaData "AndPath" "Game.LambdaHack.Client.Bfs" "LambdaHack-0.6.0.0-KKqNxYnoEMa5Wo2qfudFog" False) ((:+:) (C1 (MetaCons "AndPath" PrefixI True) ((:*:) (S1 (MetaSel (Just Symbol "pathList") NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 [Point])) ((:*:) (S1 (MetaSel (Just Symbol "pathGoal") NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 Point)) (S1 (MetaSel (Just Symbol "pathLen") NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 Int))))) (C1 (MetaCons "NoPath" PrefixI False) U1))

findPathBfs :: Array Word8 -> (Point -> Bool) -> Point -> Point -> Int -> Array BfsDistance -> AndPath

Find a path, without the source position, with the smallest length. The eps coefficient determines which direction (of the closest directions available) that path should prefer, where 0 means north-west and 1 means north.

accessBfs :: Array BfsDistance -> Point -> Maybe Int

Access a BFS array and interpret the looked up distance value.

Internal operations