游戏中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: 以上方案并不是所有游戏必须的，根据游戏情况灵活运用。