首页 / 编程开发 / 前端开发工具 / 路径规划算法可视化

路径规划算法可视化

在线路径规划算法可视化:在可编辑网格上画墙、设权重与起终点,逐步演示 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;对角移动不允许贴着两个墙角穿越。