画板

随手画障碍,最短路随每一笔实时更新。

用途:自由涂画一张地图,边画边看最短路怎样绕开障碍;切换 4 / 8 邻域对比两种规则。

最短距离
…
步数
…
求解引擎
加载中…
每次求解
…
浏览器 JS/WASM 耗时(本机,非报告基准)
  • 起点 S
  • 终点 G
  • 障碍
  • 最短路

按住拖动即画;从障碍上开始拖动则擦除。拖动起点或终点可移动它们。每次改动后立即重新求解。

怎么用

  • 按住拖动画障碍;从障碍上开始拖动则擦除。也可以在上方切换成固定的「障碍」「擦除」「起点」「终点」画笔。
  • 拖动起点 S 或终点 G 可以移动它们。拖动过程中每经过一个格子就重新求解一次。
  • 「课程题」「载入」「随机」可以换一张起始地图;「复制链接」得到的链接里带着当前网格。

数据来源

求解在浏览器里完成,不读取预先算好的答案。引擎是项目仓库 zig/src/ 下的 Zig 求解器(planner.zig、conn8.zig、conn8_astar.zig,提交 fa87b65,原样复制),编译成 wasm32 + simd128 的 WebAssembly:

  • 4 邻域:solveAuto,先单调扫描,不成再走双向位并行 BFS。
  • 8 邻域:精确代价(a + b√2 整数比较)的 A*。

为了在 wasm 上编译,只改了 conn8_astar.zig 里的一个辅助函数 nzMask(向量比较结果转位掩码改用标量循环),其余代码不变。浏览器不支持 WebAssembly 时自动退回 TypeScript 实现(4 邻域逐格 BFS,8 邻域 A*),侧栏会标明当前引擎。

站点的测试在全部 29,746 道验证题上逐题核对了这份 WASM:4 邻域与 8 邻域的最短距离都与参考答案完全一致(各 26,696 道有解、3,050 道无解)。

侧栏的「每次求解」是浏览器 JS/WASM 耗时(本机,非报告基准):同一张图重复求解约 1.5 ms 取均值,随设备和浏览器变化,不能与报告里的基准数字比较。

作为参照,站点测试(npm test)在 Node 20.19.2 里用同一份 WASM 对验证题每隔 7 道取 1 道(共 4,250 道)循环求解约 1.5 秒:4 邻域 solveAuto 平均 1.14 µs/题,8 邻域 A* 平均 15.55 µs/题。这同样是本站构建机上的 Node 耗时,非报告基准。

本页目录