🥮 mooncakes.io

    moonbitstack/moongraph/grid does not have a README file

    DStar

    source
    pub struct DStar {
      grid : Grid
      start : Int
      goal : Int
      g : Array[Double]
      rhs : Array[Double]
      km : Double
      open : 
    PairingHeap    [(Double, Double, Int)]
    }

    A board search that has been planned once and can be repaired: it holds the distance estimate of every cell, the queue of cells whose estimate is unsettled, and the offset that keeps the heuristic honest as the start moves.

    DStar::cost

    source
    fn DStar::cost(self : DStar) -> Double

    The cost of the route from the start to the goal as last planned, or a very large number when there is none.

    DStar::path

    source
    fn DStar::path(self : DStar) -> Array[Int]?

    The route as last planned, both ends included, or None when the goal cannot be reached.

    The route is read off the settled estimates greedily: from each cell, take the neighbour that leaves the least to pay. Because the estimates are settled, that walk is a cheapest route.

    DStar::replan

    source
    fn DStar::replan(self : DStar, start : Int, changed : Array[Int]) -> Unit

    Repair the plan after the board changed and the walker moved.

    changed lists the cells whose blocked state the caller just flipped — what a sensor update would report — and start is where the walker is now. The offset is raised by the distance walked, every cell the change touched is re-estimated, and the queue is worked until the new start is settled. Nothing else is thrown away, which is the whole point.

    Grid

    source
    pub struct Grid {
      width : Int
      height : Int
      blocked : Array[Bool]
    }

    A board of width × height cells, each free or blocked, numbered y * width + x.

    Grid::a_star

    source
    fn Grid::a_star(self : Grid, start : Int, goal : Int) -> Array[Int]?

    A cheapest route from start to goal, or None when the goal cannot be reached.

    A* with the octile distance as its estimate: it expands the cells the cheapest route plausibly crosses, and because the estimate never overestimates, the route it finds is a cheapest one.

    Grid::bfs

    source
    fn Grid::bfs(self : Grid, start : Int, goal : Int) -> Array[Int]?

    A cheapest route from start to goal when every step costs one, or None when the goal cannot be reached. Breadth first, so the route has the fewest cells.

    Grid::block

    source
    fn Grid::block(self : Grid, x : Int, y : Int) -> Unit

    Blocks a cell. Blocking a cell already blocked changes nothing.

    Grid::blocked_at

    source
    fn Grid::blocked_at(self : Grid, node : Int) -> Bool

    Whether the cell a number names is blocked, or off the board.

    Grid::d_star_lite

    source
    fn Grid::d_star_lite(self : Grid, start : Int, goal : Int) -> DStar

    Plan a route from start to goal, keeping the work so the next plan can reuse it.

    The first plan is already computed when this returns: path on the result is the route, and cost is what it costs. Block a cell, call replan with the cells that changed, and path is the new route — the search repairs what the change touched instead of starting over.

    test {
      let board = @grid.Grid::new(6, 6)
      let walker = board.d_star_lite(board.node(0, 0), board.node(5, 5))
      // Five across and five down, all diagonal: the octile distance.
      assert_eq(walker.cost(), board.estimate(board.node(0, 0), board.node(5, 5)))
      // A wall across the middle, with the walker still at the start.
      for y in 0..<5 {
        board.block(3, y)
      }
      walker.replan(board.node(0, 0), [
        board.node(3, 0),
        board.node(3, 1),
        board.node(3, 2),
        board.node(3, 3),
        board.node(3, 4),
      ])
      // The only way across is the bottom row, so the route is longer than the straight line.
      assert_true(
        walker.cost() > board.estimate(board.node(0, 0), board.node(5, 5)),
      )
    }

    Grid::dijkstra

    source
    fn Grid::dijkstra(self : Grid, start : Int) -> Array[Double]

    The cheapest cost of reaching every cell from start, 1.0e300 where a cell cannot be reached. Dijkstra over the eight-connected board.

    Grid::estimate

    source
    fn Grid::estimate(self : Grid, from : Int, to : Int) -> Double

    The octile distance between two cells: the cheapest a walk could possibly be, which is what A* steers by. It never overestimates, so A* still finds a cheapest route.

    Grid::height

    source
    fn Grid::height(self : Grid) -> Int

    How tall the board is.

    Grid::inside

    source
    fn Grid::inside(self : Grid, x : Int, y : Int) -> Bool

    Whether a cell is on the board.

    Grid::is_blocked

    source
    fn Grid::is_blocked(self : Grid, x : Int, y : Int) -> Bool

    Whether a cell is blocked, or off the board.

    Grid::jps

    source
    fn Grid::jps(self : Grid, start : Int, goal : Int) -> Array[Int]?

    A cheapest route from start to goal found by the jump-point search, or None when the goal cannot be reached.

    The search is A* that does not expand a cell whose parent can be reached from a cell before it by the same step: along an open straight or diagonal run it jumps straight to the next cell that matters, a corner of a blocked cell or the goal itself. The route it returns is cell by cell, and it costs the same as the one A* returns.

    Grid::line_of_sight

    source
    fn Grid::line_of_sight(self : Grid, from : Int, to : Int) -> Bool

    Whether a straight line between two cells stays on the board and off the blocked cells: the test Theta* uses before it lets a route skip a corner.

    The line is walked the way a rasteriser walks it — one cell at a time, choosing which axis to step on each turn so that the walk stays as close to the true line as a grid allows. A blocked cell anywhere along it, its ends included, fails the test.

    test {
      let board = @grid.Grid::new(5, 5)
      assert_true(board.line_of_sight(board.node(0, 0), board.node(4, 4)))
      board.block(2, 2)
      assert_false(board.line_of_sight(board.node(0, 0), board.node(4, 4)))
    }

    Grid::neighbors

    source
    fn Grid::neighbors(self : Grid, node : Int) -> Array[Int]

    The free neighbours of a cell, in the order up, down, left, right, then the four diagonals.

    A diagonal neighbour counts only when both cells the step squeezes between are free, so a walk never cuts the corner of a blocked cell.

    Grid::new

    source
    fn Grid::new(width : Int, height : Int) -> Grid

    A board with every cell free.

    Grid::node

    source
    fn Grid::node(self : Grid, x : Int, y : Int) -> Int

    The number the cell (x, y) carries.

    Grid::path_cost

    source
    fn Grid::path_cost(self : Grid, path : Array[Int]) -> Double

    The cost of walking a route, cell by cell; zero for a route of fewer than two cells.

    Grid::step_cost

    source
    fn Grid::step_cost(self : Grid, from : Int, to : Int) -> Double

    The cost of one step between two neighbouring cells: one straight, the diagonal otherwise.

    Grid::straight_cost

    source
    fn Grid::straight_cost(self : Grid, route : Array[Int]) -> Double

    The cost of an any-angle route: the octile length of each straight run, added up. Unlike path_cost, the stops need not be neighbours, only in sight of each other.

    Grid::theta_star

    source
    fn Grid::theta_star(self : Grid, start : Int, goal : Int) -> Array[Int]?

    The cheapest any-angle route from start to goal, both included, or None when no route exists.

    The walk is A* with one change: a neighbour is reached from the node's parent when the straight line between them is clear, so the route does not bend at a cell boundary it does not have to. The cost of a straight run is its octile length, the same measure the board uses for a step, so a route returned here can be compared with one a_star returns.

    test {
      let board = @grid.Grid::new(6, 6)
      let route = board.theta_star(board.node(0, 0), board.node(5, 5))
      match route {
        // Nothing in the way, so the route is a straight diagonal: two cells, not six.
        Some(cells) => assert_eq(cells.length(), 2)
        None => fail("an empty board has a route")
      }
    }

    Grid::unblock

    source
    fn Grid::unblock(self : Grid, x : Int, y : Int) -> Unit

    Frees a cell that was blocked.

    Grid::width

    source
    fn Grid::width(self : Grid) -> Int

    How wide the board is.

    Grid::x

    source
    fn Grid::x(self : Grid, node : Int) -> Int

    The column of a cell number.

    Grid::y

    source
    fn Grid::y(self : Grid, node : Int) -> Int

    The row of a cell number.

    Source Files