MoonPath

A reusable grid pathfinding toolkit written in MoonBit.

Features

• BFS — unweighted shortest path on grid maps
• Dijkstra — weighted shortest path with terrain costs
• A* — heuristic-guided search for faster results
• Weighted terrain — assign custom traversal costs to cells
• Four-way & eight-way movement — cardinal-only or include diagonals
• Configurable heuristics — Manhattan, Euclidean, Chebyshev, Octile
• Path statistics — total cost and nodes visited/expanded
• Error handling — out-of-bounds, blocked cells, unreachable goals

Quick Start

# Check that everything compiles
moon check

# Run tests
moon test

# Run ASCII demo
moon run cmd/demo

Usage

// Create a 10x10 grid
let grid = Grid::new(10, 10)

// Add some walls
let grid = grid
  .set_wall(3, 3)
  .set_wall(3, 4)
  .set_wall(3, 5)

// Run A* with Manhattan heuristic
let opts : SearchOptions = {
  movement: Movement::FourWay,
  heuristic: manhattan,
}
let result = astar(grid, Point::new(0, 0), Point::new(9, 9), opts)

match result.path {
  Some(path) => {
    println("Path length: " + (path.length() - 1).to_string())
    println("Total cost: " + result.total_cost.to_string())
  }
  None => println("No path found")
}

Demo Output

=== MoonPath ASCII Demo ===

Grid:
S . . # .
# # . # .
. . . . .
. # # # .
. . . . G

--- BFS Result ---
Path found (BFS):
S * * # .
# # * # .
. . * * *
. # # # *
. . . . G
Steps: 8
Cost: 8

--- A* Result ---
Path found (A*):
S * * # .
# # * # .
. . * * *
. # # # *
. . . . G
Nodes visited: 15
Nodes expanded: 12

API

Types

Type	Description
Point	2D coordinate (x, y)
Cell	Empty | Blocked | Weighted(Int)
Grid	2D grid with cell access, validation, and mutation
Movement	FourWay or EightWay neighbor mode
Heuristic	Function type (Point, Point) -> Double
SearchOptions	{ movement: Movement, heuristic: Heuristic }
SearchResult	{ path: Array[Point]?, total_cost: Double, ... }

Algorithms

Function	Description
bfs(grid, start, goal)	BFS for unweighted graphs
dijkstra(grid, start, goal)	Dijkstra for weighted graphs
astar(grid, start, goal, opts)	A* with configurable heuristic

Heuristics

Function	Best for
manhattan	Four-way movement
euclidean	Any movement
chebyshev	Eight-way movement (uniform costs)
octile	Eight-way movement (diagonal = sqrt(2))
zero	Benchmark baseline (equivalent to Dijkstra)

Grid Methods

Method	Description
Grid::new(w, h)	Create empty grid
grid.in_bounds(p)	Check if point is within bounds
grid.is_passable(p)	Check if cell is traversable
grid.cost(x, y)	Get traversal cost
grid.get_cell(x, y)	Get cell type
grid.set_wall(x, y)	Set a wall
grid.set_weighted(x, y, w)	Set weighted terrain

Neighbor Generation

Function	Description
four_way_neighbors(grid, p)	Cardinal neighbors (N, S, E, W)
eight_way_neighbors(grid, p)	All 8 neighbors
four_way_neighbors_with_cost(grid, p)	Neighbors + costs
eight_way_neighbors_with_cost(grid, p)	Neighbors + costs (diag = 1.414)

Project Structure

MoonPath/
  src/
    types.mbt           Point, Cell, Movement, SearchResult
    grid.mbt            Grid data structure and methods
    neighbors.mbt       Neighbor generation (4-way, 8-way)
    bfs.mbt             BFS algorithm
    priority_queue.mbt  Binary heap for Dijkstra/A*
    dijkstra.mbt        Dijkstra's algorithm
    heuristics.mbt      Manhattan, Euclidean, Chebyshev, Octile
    astar.mbt           A* algorithm
    lib.mbt             Package documentation
    *_test.mbt          Unit tests
  cmd/demo/
    main.mbt            ASCII demo
  .github/workflows/ci.yml
  moon.mod.json
  README.md

Roadmap

v0.1.0 — Initial Release

• Point and Grid data structures
• Grid validation, cell access, terrain costs
• Four-way and eight-way neighbor generation
• BFS (unweighted shortest path)
• Binary heap priority queue
• Dijkstra weighted pathfinding
• A* with Manhattan, Euclidean, Chebyshev, Octile heuristics
• Path reconstruction and search statistics
• ASCII demo
• Unit tests
• GitHub Actions CI

v0.2.0 — Planned

• Jump Point Search (JPS)
• Theta* (any-angle pathfinding)
• Bidirectional search
• Path smoothing (string pulling)
• Dynamic replanning
• Benchmarks

v0.3.0 — Future

• Web visualization page
• moon prove formal verification
• Hex grids / non-rectangular maps
• mooncakes.io package publication

License

Apache-2.0