#Moon PathPlanning

Moon PathPlanning is a reusable MoonBit path planning library for grid search, graph primitives, examples, tests, CLI demos, SVG output, and HTML output.

#项目简介

项目面向机器人路径规划、游戏地图寻路、网格导航、算法教学和确定性仿真。初版先交付二维网格地图、统一结果模型和可审查的经典搜索算法，为后续增量规划和采样规划保留可复用边界。

#项目背景与引用

本项目参考 zhm-real/PathPlanning 的路径规划主题、算法思想和案例方向。参考项目采用 MIT License；本仓库同样使用 MIT License，并在 MoonBit 原生包结构中重新组织数据模型、测试、Planner 和可视化能力，不直接照搬 Python 脚本式实现。

#功能列表

Point / Coord、搜索状态、搜索错误和统一 PathResult。
GridMap、四方向和八方向移动、障碍物、障碍物膨胀、terrain cost 与合法性检查。
WeightedGraph 加权节点和边接口。
Manhattan、Euclidean、Chebyshev 与 Octile 启发函数。
BFS、DFS、Dijkstra、A 星和双向 A 星搜索。
区域搜索预处理：障碍物边界角识别、候选搜索区域生成和空地图自由区域回退。
RS-APSO 基础组件：路径长度/平滑度适应度、固定 seed 随机源、自适应参数、停滞后多候选逃逸重采样、PSO/RS-APSO 主循环。
连续几何与采样规划基础组件：栅格中心线段栅格化、静态线段可见性检查、路径快捷平滑、基础 RRT、RRT-Connect 和 RRT* 采样规划。
动态避障基础组件：碰撞半径、移动障碍物碰撞检测、速度方向预测、边界往复预测、连续坐标时间预测、连续轨迹安全评估、连续碰撞诊断报告、连续轨迹最小安全间距评估、连续安全感知动态避障、连续等待避障和跳跃避障路径修正。
Planner 算法调度，包含经典搜索、LPA*/D* Lite 阶段入口、基础 PSO、RS-APSO、RRT、RRT-Connect 和 RRT*；JSON v1 示例、序列化、字符串解析、嵌入式示例地图、SVG/HTML 导出、RRT 系列路径对比 SVG/HTML、CLI demo，以及支持 JSON 文件、JSON 字符串和示例名输入的 benchmark runner。
LPA*/D* Lite 当前明确属于阶段入口：用于统一调度、状态结构和变化单元记录验证，尚不是复用上一轮 open list 的完整增量规划实现。

#当前完成情况

初步工程已包含源码、测试文件、示例地图、文档、CI 和 benchmark 说明，并已按论文方向开始补充区域搜索、swarm 基础模块、连续几何与基础 RRT/RRT-Connect/RRT* 采样规划模块和动态避障模块，其中 PSO/RS-APSO 已能在区域候选点中搜索中间路点并用 A 星拼接可行路径。JSON v1 当前提供 schema、示例地图、序列化和字符串解析入口。CLI v1 支持内置 demo 地图、--json 字符串输入、--example 跨后端示例名输入，也支持 native 后端读取 JSON 地图文件； bench runner 已固定两个 20x20 RS-APSO 场景和三个动态避障场景，并以 5 次重复输出经典搜索、LPA*/D* Lite 阶段入口、PSO/RS-APSO、RS-APSO 参数变体、RRT/RRT-Connect/RRT* 的 CSV 指标、耗时统计和连续动态行安全指标；runner 也支持 --json 字符串输入和 --example 示例名输入，native 后端还可读取 JSON v1 地图文件运行同格式 benchmark。增量规划边界请按阶段能力理解：当前 LPA*/D* Lite 会在地图变化后重新生成一致的搜索状态，用于保留 API 和测试变化单元记录；完整增量复用实现仍在后续路线中。

#快速开始

先安装 MoonBit 工具链，再在仓库根目录执行：

moon check
moon test
moon run cli
moon run cli -- --json '{\"format\":\"moon-pathplanning.grid.v1\",\"width\":3,\"height\":3,\"start\":[0,0],\"goal\":[2,2],\"movement\":\"four_way\",\"obstacles\":[],\"terrain\":[]}'
moon run cli -- --example weighted_grid
moon run cli --target native -- examples/simple_grid.json
moon run cli --target native -- --example weighted_grid --html weighted_grid.html
moon run ./bench
moon run ./bench -- --json '{\"format\":\"moon-pathplanning.grid.v1\",\"width\":3,\"height\":3,\"start\":[0,0],\"goal\":[2,2],\"movement\":\"four_way\",\"obstacles\":[],\"terrain\":[]}'
moon run ./bench -- --example rs_apso_20x20_simple
moon run ./bench --target native -- examples/simple_grid.json

当前 CLI 会运行内置 A 星示例并打印路径节点数、总代价、访问节点数和展开节点数。字符串型 JSON 输入使用 --json/-j，不依赖文件读取；PowerShell 中需要像上面的示例一样转义 JSON 双引号。嵌入式示例地图使用 --example/-e，当前支持 simple_grid、weighted_grid、rs_apso_20x20_simple 和 rs_apso_20x20_complex，适合默认后端下复用示例内容。文件型 JSON 输入需要 native 后端，命令形如 moon run cli --target native -- --map examples/weighted_grid.json。 HTML 可视化导出同样需要 native 后端，命令形如 moon run cli --target native -- --example weighted_grid --html weighted_grid.html，会在打印路径指标后生成包含网格、障碍物、起点、终点和最终路径的自包含 HTML 文件。 benchmark runner 会对 20x20 simple/complex 场景输出 A 星、Dijkstra、PSO、RS-APSO、RS-APSO 参数变体、RRT、RRT-Connect 和 RRT* 的路径长度、平滑度、访问/展开节点数、迭代次数、候选数量或采样树节点数、最终适应度、swarm 或采样参数、重复次数和总/平均耗时；同时输出 dynamic_5x1、dynamic_10x10_crossing 和 dynamic_12x12_mixed 下静态 A 星基线、整数速度动态修正、边界往复修正、连续安全感知修正和连续等待修正的同格式 CSV 行，并为连续动态行记录 safety_evaluated、continuous_safe 和 min_clearance。文件型 benchmark 输入需要 native 后端，命令形如 moon run ./bench --target native -- --map examples/weighted_grid.json。

#示例地图格式

examples/simple_grid.json 与 examples/weighted_grid.json 使用 moon-pathplanning.grid.v1 schema；examples/rs_apso_20x20_simple.json 与 examples/rs_apso_20x20_complex.json 固定 20x20 RS-APSO benchmark 输入：

{
  "format": "moon-pathplanning.grid.v1",
  "width": 6,
  "height": 5,
  "start": [0, 0],
  "goal": [5, 4],
  "movement": "four_way",
  "obstacles": [[1, 1], [1, 2]],
  "terrain": [{"point": [3, 2], "cost": 4.0}]
}

#API 示例

let map = @grid.new_grid(5, 5, @core.point(0, 0), @core.point(4, 4))
  .with_obstacles([@core.point(2, 1), @core.point(2, 2)])
let result = @planner.plan(map, @planner.AStar, @planner.default_options())

直接算法调用适合教学，Planner 适合统一业务入口。PathResult 包含路径、总代价、访问节点数、展开节点数、状态和错误字段；更多说明见 docs/api.md。

#测试方式

MoonBit 测试位于 test/，覆盖最短路径、无路径、障碍绕行、权重地图、三类算法一致性、移动模式、起点等于终点、非法地图输入、JSON 字符串解析、区域搜索、 RS-APSO 基础能力、LPA*/D* Lite 阶段入口、连续几何、基础 RRT/RRT-Connect/RRT* 采样规划和动态避障，包含整数栅格、线段可见性、路径快捷平滑、单树/双树采样绕障、RRT* 邻域择优与重连、固定 seed 复现、RS-APSO 即时停滞逃逸复现、增量重规划变化单元记录、无路返回、边界往复、连续坐标动态障碍物、连续轨迹安全评估、连续碰撞诊断、最小安全间距评估、连续安全感知修正、连续等待修正和混合穿越障碍物场景。标准检查命令是 moon check 与 moon test。CI 还会执行验收命令 moon fmt --deny-warn、moon info --deny-warn、moon check --deny-warn 和 moon test --deny-warn；由于当前 MoonBit 工具链的 fmt/info 子命令尚未直接暴露 --deny-warn 参数，CI 使用 .github/scripts/moon 将验收命令映射到当前工具链支持的格式检查和接口生成命令。

#可视化说明

src/visualize/svg_exporter.mbt 会导出网格、起点、终点、障碍物和最终路径的 SVG 字符串，也能通过 grid_region_to_svg() 叠加区域搜索候选格和障碍物边界角。调用方可将字符串写入展示层或示例文件；grid_paths_to_svg() 可叠加多条命名路径，rrt_comparison_to_svg() 可用固定采样参数把 RRT、RRT-Connect 和 RRT* 三条路径绘制到同一张 SVG 中。grid_to_html()、grid_region_to_html()、grid_paths_to_html() 和 rrt_comparison_to_html() 会把对应 SVG 包装为自包含 HTML 文档，便于直接落地成 .html 查看。仓库不提交大量生成图片。 CLI 已支持在 native 后端用 --html/-o <output.html> 直接导出基础路径 HTML。

#开发路线

第一阶段：基础工程、地图模型和五类搜索算法。
第二阶段：JSON、CLI、SVG/HTML 和 benchmark 完善。
第三阶段：基于论文资料推进区域搜索、RS-APSO 和动态避障。
第四阶段：LPA*/D* Lite 完整增量规划实现，并继续扩展基础 RRT/RRT-Connect/RRT* 的连续空间案例。
第五阶段：mooncakes.io 发布与 MoonBit 生态适配。

详细设计、迁移说明、RS-APSO 开发准备与路线图见 docs/。

#License

This project is released under the MIT License. See LICENSE.

Site source Report issue Packages Build queue Skills Statistics