🚁 无人机低空物流路径规划系统

Drone Low-Altitude Logistics Path Planning System (A* Algorithm)

基于 C11 标准实现的高效 A* 路径规划模拟器，专为城市低空物流场景设计。通过模块化编程完整覆盖地图解析 → 最优路径搜索 → 路径可视化 → 性能统计的全流程。

---

📊 项目概览

本系统模拟无人机从仓库（起点 S）飞往医院（终点 E）配送紧急物资的过程。城市环境中存在高层建筑（障碍物 1），无人机受限于电池续航，需要寻找一条距离最短且安全的飞行路径。

特性	描述
核心算法	A* (A-Star) 寻路算法
启发函数	曼哈顿距离：h = (x1 - x2) + (y1 - y2)
数据结构	最小堆 (二叉堆) 作为开放列表，O(log n) 插入/弹出
内存策略	节点池 (Node Pool) 一次申请、一次释放，零泄漏
编码标准	严格遵循 C11，禁用 VLA、gets()，强制指定初始化器

---

快速开始

1. 编译

# Linux / macOS / WSL
gcc -std=c11 -Wall -Wextra -o drone_planner main.c map.c heap.c astar.c

# Windows (MinGW，需指定 GBK 字符集以正确显示中文)
gcc -std=c11 -Wall -Wextra -fexec-charset=gbk -o drone_planner.exe main.c map.c heap.c astar.c

注意：四个 .c 文件缺一不可——main.c 是入口，map.c / heap.c / astar.c 分别是地图、堆、算法模块。

2. 运行

# 启动程序
./drone_planner.exe

3. 操作流程

请输入地图文件的路径（例如 ./maps/map1.txt）: map_test.txt

程序将依次执行：

[输入路径] → [加载地图] → [打印原始地图] → [A* 寻路] → [打印带路径的结果地图] → [输出统计] → [自动释放内存]

---

地图文件规范

字符定义

字符	含义	说明
S	起点	仓库 / 无人机起飞点
E	终点	医院 / 物资送达点
0	可通行	空旷飞行空域
1	障碍物	高层建筑，不可穿越

格式约束

• 尺寸上限：最大 50 × 50
• 无需声明尺寸：程序采用双轨扫描法自动探测行数和列宽
• 短行自动补全：不足最长行的位置自动填充 0
• 起终点唯一：文件中必须有且至少各一个 S 和 E

示例文件

S0000
01110
00010
01010
0001E

项目内附带多组测试地图，位于 程序测试验证/测试地图数据/ 目录下：

• map1标准绕障.txt — 标准绕障碍场景 (5×5)
• map2无路可走.txt — 起点被包围，终点不可达
• map3大地图.txt — 大规模压力测试
• map4唯一路线.txt — 仅有一条可行路径

---

核心设计

模块架构

┌─────────┐     ┌─────────┐     ┌─────────┐
│  map.h  │     │ heap.h  │     │ astar.h │
│  map.c  │     │ heap.c  │     │ astar.c │
├─────────┤     ├─────────┤     ├─────────┤
│ 地图加载 │     │ 最小堆   │     │ A* 搜索  │
│ 双轨扫描 │     │ 上浮下沉 │     │ 路径回溯 │
│ 可视化   │     │ Push/Pop│     │ 代价计算 │
└────┬────┘     └────┬────┘     └────┬────┘
     │               │               │
     └───────────────┼───────────────┘
                     │
              ┌──────┴──────┐
              │   main.c    │
              │ 入口·计时·统计│
              └─────────────┘

地图模块 (map)

功能	实现方式
尺寸探测	第一遍扫描：fgets 逐行读取，统计行数和最长列宽
数据灌入	第二遍扫描：按探测到的尺寸 malloc 二维网格，逐字符写入
S/E 定位	写入时识别 S / E 记录坐标，随后替换为 0（便于算法统一处理）
可视化	map_print 双重循环逐格输出，在起点/终点坐标处还原 S / E

堆模块 (heap)

特性	说明
堆性质	最小堆，按 f_cost = g + h 排序，根节点为当前最优候选
核心操作	heap_sift_up (插入时上浮) / heap_sift_down (弹出时下沉)
容量上限	HEAP_MAX_SIZE = 2500（对应 50 × 50 地图）
接口	heap_push / heap_pop / heap_is_empty

A* 算法模块 (astar)

┌─────────────────────────────────────┐
│  1. 分配 Closed List (malloc 二维)   │
│  2. 分配 Node Pool (一次 calloc)     │
│  3. 初始化起点，推入 Open List        │
│  4. 主循环：                         │
│     ├─ pop 最优节点                  │
│     ├─ 终点判定 → 回溯标记路径        │
│     ├─ 标记 Closed                   │
│     └─ 探索四邻居：                  │
│        ├─ 越界/障碍/Closed → 跳过    │
│        ├─ 未见过 → 初始化 + push     │
│        └─ 已见过 → Lazy 更新         │
│  5. 堆空 → 无可行路径                │
└─────────────────────────────────────┘

技术细节	说明
启发式函数	曼哈顿距离：`
节点池	calloc(width × height, sizeof(Node)) 一次性分配，node_map[r][c] 按 r × width + c 索引
Closed List	malloc 二维 uint8_t 数组（非 VLA，符合 C11 第 4 条）
Lazy 更新	发现更优 g 时直接更新并重新 push，旧条目出堆时通过 Closed 跳过
路径回溯	从终点沿 parent 链递归至起点，途中将 grid 改写为 *
起终点保护	回溯标记跳过 (start_row, start_col) 和 (end_row, end_col)

---

运行输出示例

===== 原始地图 =====
Map 5x5  start=(0,0) end=(4,4)
  S 0 0 0 0
  0 1 1 1 0
  0 0 0 1 0
  0 1 0 1 0
  0 0 0 1 E

===== A* 寻路中... =====

===== 寻路结果 =====
Map 5x5  start=(0,0) end=(4,4)
  S * * * *
  0 1 1 1 *
  0 0 0 1 *
  0 1 0 1 *
  0 0 0 1 E

===== 统计成绩单 =====
  路径总长度:   8 步
  搜索展开节点: 17 个
  运行耗时:     3.00 ms

其中 * 标记的格子即为无人机的最优飞行路径。

---

错误码参考

错误码	含义	程序输出
0	加载成功	—
-1	文件不存在或无法打开	错误：找不到地图文件！
-2	地图为空或格式错误	错误：地图内容为空或格式不正确！
-3	宽或高超过 50	错误：地图尺寸超过50x50限制！
-4	malloc 失败	错误：内存分配失败！
-5	缺少 S 或 E	错误：地图中缺失S或E！

寻路阶段另有独立错误提示：

返回值	含义	程序输出
0	寻路成功	打印带 * 的结果地图 + 统计成绩单
-1	无可行路径	异常：起点被包围或终点不可达，无可行路径！
-2	内存不足	错误：内存不足，寻路中断！

---

项目结构

实验6_无人机路径规划综合实践/
│
├── main.c                    # 程序入口：交互输入、计时、统计输出
├── map.h / map.c             # 地图模块：双轨扫描、动态加载、可视化
├── heap.h / heap.c           # 最小堆模块：A* 开放列表核心数据结构
├── astar.h / astar.c         # A* 算法模块：启发式搜索、路径回溯
│
├── map_test.txt              # 快速测试用地图 (5×5)
├── 程序测试验证/
│   └── 测试地图数据/          # 多组测试用例（标准/无路/大地图/唯一路径）
│
├── AGENTS.md                 # AI 开发辅助规则（与 CLAUDE.md 等效）
├── CLAUDE.md                 # C11 编码标准 + 项目需求说明
├── .gitignore                # Git 忽略规则
├── README.md                 # 本文件
└── 开发报告.md               # 人机协作开发过程实录

---

技术约束 (C11 Compliance)

本项目严格遵循 CLAUDE.md 中规定的 7 条 C11 编码标准：

1. 定宽整数 — 所有坐标和尺寸使用 uint32_t、int32_t（<stdint.h>）
2. 指定初始化器 — 结构体初始化使用 .member = value 语法
3. 禁止 gets() — 仅使用 fgets、scanf（含宽度限制 %255s）
4. 禁用 VLA — 关闭列表和节点映射全部使用 malloc / calloc 动态分配
5. 编译期断言 — 关键结构中可使用 _Static_assert
6. 就近声明 — 循环变量在 for 头部声明（如 for (uint32_t r = 0; ...)）
7. 注释规范 — 所有函数和关键变量均附带注释

---

编译零警告 | 内存零泄漏 | 算法最优性可证明 | 错误处理全覆盖