画板
随手画障碍,最短路随每一笔实时更新。
用途:自由涂画一张地图,边画边看最短路怎样绕开障碍;切换 4 / 8 邻域对比两种规则。
怎么用
- 按住拖动画障碍;从障碍上开始拖动则擦除。也可以在上方切换成固定的「障碍」「擦除」「起点」「终点」画笔。
- 拖动起点 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 耗时,非报告基准。