路径规划算法可视化
在线路径规划算法可视化:在可编辑网格上画墙、设权重与起终点,逐步演示 BFS、DFS、Dijkstra、A*、Greedy、双向 BFS 的扩散与回溯,支持启发式、对角移动、迷宫生成、六算法同图对比与路径 PNG/JSON 导出;纯浏览器本地计算,地图不上传。
使用说明
搜索算法
启发式权重 w1.0
绘制地图
画笔工具(在右侧网格上按住拖拽)右键格子可快速擦除。绿色为起点、红色为终点;琥珀色格是权重格,进入代价为普通格的 5 倍。
运行控制
动画速度8 步/帧
导入与导出
全部计算在浏览器本地完成,地图与文件不会上传到服务器。
搜索过程
就绪。选择算法后点击「开始搜索」。
已访问节点0
待探索边界0
路径步数--
路径总代价--
计算耗时--
起点
终点
墙
权重格(×5)
已访问 closed
待探索 open
最终路径
同图算法对比
点击左侧「对比全部 6 种算法」,会在同一张地图上依次跑完 6 种搜索,比较访问节点数与路径代价。
| 算法 | 访问节点 | 路径步数 | 路径代价 | 耗时 | 最优性 |
|---|
算法解读
g(n) 从起点到当前格的累计代价;h(n) 当前格到终点的估计代价;f(n)=g(n)+w·h(n) 是 A* 的排序依据。
open 是待探索边界(蓝色),closed 是已取出并扩展过的节点(蓝紫渐变,越晚访问越偏紫)。
可容许启发式 指 h 从不高估真实剩余代价;只有 h 可容许(且 w=1)时 A* 才保证最短路径。
普通格进入代价 1、权重格 5、对角移动再乘 √2;对角移动不允许贴着两个墙角穿越。
open 是待探索边界(蓝色),closed 是已取出并扩展过的节点(蓝紫渐变,越晚访问越偏紫)。
可容许启发式 指 h 从不高估真实剩余代价;只有 h 可容许(且 w=1)时 A* 才保证最短路径。
普通格进入代价 1、权重格 5、对角移动再乘 √2;对角移动不允许贴着两个墙角穿越。