当然！以下是整理后的内容带图片的文档：
算法课程作业：A路径规划与 JPS 扩展*
主要探讨了 A* 路径规划算法，并附带实现了Jump Point Search (JPS)的改进版本，支持对角障碍物的阻塞与绕路处理。
注：所有代码都包含详细注释。
🤗 点击在线尝试：→ Binder
目录
- 展示柜
./src目录结构- 一些个人心得
- 2.1 梳理一下
- 2.2 JPS 算法碎碎念
- 容易被绕进去的地方
- 3.1 强制邻居是怎么引导扩展结点的？
- 对角障碍物的处理
- 4.1 初探
- 4.2 绕过对角障碍物
- 4.3 修正绕路后的搜索策略
- 其他需要说明的地方
- 5.1 生成问题时去除对角障碍物
- 踩到的一个坑
- 不足之处
- 总结
0. 展示柜
A* 算法：
带对角障碍物绕路机制的Jump Point Search (JPS)算法：
1. ./src 目录结构
src ├── algorithms # 算法实现 │ ├── __init__.py │ ├── a_star.py # A* 算法 │ ├── a_star_jps.py # A* Jump Point Search 版本 │ ├── a_star_jps_detour.py # JPS 版，支持对角障碍绕路 │ ├── a_star_jps_detour_fixed.py # 最优版 JPS，修正绕路后的搜索策略 │ ├── a_star_jps_detour_failed.py # 绕路失败的版本 │ ├── algorithm_base.py # 算法基类 │ ├── states.py # 算法状态枚举 │ └── utils.py # 工具类（方向处理相关） ├── exceptions │ └── __init__.py # 自定义异常 ├── problems │ ├── __init__.py │ ├── cell_status.py # 格子状态枚举 │ ├── drawer.py # 问题绘制模块 │ ├── generator.py # 随机问题生成 │ ├── problem.py # 问题类，用于表示二维栅格图 │ └── utils.py # 工具方法 ├── test.py # 测试用例 ├── requirements.txt # Python 依赖 ├── problem.bin # 示例问题（pickle 格式） └── visualization ├── __init__.py ├── algo_animator.py # 算法动画化模块 ├── problem_visualizer.py # 问题可视化模块 ├── result_visualizer.py # 结果可视化模块 └── utils.py # 可视化相关工具方法说明：
- 每个算法实现的
.py文件头部均包含文档注释，具体内容可以查看源码。 - 示例问题可以通过
Problem.from_file方法载入。 - 调用方法请参考
test.py文件以及各个方法的docstring注释。
2. 一些个人心得
2.1 梳理一下
- Dijkstra 算法：逐步扩展路径最短的结点，虽然能找到最优路径，但扩展速度缓慢，适合边权非负的场景。
- A* 算法：在 Dijkstra 的基础上加入启发式信息，加速搜索过程，但启发式计算方式对性能有较大影响。
- Jump Point Search (JPS)算法：通过跳点大幅减少扩展结点数量，是 A* 的一种重要优化。
核心思想：扩展结点的策略。
JPS 算法的优化点：
- 强制邻居：引导结点扩展，找到跳点。
- 跳点：扩展目标，不是所有邻居，而是跳点。
2.2 JPS 算法碎碎念
在 JPS 中，扩展结点仅限于跳点，而不是 A* 的邻居，从而显著减少扩展数量。优化点主要在扩展策略。
JPS 的两个核心概念：
- 强制邻居（Forced Neighbor）：通过其引导扩展跳点。
- 跳点（Jump Point）：算法扩展的实际目标。
💡总结：相比 A*，JPS 改进的重点在“扩展结点的部分”。
3. 容易被绕进去的地方
3.1 强制邻居是如何引导扩展的？
强制邻居的作用：
- 用于判定跳点。
- 用于引导扩展结点方向。
例：
水平/竖直方向
- 沿路径方向扩展，遇到强制邻居，新增扩展方向。
对角方向
- 同时沿水平和竖直方向移动，遇到障碍物时，强制新增方向。
以下图示展示扩展方式：
4. 对角障碍物的处理
4.1 初探
diagonal_obstacles参数控制是否允许穿过对角障碍物。如下示例：
Case 1：简单对角障碍
Case 2：复杂对角障碍
4.2 绕过对角障碍物
对于复杂障碍，JPS 可通过额外记录“绕路结点”实现绕行，如下图：
4.3 修正绕路后的搜索策略
修正策略：将绕路结点临时加入open_list并强制搜索平行方向，确保找到最优路径。
示例：
5. 其他需要说明的地方
5.1 生成问题时去除对角障碍物
示例：
未去除对角障碍物：
去除对角障碍物：
6. 踩到的一个坑
绕路结点加入open_list时的注意事项：
- 不标记其坐标，避免与其他结点冲突。
- 不加入
closed_list，仅作为临时结点。
7. 不足之处
- 在障碍物复杂的图中，修正后的 JPS 求解速度仍慢于 A*。
- 跳点搜索耗时较高，特别是在随机障碍物分布的情况下。
8. 总结
通过实现 JPS 及其改进版，深刻体会到路径规划的趣味与复杂性。特别是在绕路与搜索策略修正部分，算法的设计与优化充满挑战和成就感！
