🥮 mooncakes.io

moon_path

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

pathfinding
grid
astar
dijkstra
bfs
moon add Feather119/moon_path@0.1.1
Download zip
Version
0.1.1
License
Apache-2.0
Repository
Last updated
yesterday
Downloads
13
README

#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 issuePackagesBuild queueSkillsStatistics

© 2026 mooncakes.io