游戏中A*寻路算法的优化与改进

 - by Hector

游戏中A*寻路算法的优化与改进

上一遍文章中,我对A*算法进行了实现,并用跳步算法进行了优化。在游戏项目中,根据游戏的特点有很多优化的方式,可以选择使用。

在游戏中,一般将地图划分为一个一个的格子,将这些格子当做节点,进行寻路。

选择适当的地图大小和格子大小

  1. 如果地图太大,进行A*算法难免耗时过久,因此可以将地图划分为几部分,划分为阶段目的地,进行分段寻路。
  2. 格子的大小会是A*的消耗成倍增长,在不影响寻路效果的情况下,尽量让格子尽可能的大一些。

可以直接到达的点避免进行A*寻路

如果起点和终点直接并没有阻碍,则可以直接通过,避免进行A*寻路。具体做法:

  1. 计算起点和终点之间的直线方程y = a + bx,将格子的边界带入方程,得到边界点。
  2. 寻找边界点的格子,看是否可通过(可能有2,4个格子)。
  3. 两个边界点可能跨过一个格子,那么这个格子可能就漏掉了,可以根据直线是否大于45度来确定是由x得到y,还是由y得到x。

这里有详细介绍的:http://www.iamsevent.com/post/33.html

解决目的地不可到达造成的角色不移动

如果目的地不能到达,A*无法寻路,角色就无法移动,这对于游戏来说是很不合理的,最好的方式是走到离目的地最近的可通行的点上去。

解决方法一:将不可通行点设置为通行代价极高的点

解决这个问题很简单,原来不可通行的点直接被我们排除了,我们可以将这些不可通行的点通过代价设置很大就可以放到open列表中去,这样A*寻路到最后实在找不到通行的节点,会硬着头皮走这些不可能通过的点。这样我们总能找到一条可通行的路径。

最后,当角色移动时,如果通过的节点是不通行的,角色停止移动就达到我们的目的了。此方案精确,但是加入了不可通行的节点,A*算法的代价变大很多。

解决方案二:寻找替代点

假如,目的节点是草地(不可通行的),我们可以找个离目的节点和起始节点最近的节点,作为替代的目的地。寻找目的节点的方法如下:

  1. 寻找目的节点周围第一圈所有可通行的节点,将节点放在一个数组。
  2. 若第一圈一个可通行的节点都没有,则寻找第二圈,依次类推。
  3. 比较可通行的节点中最接近起始节点的节点作为替代目的地。

弊端:寻找替代点在孤岛回字形的目的节点中会失效。

弗洛伊德路径平滑算法

参考文章:http://www.iamsevent.com/post/34.html
当寻找到路径之后,进行路径的平滑处理。

  1. 合并共线的路径节点。
  2. 尽可能的去除多余的拐点。

合并共线

A,B,C三个节点,如果AB,与BC,斜率一样,则可以由A到C,去除B点。

比如A~Z点,循环处理AB,BC,CD…YZ节点,一遍循环则可以处理完毕了。

去除拐点

A,B,C,D四个节点,若,AD直接不存在障碍物,则去除B,C两点。算法如下:

for(int i= len-1; i>=0; i--)
{
    for(int j = 0;j<= i-2;j++)
    {
        if(Node[i]和Node[j]直接没有障碍物)
        {
            1. 去除i,j之间所有的点
            2. 重新计算len
            3. i = j;
            break;
        }
    }
}

ps: 以上方案并不是所有游戏必须的,根据游戏情况灵活运用。

Leave a comment