#MoonPath

#评审速览

#30 秒体验

git clone https://github.com/Burnling-gx/moonpath.git
cd moonpath
moon test
moon run src/cmd/demo

#Why MoonPath

• 统一接口：三种算法都返回路径、代价、发现节点数和展开节点数。
• 正确处理权重：Dijkstra 与 A* 按进入目标格的地形代价计算；非法的零/负权不会进入网格。
• 安全八向移动：斜向代价为 sqrt(2) × terrain_cost，且不会从两个障碍之间穿角。
• 适合批量建图：set_cells 只复制网格一次，加载 K 个更新的复杂度为 O(N + K)。
• 可复现：65 个测试、基准入口、严格零警告检查、覆盖率、构建和 Demo 均进入 CI。

#Why MoonBit

• 使用 enum 与模式匹配表达网格单元和可选路径，减少无效状态。
• 使用强类型公开 API 明确移动方式、启发式约束、搜索结果和失败语义。
• 使用 MoonBit 原生测试、黑盒测试、benchmark 和 coverage 命令形成质量闭环。
• 通过 moon check --target all 持续验证多目标兼容性，并以 Wasm-GC release 构建复测性能。

#Demo

S 9 9 9 9 9 G
. # # # # # .
. . . . . . .

BFS（最少步数）             Dijkstra / A*（最低代价）
S * * * * * G              S 9 9 9 9 9 G
. # # # # # .              * # # # # # *
. . . . . . .              * * * * * * *

#Benchmark snapshot

#Quick start

git clone https://github.com/Burnling-gx/moonpath.git
cd moonpath

moon check --target all --deny-warn
moon test
moon build
moon run src/cmd/demo

# Optional: run the benchmark suite
moon bench --release

Total tests: 65, passed: 65, failed: 0.

#Install and use

moon add Burnling-gx/moonpath

import {
  "Burnling-gx/moonpath",
}

let grid = @moonpath.Grid::new(10, 10).set_cells([
  (@moonpath.Point::new(3, 3), @moonpath.Cell::Blocked),
  (@moonpath.Point::new(3, 4), @moonpath.Cell::Blocked),
  (@moonpath.Point::new(4, 2), @moonpath.Cell::Weighted(5)),
])

let start = @moonpath.Point::new(0, 0)
let goal = @moonpath.Point::new(9, 9)
let result = @moonpath.astar(
  grid,
  start,
  goal,
  @moonpath.SearchOptions::four_way(),
)

match result.path {
  Some(path) => {
    println("Steps: " + result.steps().to_string())
    println("Cost: " + result.total_cost.to_string())
  }
  None => println("No path found")
}

#Algorithm guide

• SearchOptions::four_way() — Manhattan heuristic.
• SearchOptions::eight_way() — Octile heuristic and no corner cutting.
• SearchOptions::new(movement, heuristic) — custom configuration.

#Cost and statistics semantics

• Moving into Empty costs 1; moving into Weighted(n) costs n.
• The start cell is not charged. A four-way path's cost is the sum of entered cells.
• Eight-way diagonal movement multiplies the entered cell's cost by sqrt(2).
• nodes_visited counts distinct discovered nodes, including the start.
• nodes_expanded counts neighbor-generation events; the goal is not expanded, and a reopened node may count again.
• On failure, path is None, total_cost is -1, and steps() returns -1.

#Safety guarantees

• Search rejects out-of-bounds or blocked start/goal points.
• get_cell returns Blocked outside the grid; try_get_cell returns None.
• Lenient setters ignore invalid updates; try_set_cell and try_set_weighted report them as None.
• from_cells rejects invalid dimensions, invalid weights, and mismatched cell counts.
• Grid dimensions are checked before multiplication to prevent cell-count overflow.
• Grid storage is private and copied at construction boundaries, so callers cannot break invariants through array aliasing.

#Public API at a glance

Grid
  new / try_new / from_cells
  width / height / size / in_bounds
  get_cell / try_get_cell / cost / is_passable
  set_cell / try_set_cell / set_cells / set_wall
  set_weighted / try_set_weighted / clear

Search
  bfs
  dijkstra / dijkstra_with_movement
  astar + SearchOptions

Result
  path / total_cost / nodes_visited / nodes_expanded
  found / steps

#Project structure

moon.mod                    module metadata (source root: src)
src/
  moon.pkg                 library package configuration
  types.mbt                public data model and result semantics
  grid.mbt                 validated immutable-style grid
  neighbors.mbt            four/eight-way movement and costs
  priority_queue.mbt       O(log n) deterministic binary min-heap
  bfs.mbt
  dijkstra.mbt
  astar.mbt
  heuristics.mbt
  *_test.mbt               black-box tests and benchmark cases
  cmd/demo/
    moon.pkg
    main.mbt               weighted ASCII comparison demo
.github/workflows/ci.yml   format, check, build, test, coverage, demo

#Roadmap

• 持续发布带变更记录和可复测结果的版本。
• 增加浏览器交互式路径可视化与更多地图密度的可复测基准。
• 探索双向搜索、Jump Point Search 与 moon prove 形式化性质。

#License