对于地图信息已知且各障碍位置固定的情况下,可以将常用的位置及其之间的路径信息保存,然后寻路时分别找到离开始点,结束点较近的位置,分别进行寻路,再将路径组合得到最终路径,不过此路径可能较正常寻路出的路径较远但寻路用时较少。
简单寻路中启发函数公式:
f(寻路消耗)= g(实际消耗也可以说离起点距离)+ h(预计消耗也可以说离终点距离)
一般情况下,h距离使用欧几里得距离公式,即h=
但是对于四方向寻路时(只能前后左右寻路,不能斜角寻路),
h可以使用曼哈顿距离公式,即h = | x1 - x | + | y1 - y |
当对于八方向寻路时,h可以使用切比雪夫距离公式,即h = max(| x1 - x |, | y1 - y |)
简单情况下,寻路消耗是由实际消耗与预计消耗1:1相加得到,但是实际情况是预计消耗是预计值,它不等于真实的距离终点的值,此时可以增加一个系数w,将寻路消耗公式变为
f = g + w * h
此时可以通过修改w的值来改变实际消耗与预计消耗的混合比,比如当w > 1时,寻路消耗会更优先考虑当前路径预计造成的代价,当w < 1时,寻路会更优先考虑当前路径已造成的代价。
在开启列表中寻找寻路消耗最小点时,一般情况下避免不了寻路消耗一样的点的出现,此时就需要对这些点进行取舍,而取舍的方式就是为预估函数增加一个微小的偏移量p,这个偏移量p能起作用的原因是:当某两个节点的启发函数值相同时,我们希望优先判断那个距离终点更近的节点,而距离终点近也就意味着其预估函数值更小,所以,如果我们为预估函数增加一个小偏移量p(p甚至可取0.1%左右),就会使得距终点近的的节点的启发函数值更小,就会被优先选择。因此,我们可以将启发函数进一步优化为如下形式
f = g + w * h + p * h = g + (w + p) * h
寻路有时会出现频繁转向的路径,虽然该路径确实是消耗最小的路径,但是也会存在其他消耗一样的路径且没有过多转向。结合实际,其实转向也是有消耗的,所以可以增加一个值e用来表示转向消耗,当没有转向时e = 0,当转向时e = 1,此时启发函数变为
f = g + (w + p) * h + e
开启列表在寻路中是一个会被频繁插入数据并排序的一个列表,若每次都插入数据再排序会十分消耗性能,所以在插入数据时可以先进行数据比较,再插入数据,就能一定程度上优化开启列表。
寻路是一个重复计算一个点周围所有点距离起点和终点距离的过程,但有时并不需要将周围所有点都纳入计算,比如终点在起点右上方时,起点左下角的个别点其实可以不进行计算,因为它们的消耗一般情况下都会更大,此时循环对这些点进行计算会浪费很多时间,所有在计算时可以舍弃部分点。
但有时舍弃相邻的部分点也会导致寻路得到的路径并不是最优路径,比如起点被障碍包围,只在被舍弃的周围点附近留有缺口时,寻找到的路径就会绕路,这时旧还需优化(但本人没找到好的优化方案^_^)
下面是使用unity实现的可视化A星寻路优化工程
除了上述几点外,A星寻路还有其他的优化方案,但我在工程中只实现上述几种,并没有实现存储常用位置间的路径信息的优化,而且A星寻路有时就是找不到最优路径,尤其在障碍点较复杂时比如在我工程中的情况,所以还有待优化