Safe Haskell | None |
---|---|

Language | Haskell2010 |

Breadth first search algorithm.

## Synopsis

- data BfsDistance
- data MoveLegal
- minKnownBfs :: BfsDistance
- apartBfs :: BfsDistance
- maxBfsDistance :: BfsDistance
- fillBfs :: Array Word8 -> Word8 -> Point -> Array BfsDistance -> ()
- data AndPath
- findPathBfs :: Array Word8 -> (Point -> Bool) -> Point -> Point -> Int -> Array BfsDistance -> AndPath
- accessBfs :: Array BfsDistance -> Point -> Maybe Int
- abortedKnownBfs :: BfsDistance
- abortedUnknownBfs :: BfsDistance

# Documentation

data BfsDistance Source #

Weighted distance between points along shortest paths.

## Instances

State of legality of moves between adjacent points.

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.

:: Array Word8 | |

-> Word8 | |

-> Point | starting position |

-> Array BfsDistance | initial array, with |

-> () |

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`

.

## Instances

Show AndPath Source # | |

Generic AndPath Source # | |

Binary AndPath Source # | |

type Rep AndPath Source # | |

Defined in Game.LambdaHack.Client.Bfs type Rep AndPath = D1 (MetaData "AndPath" "Game.LambdaHack.Client.Bfs" "LambdaHack-0.8.1.2-9Fmfvbfsr9xEInnejydwaW" False) (C1 (MetaCons "AndPath" PrefixI True) (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))) :+: C1 (MetaCons "NoPath" PrefixI False) (U1 :: * -> *)) |

findPathBfs :: Array Word8 -> (Point -> Bool) -> Point -> Point -> Int -> Array BfsDistance -> 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.

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

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

# Internal operations

abortedKnownBfs :: 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 known and not blocked. It is also a true distance value for this tile (shifted by minKnownBfs, as all distances of known tiles).

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.