Home » Flash相关 » 关于优化A星寻路算法的新思路:预设高速公路

关于优化A星寻路算法的新思路:预设高速公路

astar

在修改地图编辑器网格尺寸的时候,突然萌生的一个想法,觉得这个思路可以在A星寻路范围比较大的情况下,可以加速搜索。优化思路如下:

1、在地图中,预设一条链路,如上图红色箭头链路所示。
2、白色方框中的两个红点,假设为起点和终点。
3、首先,按照传统的A星寻路,正常搜索。
4、当搜索中,碰到了红色的“高速公路”,则停止搜索,并记录“高速公路入口点”.(如上图,第一条绿色的通道)
5、然后,把终点设置成起点,把原来的起点设置成终点,按照正常的A星算法进行搜索。
6、在搜索中,一旦碰到红色的“高速公路”,则停止搜索,这样又得到一个“高速公路的入口点”(如上图,第二条绿色的通道)
7、然后把两段绿色的通道,以及两个“高速公路入口点”截断的高速公路段连接起来。就得到一条路径。
8、这条三段式路径就是最终结果。中间高速公路段的搜索,就是省下来的效率

 

嗯,会不会有啥坑呢?先记着,改天得空了,再做做试验。

    分享到: