实现并比较了Breadth-First Search (BFS), Greedy BFS, Dijkstra, A*, Jump Point Search (JPS), 以及弗洛伊德路径平滑算法
- main.lua: 运行寻路算法的主脚本
- map_util.lua: 地图工具
- minheap.lua: 最小堆实现
- BFS.lua: BFS算法
- greedyBFS.lua: 贪心BFS算法
- Dijkstra.lua: 弗洛伊德路径平滑算法
- Astar.lua: A*算法
- JPS.lua: JPS算法
- AstarWithSmoothing.lua: 对A*进行弗洛伊德路径平滑优化
- BFS_path.csv: BFS寻路结果
- Astar_path.csv: A*寻路结果
- JPS_path.csv: JPS寻路结果
- Astar_smooth_path.csv: A*弗洛伊德平滑优化结果
- algorithm_compare.csv: 寻路算法比较结果
BFS是一种最基础的寻路算法，能够保证找到最短路径（在所有边权相等的情况下）。实现简单，适合无权图。但在实际大地图或障碍较多时，BFS会遍历大量无效节点，效率较低。
算法特点：
- 优点：实现简单，保证找到最短路径
- 缺点：扩展节点多，效率低
改进点：
- 将基本操作改为6方向以实现在蜂窝网格中的扩展
- 优化节点索引：(row-1)*cols+col
适用场景：
- 小规模地图
- 无权图
- 需要简单实现的场景
后续可以改进的点：
- 可结合双向BFS优化
- 封装queue, 优化队列操作
Greedy BFS引入了启发式函数，每次优先扩展距离目标最近的节点。虽然速度提升明显，但不能保证找到最短路径，容易陷入局部最优。
算法特点：
- 优点：搜索方向性强，效率较高
- 缺点：可能找到非最优路径
改进点：
- 自定义优先级队列, 实现insert_priority_queue函数
- 使用欧几里得距离作为启发函数，来兼容蜂窝网格
- 优化节点展开顺序
适用场景：
- 需要快速找到可行路径
- 最优性要求不高的场景
后续可以改进的点：
- 结合A*的代价函数，既利用启发式信息，又兼顾已走路径长度
- 使用LuaJIT加速排序
Dijkstra适用于带权图，能找到从起点到所有点的最短路径。与BFS相比，Dijkstra适用范围更广，但在无权图上效率与BFS类似。
算法特点：
- 优点：保证最短路径
- 缺点：计算成本高
改进点：
- 利用最小堆优化开放列表
适用场景：
- 需要精确最短路径
- 不计较效率的场景
后续可以改进的点：
- 开放列表优化
- 使用Lua的FFI实现更高效堆
A算法结合了Dijkstra和Greedy BFS的优点，利用启发式函数（h）和已走路径（g）共同决定扩展顺序。只要启发式函数不高估，A能保证最优解且效率极高。
算法特点：
- 优点：平衡效率与最优性
- 缺点：启发函数设计影响大
改进点：
- 使用欧几里得距离作为启发函数，来兼容蜂窝网格
- 优化节点重复检查
适用场景：
- 大多数寻路场景
- 需要平衡效率与质量的场景
后续可以改进的点：
- 分层路径规划(HPA*)
- 动态调整启发权重
- goal 不可到达时，选择离goal最近的位置继续寻路
JPS是对A*的优化，专门针对网格地图。通过跳点规则，大幅减少扩展节点数量，极大提升效率。实现上较为复杂，但效果显著。
算法特点：
- 优点：大幅减少节点扩展
- 缺点：实现复杂
改进点：
- 基于蜂窝网格的强制邻居检测表
适用场景：
- 开放地图
- 需要高效寻路的场景
后续可以改进的点：
- 优化对角线移动处理
- 缓存跳跃点结果
Floyd路径平滑用于优化寻路结果，使路径更自然、节点更少。通过消除多余拐点，提升路径可用性。
算法特点：
- 优点：显著减少路径节点数，使路径更自然
- 缺点：需要额外的计算时间
实现原理：
-
直线可见性检查：
- 检查两点间是否存在无障碍直线路径
-
路径平滑处理：
- 从起点开始，寻找最远的可见点
- 跳过中间冗余节点
改进点：
- 优化直线检查算法，减少计算量
适用场景：
- 需要更自然移动路径的应用
- 路径节点数过多的场景
- 对路径美观度有要求的游戏
后续可以改进的点：
- 预计算可见性表 以加速检查
- 优化对角线移动的平滑处理
lua main.lua <algorithm> <map_file> <start_row> <start_col> <goal_row> <goal_col> Example:
lua main.lua Astar map.bytes 1 1 10 10| Algorithm | Time Cost | Number of path nodes |
|---|---|---|
| BFS | 3.9372s | 715 |
| Greedy BFS | 3.3256s | 955 |
| Dijkstra | 2.1230s | 715 |
| A* | 0.1072s | 716 |
| JPS | 0.7738s | 681 |
| A* + Smoothing | 0.1336s | 128 |
A*算法在大多数场景下表现最优，平衡了效率与路径质量。JPS算法在开放地图下表现优秀，但需要更多计算资源。路径平滑可显著改善视觉效果。
适用场景：
- 小规模地图：BFS或Dijkstra
- 中等规模地图：A*
- 大型开放地图：JPS
- 需要自然移动：A*+平滑
实践建议：
- 根据实际场景选择算法，没有绝对最优
- 在路径质量和计算开销间寻找平衡
- 考虑预处理和缓存优化常用路径