LambdaHack-0.11.0.1: A game engine library for tactical squad ASCII roguelike dungeon crawlers

Safe Haskell | None
Language | Haskell2010

Game.LambdaHack.Client.Bfs

Contents

- Internal operations

Description

Breadth first search algorithm.

Synopsis

- data BfsDistance
- data MoveLegal
  - = MoveBlocked
  - | MoveToOpen
  - | MoveToClosed
  - | MoveToUnknown
- subtractBfsDistance :: BfsDistance -> BfsDistance -> Int
- minKnownBfs :: BfsDistance
- apartBfs :: BfsDistance
- maxBfsDistance :: BfsDistance
- fillBfs :: Array Word8 -> Word8 -> Point -> (PrimArray PointI, PrimArray PointI) -> Array BfsDistance
- data AndPath = AndPath {
  - pathSource :: Point
  - pathList :: [Point]
  - pathGoal :: Point
  - pathLen :: Int
  }
- findPathBfs :: EnumSet Point -> Array Word8 -> (PointI -> Bool) -> Point -> Point -> Int -> Array BfsDistance -> Maybe AndPath
- accessBfs :: Array BfsDistance -> Point -> Maybe Int
- succBfsDistance :: BfsDistance -> BfsDistance
- predBfsDistance :: BfsDistance -> BfsDistance
- abortedUnknownBfs :: BfsDistance
- maskBfs :: BfsDistance -> BfsDistance
- distanceBfs :: BfsDistance -> Maybe Int

# Documentation

data BfsDistance Source #

Weighted distance between points along shortest paths.

#### Instances

Instances details

UnboxRepClass BfsDistance Source # |

Instance details

Defined in Game.LambdaHack.Client.Bfs

Associated Types

type UnboxRep BfsDistance |
Instance details Defined in Game.LambdaHack.Client.Bfs type UnboxRep BfsDistance

Methods

toUnboxRepUnsafe :: BfsDistance -> UnboxRep BfsDistance Source #

fromUnboxRep :: UnboxRep BfsDistance -> BfsDistance Source #

Bits BfsDistance Source # |

Instance details

Defined in Game.LambdaHack.Client.Bfs

Methods

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

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

xor :: BfsDistance -> BfsDistance -> BfsDistance Source #

complement :: BfsDistance -> BfsDistance Source #

shift :: BfsDistance -> Int -> BfsDistance Source #

rotate :: BfsDistance -> Int -> BfsDistance Source #

zeroBits :: BfsDistance Source #

bit :: Int -> BfsDistance Source #

setBit :: BfsDistance -> Int -> BfsDistance Source #

clearBit :: BfsDistance -> Int -> BfsDistance Source #

complementBit :: BfsDistance -> Int -> BfsDistance Source #

testBit :: BfsDistance -> Int -> Bool Source #

bitSizeMaybe :: BfsDistance -> Maybe Int Source #

bitSize :: BfsDistance -> Int Source #

isSigned :: BfsDistance -> Bool Source #

shiftL :: BfsDistance -> Int -> BfsDistance Source #

unsafeShiftL :: BfsDistance -> Int -> BfsDistance Source #

shiftR :: BfsDistance -> Int -> BfsDistance Source #

unsafeShiftR :: BfsDistance -> Int -> BfsDistance Source #

rotateL :: BfsDistance -> Int -> BfsDistance Source #

rotateR :: BfsDistance -> Int -> BfsDistance Source #

popCount :: BfsDistance -> Int Source #

Show BfsDistance Source # |
Instance details Defined in Game.LambdaHack.Client.Bfs Methods showsPrec :: Int -> BfsDistance -> ShowS Source # show :: BfsDistance -> String Source # showList :: [BfsDistance] -> ShowS Source #
Eq BfsDistance Source # |
Instance details Defined in Game.LambdaHack.Client.Bfs Methods (==) :: BfsDistance -> BfsDistance -> Bool Source # (/=) :: BfsDistance -> BfsDistance -> Bool Source #
Ord BfsDistance Source # |

Instance details

Defined in Game.LambdaHack.Client.Bfs

Methods

compare :: BfsDistance -> BfsDistance -> Ordering Source #

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

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

(>) :: BfsDistance -> BfsDistance -> Bool Source #

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

max :: BfsDistance -> BfsDistance -> BfsDistance Source #

min :: BfsDistance -> BfsDistance -> BfsDistance Source #

type UnboxRep BfsDistance Source # |
Instance details Defined in Game.LambdaHack.Client.Bfs type UnboxRep BfsDistance

data MoveLegal Source #

State of legality of moves between adjacent points.

Constructors

MoveBlocked |
MoveToOpen |
MoveToClosed |
MoveToUnknown |

#### Instances

Instances details

Eq MoveLegal Source # |
Instance details Defined in Game.LambdaHack.Client.Bfs Methods (==) :: MoveLegal -> MoveLegal -> Bool Source # (/=) :: MoveLegal -> MoveLegal -> Bool Source #

subtractBfsDistance :: BfsDistance -> BfsDistance -> Int Source #

minKnownBfs :: BfsDistance Source #

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

apartBfs :: BfsDistance Source #

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 Source #

Maximum value of the type.

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

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 Source #

Constructors

AndPath |

Fields

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

#### Instances

Instances details

Binary AndPath Source # |
Instance details Defined in Game.LambdaHack.Client.Bfs Methods put :: AndPath -> Put Source # get :: Get AndPath Source # putList :: [AndPath] -> Put Source #
Generic AndPath Source # |

Instance details

Defined in Game.LambdaHack.Client.Bfs

Associated Types

type Rep AndPath |

Instance details

Defined in Game.LambdaHack.Client.Bfs

type Rep AndPath = D1 ('MetaData "AndPath" "Game.LambdaHack.Client.Bfs" "LambdaHack-0.11.0.1-BLuOaw8nuizISmzkanqI8h" '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))))

Methods

from :: AndPath -> Rep AndPath x Source #

to :: Rep AndPath x -> AndPath Source #

Show AndPath Source # |
Instance details Defined in Game.LambdaHack.Client.Bfs Methods showsPrec :: Int -> AndPath -> ShowS Source # show :: AndPath -> String Source # showList :: [AndPath] -> ShowS Source #
type Rep AndPath Source # |

Instance details

Defined in Game.LambdaHack.Client.Bfs

type Rep AndPath = D1 ('MetaData "AndPath" "Game.LambdaHack.Client.Bfs" "LambdaHack-0.11.0.1-BLuOaw8nuizISmzkanqI8h" '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))))

findPathBfs :: EnumSet Point -> Array Word8 -> (PointI -> Bool) -> Point -> Point -> Int -> Array BfsDistance -> Maybe AndPath Source #

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 (only if they had opposed direction of their goals; unlikely). But in corridors they will still displace and elsewhere this scenario was quite rare already.

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

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

# Internal operations

succBfsDistance :: BfsDistance -> BfsDistance Source #

predBfsDistance :: BfsDistance -> BfsDistance Source #

abortedUnknownBfs :: BfsDistance Source #

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.

maskBfs :: BfsDistance -> BfsDistance Source #

distanceBfs :: BfsDistance -> Maybe Int Source #