寻路算法实验室

四方向网格 · BFS 按步数 · Dijkstra / A* 按地形代价（普通格 1，高代价格 5，起点不计）

算法

速度约 50 步/秒

画笔

显示代价数值

地图与预设

预设种子

尺寸

当前搜索

三种算法对比（当前地图）

对比表在后台即时计算，不影响左侧动画。BFS 只保证步数最少；Dijkstra 与 A* 保证总代价最小。

规则说明

只能上下左右四方向移动，不能斜走，不能穿过墙壁。
BFS 把每一步都视为相同代价，按步数逐层扩展，得到步数最少的路径，不考虑地形代价。
Dijkstra 按累计地形代价从小到大扩展；A* 在此基础上加入曼哈顿距离启发值 h = |Δx| + |Δy|，按 f = g + h 扩展。由于最小进入代价为 1，h 不会高估，A* 与 Dijkstra 得到相同的最小总代价。
代价按“进入格子”计算：起点不计；普通格 1，高代价格 5（终点也按其地形计入）。
每次“单步”扩展一个节点：从前沿取出节点、标记为已访问，并把可达邻居加入前沿。

操作说明

选择画笔后在网格上按住拖动：墙壁/高代价画笔从已有同类格开始拖动时会改为擦除该类格。
按住起点（绿）或终点（红）拖动即可移动，它们不能被墙壁或地形覆盖，也不能放到墙上。
搜索进行中修改地图、移动起终点、切换算法或载入预设，都会立即停止并清除旧搜索。
快捷键：空格 运行/暂停，N 单步，C 清除搜索。