【路径规划】基于A星算法实现栅格地图路径规划
发布网友
发布时间：2024-10-22 21:20
共1个回答
热心网友
时间：2024-11-24 13:52
我们假设某人需要从 A 点移动到 B 点，但两点间被障碍物隔开。图 1 展示了这个情况，绿色代表 A 点，红色代表 B 点，中间蓝色是障碍物。为了简化搜索区域，我们将其划分成正方形格子。通过计算从 A 到 B 需要经过哪些方格，可以找到路径。到达目的地时，人物从一个方格中心移动到另一个方格中心。
方格中心称为节点。在讨论 A* 算法时，人们经常提到节点而非方格，因为可以将搜索区域划分为任意形状，如六边形、矩形或任意多边形。节点可以位于多边形中心或边上。使用节点系统是因为它更简单。
搜索过程如下：
将起点 A 加入开放列表。开放列表相当于购物清单，初始只有起点。
检查与 A 相邻的可通行方格，加入开放列表。将 A 作为这些方格的父节点。
移除 A，加入关闭列表。关闭列表中方格不再关注。
图 2 展示了这个过程。深绿色方格为起点，外框为亮蓝色，加入关闭列表。与之相邻的黑色方格为待检查的，外框为亮绿色，每个方格都有灰色指针指向父节点 A。
继续搜索过程包括：
选择开放列表中 F 值最小的方格。
将其移至关闭列表。
检查相邻方格，忽略关闭列表或不可通行方格。若方格不在开放列表中，加入并设置父节点。
若相邻方格在开放列表中，检查路径是否更优，通过 G 值决定。若更优，更新父节点并重新计算 F 值。
计算 F、G 和 H 值：
G：从起点 A 到指定方格的移动代价。
H：从指定方格到终点 B 的估算成本。使用 Manhattan 方法计算，忽略对角移动。
F：G + H。
选择 G、H 和 F 值最小的方格。不断重复直至终点加入开放列表，路径已找到。
确定实际路径：从终点开始，沿父节点移动至起点。
A* 算法总结：
将起点加入开放列表。
遍历开放列表，选择 F 值最小的方格。
移至关闭列表，检查相邻方格，更新父节点和列表。
停止条件：终点加入开放列表或列表为空。
三、代码演示和仿真结果
