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.
• 7 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 heuristics.
• 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, wall='#')
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",
], wall='#')

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

Testing

The test suite covers:

• BFS shortest path around walls.
• Unreachable goals.
• Start equals goal.
• A* and Dijkstra cost consistency.
• 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

• Main implementation language is MoonBit.
• README explains project goal, usage, and examples.
• Runnable example is available.
• Tests cover core behavior.
• CI workflow is included.
• OSI-approved license is included.
• GitHub repository URL is filled in moon.mod.
• Gitlink repository is created and synchronized.
• Package is published to mooncakes.io.

License

Apache-2.0. See LICENSE.