Flash平台上自动寻路(A)算法优化设计(4)
时间:2017-06-22 17:34 来源:毕业论文 作者:毕业论文 点击:次
节点代价系数：根据节点在地图中的虚拟属性，比如:沙漠，草地，森林，所定义的障碍系数。 g：从起始节点到当前某个节点的代价值，是一个精确值。 h：从当前某个节点到目标节点的代价值。这是一个估计值，由启发函数来计算该值，计算时不考虑障碍物的情况。 f：一个节点的代价值，f=g+h。 启发函数：计算从当前某个节点到目标节点所需估计代价的函数。 开启列表：已经访问过并且计算、赋值过代价的节点所组成的列表。 关闭列表：周围8个节点全部访问过的节点所组成的列表。 父节点：一个节点的父级节点，指由通过哪一个节点走到当前节点。 算法流程描述 A 将起始节点添加进开启列表。 B 主循环 a 寻找开启列表中代价（f值）最小的节点，取出这个节点设置为当前节点。 b 如果当前节点是终点则完成寻路，转到步骤5。 c 检查当前节点的各个相邻节点，一共8个。 （1）如果检查的相邻节点是不可通过的则跳过继续处理下一个邻节点，否则继续。 （2）拐角判断，检查与该邻节点同一列（或者行），与当前节点同一（或者列）的节点是否为不可通过，如果为不可通过，则跳过继续 处 理下一个邻节点，否则继续。 （3）计算该邻节点的代价f值（f=g+h）。 （4）最佳路径判断：经在开启列表或者关闭列表中：判断它现在计算出的的f值是否小于原先计算出的f值 如果是，则将其g值、h值、f值更新为当前计算出的相应值，将其父节点设置为当前节点，跳过步骤（5）。如果不是则跳过这个邻节点处理下一个邻节点。如果该邻节点不在开启列表或者关闭列表中，继续下一步。 （5）将计算出的g值，h值，f值赋给该节点，并且将其添加进开启列表中。 d 将当前节点放入关闭列表中。 C 如果开启列表长度为0，则说明没有找到路径，退出循环，转到步骤4。对于更新后的开启列表循环步骤B。 D 路径没有找到，寻路结束。 E 已经到达终点，创建一个路径列表，并且把终点添加到该列表。 F 重复将终点的父节点添加进列表，所形成的路径即为寻路结果，寻路结束。 图 2.1 A*寻路算法流程 （2） 启发函数 启发函数是A*寻路算法中的一个重要的子函数，该函数的功能是判断当前节点与目标节点之间的预测路径值，并且不考虑障碍物。有3种主流的启发函数，他们的作用和功能都相同，但是在A*寻路算法中所产生的效果有着很大的不同。 图 2.2 三个不同的启发函数的效果 A 曼哈顿启发函数 如图2.2（a），曼哈顿启发函数是最简单的启发函数，它只是计算当前测试节点与终点之间的列数差和行数差的和，即不考虑走对角线。例如：a（1,1） b（2,3），直线的代价为1，则最后得到的结果是3。 B 三角启发函数 如图2.2（b），三角启发函数是计算当前测试节点与终点之间的直线距离，即使用两点之间距离公式。 C 对角启发函数 如图2.2（c），对角启发函数是比较精确的一种启发函数，它会先根据当前测试节点和终点的行数差和列数差的最小值，选择走一个矩形的对角线，然后再走一条直线。 三种启发函数的比较： 曼哈顿启发函数是3个函数中计算方式最简单的一个，但是他忽略了走对角线的情况，因此由曼哈顿启发函数所产生的开启列表的长度会非常大，因为它把很多无关的节点也放入了开启列表中。三角启发函数相对于曼哈顿启发函数，有了一定的改进，但是它忽略了一个重要的问题：合理的路径。由三角启发函数计算出的值并不是路径的真实预测值。因此使用三角启发函数一样会产生比较多的无关节点放入开启列表中。对角启发函数是3个启发函数中最精确的，虽然它在计算单个节点的代价时，是3个函数中最复杂的，开销最大的，但是由它所产生的开启列表的长度是最少的[1]。 (责任编辑：qin) |