🥮 mooncakes.io

    moon_path

    A lightweight MoonBit pathfinding library for grid maps and graph search.

    pathfinding
    grid
    astar
    dijkstra
    bfs
    Download zip
    Version
    0.1.1
    License
    Apache-2.0
    Repository
    Last updated
    2 months ago
    Downloads
    45

    No dependencies

    #moon_path

    moon_path is a lightweight pathfinding library for MoonBit. It focuses on small, dependable building blocks for grid maps and graph-like search problems: BFS, Dijkstra, and A*.

    The project is designed for the 2026 MoonBit open source ecosystem contest. Its goal is to be useful, testable, easy to read, and easy to extend.

    #Status

    Current contest version:

    • Core grid pathfinding API implemented.
    • 8 behavior tests passing.
    • Runnable command example included.
    • CI workflow included for moon check and moon test.
    • Licensed under Apache-2.0.

    #Features

    • Point and Grid primitives for two-dimensional maps.
    • Four-direction and eight-direction neighborhood modes.
    • Breadth-first search for unweighted shortest paths.
    • Dijkstra search for weighted shortest paths.
    • A* search with Manhattan, Chebyshev, and squared Euclidean guidance while preserving optimal paths.
    • Path reconstruction with deterministic results.
    • Minimal runnable example using an ASCII map.

    #Install

    After the package is published to mooncakes.io, add it with:

    moon add Feather119/moon_path

    During local development, clone this repository and run commands from the project root.

    #Example

    let map = [
      "S....",
      ".###.",
      "...#G",
    ]

    let grid = @moon_path.Grid::from_ascii(map, '#')
    let start = @moon_path.Point::{ x: 0, y: 0 }
    let goal = @moon_path.Point::{ x: 4, y: 2 }

    let result = @moon_path.astar_grid(
      grid,
      start,
      goal,
      @moon_path.Neighbors::Four,
      @moon_path.Heuristic::Manhattan,
    )

    Run the included example:

    moon run cmd/grid_maze

    Expected output:

    found path with cost 6 and 7 nodes

    #API Overview

    #Point

    Point is a two-dimensional coordinate:

    let start = @moon_path.Point::{ x: 0, y: 0 }
    let goal = @moon_path.Point::{ x: 4, y: 2 }

    #Grid

    Grid stores map dimensions and passability:

    let grid = @moon_path.Grid::from_ascii([
      "S....",
      ".###.",
      "...#G",
    ], '#')

    You can also create an open grid:

    let grid = @moon_path.Grid::open(10, 10)

    #Search Functions

    • bfs_grid(grid, start, goal, neighbors) for unweighted shortest paths.
    • dijkstra_grid(grid, start, goal, neighbors) for uniform-cost paths.
    • astar_grid(grid, start, goal, neighbors, heuristic) for heuristic-guided search.

    #Neighbor Modes

    • Four: left, right, up, down.
    • Eight: four-way movement plus diagonals.

    #Heuristics

    • Manhattan
    • Chebyshev
    • EuclideanSquared

    A* caps the selected estimate at the admissible distance for the movement mode: Manhattan for four-way movement and Chebyshev for eight-way movement. This means EuclideanSquared can guide node ordering without allowing an overestimate to produce a path cost higher than Dijkstra's result.

    #Testing

    The test suite covers:

    • BFS shortest path around walls.
    • Unreachable goals.
    • Start equals goal.
    • A* and Dijkstra cost consistency.
    • Squared Euclidean A* optimality on a regression map.
    • Eight-way diagonal movement.
    • Blocked starts.
    • Heuristic distance calculations.

    #Planned Scope

    This first contest version intentionally keeps the API small:

    • Grid pathfinding first.
    • Generic graph adapters later.
    • Weighted cells later.
    • Priority queue optimization later.
    • Clear tests before advanced algorithms.

    #Development

    moon check
moon test

    Coverage, if the local MoonBit toolchain supports it:

    moon test --enable-coverage
moon coverage report -f summary

    #Contest Checklist

    #License

    Apache-2.0. See LICENSE.

    Grid

    source
    pub(all) struct Grid {
      width : Int
      height : Int
      passable : Array[Bool]
    } derive(Eq, 
    Debug    )

    Grid::contains

    source
    fn Grid::contains(self : Grid, point : Point) -> Bool

    Grid::from_ascii

    source
    fn Grid::from_ascii(rows : Array[String], wall : Char) -> Grid

    Grid::id

    source
    fn Grid::id(self : Grid, point : Point) -> Int

    Grid::is_passable

    source
    fn Grid::is_passable(self : Grid, point : Point) -> Bool

    Grid::new

    source
    fn Grid::new(width : Int, height : Int, passable : Array[Bool]) -> Grid

    Grid::open

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

    Grid::point

    source
    fn Grid::point(self : Grid, id : Int) -> Point

    Grid::set_passable

    source
    fn Grid::set_passable(self : Grid, point : Point, value : Bool) -> Unit

    Heuristic

    source
    pub(all) enum Heuristic {
      Manhattan
      Chebyshev
      EuclideanSquared
    } derive(Eq, 
    Debug    )

    Neighbors

    source
    pub(all) enum Neighbors {
      Four
      Eight
    } derive(Eq, 
    Debug    )

    PathResult

    source
    pub(all) struct PathResult {
      found : Bool
      cost : Int
      nodes : Array[Point]
    } derive(Eq, 
    Debug    )

    Point

    source
    pub(all) struct Point {
      x : Int
      y : Int
    } derive(Eq, 
    Debug    )

    astar_grid

    source
    fn astar_grid(grid : Grid, start : Point, goal : Point, neighbors : Neighbors, heuristic : Heuristic) -> PathResult

    bfs_grid

    source
    fn bfs_grid(grid : Grid, start : Point, goal : Point, neighbors : Neighbors) -> PathResult

    chebyshev

    source
    fn chebyshev(a : Point, b : Point) -> Int

    dijkstra_grid

    source
    fn dijkstra_grid(grid : Grid, start : Point, goal : Point, neighbors : Neighbors) -> PathResult

    estimate

    source
    fn estimate(a : Point, b : Point, heuristic : Heuristic) -> Int

    euclidean_squared

    source
    fn euclidean_squared(a : Point, b : Point) -> Int

    manhattan

    source
    fn manhattan(a : Point, b : Point) -> Int

    Source Files

    Powered by MoonBit

    Site sourceReport issueModulesSkillsCLIBuild queueStatistics

    © 2026 mooncakes.io