Game.LambdaHack.Client.Bfs

Breadth first search algorithm.

Documentation

data BfsDistance

Weighted distance between points along shortest paths.

Instances

Eq BfsDistance

Defined in Game.LambdaHack.Client.Bfs

Methods

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

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

Ord BfsDistance

Defined in Game.LambdaHack.Client.Bfs

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

Defined in Game.LambdaHack.Client.Bfs

Methods

showsPrec :: Int -> BfsDistance -> ShowS

show :: BfsDistance -> String

showList :: [BfsDistance] -> ShowS

Bits BfsDistance

Defined in Game.LambdaHack.Client.Bfs

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

UnboxRepClass BfsDistance

Defined in Game.LambdaHack.Client.Bfs

Associated Types

type UnboxRep BfsDistance :: Type

Methods

toUnboxRepUnsafe :: BfsDistance -> UnboxRep BfsDistance

fromUnboxRep :: UnboxRep BfsDistance -> BfsDistance

type UnboxRep BfsDistance

Defined in Game.LambdaHack.Client.Bfs

type UnboxRep BfsDistance = Word8

data MoveLegal

State of legality of moves between adjacent points.

Constructors

MoveBlocked

MoveToOpen

MoveToClosed

MoveToUnknown

Instances

Eq MoveLegal

Defined in Game.LambdaHack.Client.Bfs

Methods

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

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

subtractBfsDistance :: BfsDistance -> BfsDistance -> Int

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.

maxBfsDistance :: BfsDistance

Maximum value of the type.

fillBfs :: Array Word8 -> Word8 -> Point -> (PrimArray PointI, PrimArray PointI) -> Array BfsDistance

Create and fill a BFS array for the given level. Unsafe array 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.

Instead of a BFS queue (list) we use the two tabs (arrays), for (JS) speed.

data AndPath

Constructors

AndPath

Fields

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

Instances

Show AndPath

Defined in Game.LambdaHack.Client.Bfs

Methods

showsPrec :: Int -> AndPath -> ShowS

show :: AndPath -> String

showList :: [AndPath] -> ShowS

Generic AndPath

Defined in Game.LambdaHack.Client.Bfs

Associated Types

type Rep AndPath :: Type -> Type

Methods

from :: AndPath -> Rep AndPath x

to :: Rep AndPath x -> AndPath

Binary AndPath

Defined in Game.LambdaHack.Client.Bfs

Methods

put :: AndPath -> Put

get :: Get AndPath

putList :: [AndPath] -> Put

type Rep AndPath

Defined in Game.LambdaHack.Client.Bfs

type Rep AndPath = D1 (MetaData "AndPath" "Game.LambdaHack.Client.Bfs" "LambdaHack-0.9.3.1-inplace" False) (C1 (MetaCons "AndPath" PrefixI True) ((S1 (MetaSel (Just "pathSource") NoSourceUnpackedness NoSourceStrictness DecidedStrict) (Rec0 Point) :*: S1 (MetaSel (Just "pathList") NoSourceUnpackedness NoSourceStrictness DecidedStrict) (Rec0 [Point])) :*: (S1 (MetaSel (Just "pathGoal") NoSourceUnpackedness NoSourceStrictness DecidedStrict) (Rec0 Point) :*: S1 (MetaSel (Just "pathLen") NoSourceUnpackedness NoSourceStrictness DecidedStrict) (Rec0 Int))))

actorsAvoidedDist :: Int

findPathBfs :: BigActorMap -> Array Word8 -> (PointI -> Bool) -> Point -> Point -> Int -> Array BfsDistance -> Maybe 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. The path tries hard to avoid actors and tries to avoid tiles that need altering and ambient light. Actors are avoided only close to the start of the path, because elsewhere they are likely to move before they are reached. Even projectiles are avoided, which sometimes has the effect of choosing a safer route (regardless if the projectiles are friendly fire or not).

An unwelcome side effect of avoiding actors is that friends will sometimes avoid displacing and instead perform two separate moves, wasting 1 turn in total. But in corridors they will still displace and elsewhere this scenario was quite rare already.

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

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

Internal operations

succBfsDistance :: BfsDistance -> BfsDistance

predBfsDistance :: BfsDistance -> BfsDistance

abortedUnknownBfs :: BfsDistance

The distance value that denotes that path search was aborted at this tile due to too large actual distance and that the tile was unknown. It is also a true distance value for this tile.