寻路算法实验室

在网格上比较 BFS、Dijkstra 与 A*。BFS 按步数搜索；Dijkstra 与 A* 按地形代价搜索。起点代价不计入，普通格进入代价 1，高代价地形进入代价 5。A* 使用曼哈顿距离作为启发函数。

算法

工具

速度 36 步/秒

空地障碍代价 5 前沿已访问路径

触摸或拖动即可绘制；直接拖动起点 / 终点可改变位置。搜索期间编辑地图会停止并清除当前搜索。

搜索结果

状态就绪

已访问节点0

当前前沿0

路径步数—

路径总代价—

算法指标—

选择算法与工具，然后点击“运行”。也可以先单步观察搜索前沿的扩张。

BFS：按步数最少搜索，队列先进先出，不考虑地形代价。
Dijkstra：按累计地形代价最小搜索。
A*：累计代价 + 曼哈顿距离启发；在四方向、最小进入代价为 1 时保持可采纳性。加权地图上 Dijkstra 与 A* 应得到相同的最小代价。

起点与终点不能被障碍或高代价地形覆盖。若终点被障碍完全封闭，搜索会明确显示“不可达”。暂停后画面停止扩张；单步每次只扩展一个节点。改变算法、地图或端点都会清除旧搜索，避免混用状态。

预设使用固定布局：包含墙体缺口、高代价沼泽与一条可通行路径，便于重复比较三种算法。