【Unity】六边形、菱形的AStar（A*）算法及死路优化

前言

上一篇[一篇文章搞定AStar（A*）算法] 写了一下四边形的A*算法。但是在游戏开发中，战棋类游戏往往并不会采用四边形网格而是采用六边形或菱形网格，一方面六边形或菱形网格看上去更具美感，另一方面六边形或菱形网格可玩性比四边形网格更高。那么本篇再来写一写六边形、菱形网格的A*算法是如何实现的。

六边形A*算法

在开始实现发算法之前，要先弄明白六边形网格的地图应该如何去生成，因为算法也是基于地图的，没有一个正确的地图就无法对算法有一个正确的理解。

在四边形的A*算法中，把x，y分别加1减1就获取到了某点周围的4个邻接节点，代码是这样的：


FindDestNode(currX, currY + 1, xTo, yTo, currNode, openList);
FindDestNode(currX, currY - 1, xTo, yTo, currNode, openList);
FindDestNode(currX - 1, currY, xTo, yTo, currNode, openList);
FindDestNode(currX + 1, currY, xTo, yTo, currNode, openList);

但六边形有六条边，每个格子就有6个邻接节点，无论怎样去安排这六个点的坐标，都不能通过把x，y加1减1的方式全部都获取到。所以要生成一张六边形网格，首先就是要解决六边形网格的坐标问题。

不妨找一张六边形网格观察一下，会发现每行每列的格子都是交错排列的，如果逻辑坐标也能这样交错排列就完美的与网格对应上了。

所以解决这个问题的方法就是把x坐标扩大2倍+y坐标%2，形成奇数行x坐标就进行奇数排列，偶数行x坐标就进行偶排列，y坐标不变。

1	return new Vector2Int(2 * x + y % 2, y);

确定了格子的坐标，获取邻接节点就很容易了

FindDestNode(currX + 1, currY + 1, xTo, yTo, currNode, openList);//右上
FindDestNode(currX - 1, currY + 1, xTo, yTo, currNode, openList);//左上
FindDestNode(currX + 1, currY - 1, xTo, yTo, currNode, openList);//右下
FindDestNode(currX - 1, currY - 1, xTo, yTo, currNode, openList);//左下
FindDestNode(currX + 2, currY, xTo, yTo, currNode, openList);//右
FindDestNode(currX - 2, currY, xTo, yTo, currNode, openList);//左

好了，现在一切准备就绪，来定几个障碍点跑一下试试。

完美！

菱形A*算法

地图坐标的处理和六边形A*算法的处理是完全一样的。

死路优化

有没有想过这两种情景：

玩家在地图上点击了一个点，但这个点却是一个障碍点。
玩家在地图上点击了一个点，但很遗憾，这个点四面楚歌，并没有通往这个点的路线以上这两种情况，玩家操控的角色该如何行动？

显然，在这两个前提下，A*算法不会得出结果，因为在之前的代码里，对于不可行走的格子直接就跳过检测了。没有路线，玩家角色自然就会巍然不动。

我的前上司曾对我说过，一个具有良好体验的游戏，应该做到”逢点击，必响应“，只是因为点击到了一个障碍点就不做出反馈，这实属是犯了大忌啊！

那么苦哈哈的程序员必须要优化：即使点击到了障碍甚至没有通路，也要让玩家角色移动到距离障碍点最近的点。

聪明伶俐的你一定已经发现了，之所以没有通路是因为目标点不可达，所以把目标点替换到它附近的可以到达的点不就行了吗？

既然我已经写到这了，那么这种方法肯定就是不可以的！

确实，当目标点不可达时，从目标点开始广度优先遍历，直到找到一个不是障碍的点来代替原来的目标点这种方法看起来可行，但是，如果代替点也是个空心的呢？它的周围也被障碍团团围住，那不还是死路一条？这样想下去就没完没了了，可能这个广度优先的替代法会执行到遍历完整个地图为止。

其实回过头重新仔仔细细的看一遍算法就会发现，之所以得不出路线的根本原因就是因为那些障碍点直接被跳过了，根本就没有机会被放进openList中等待检测，那么只要打破这个规则：即使目标点不可达，也要把它放进openList中去检测，不就能得到路线了吗？

回想我们的Dijkstra大师对我们的教导：最短路径的求解是不断寻找移动消耗最低的点直到终点。

看到【移动消耗】这个词，你是否已经有了灵感？

没错，这个问题的终极解决办法就是：

我们要打破铁律，我们要为底层劳苦大众发声，障碍点低人一等吗？障碍点也有进入openList的资格！
但障碍点终归是障碍点，在openList里它终归是个异类，即使允许它进入openList，它也是最后一个被检测的，只有实在没有其他选择的时候，A*才会垂怜它一下。

把障碍点也放进openList，但它的移动消耗G是无穷大！这样一来，在没有任何通路的情况下，A*会回头来检测从这些障碍点身上通过是否能到达终点，无论如何都会给玩家一条路走。

private void FindDestNode(int x, int y, int xTo, int yTo, Node currNode, List<Node> openList)
{
    if (x >= 0 && x / 2 < m_MapWidth && y >= 0 && y < m_MapHeight)
    {
        int index = x / 2 + y * m_MapWidth + 1;
        int toIndex = xTo / 2 + yTo * m_MapWidth + 1;
        int mulity = 1;

        if (m_MapData[index - 1] == -1)
        {
            mulity = 1000;//如果是障碍点，把它的移动消耗G扩大一千倍
        }

        Node temp = openList.Find(obj => obj.index == index);

        if (temp == null)
        {
            temp = new Node(index, currNode, (currNode.g + 1) * mulity, GetDistance(index, toIndex));
            openList.Add(temp);
        }
        else if (temp.isOpen && temp.f > currNode.g + 1 + temp.h)
        {
            temp.g = (currNode.g + 1) * mulity;
            temp.f = temp.g + temp.h;
        }
    }
}

但路是有了，那回溯的时候不就把障碍点以及后面那些进不去的地方也算进来了吗？其实这个就更简单了，回溯的时候一但发现障碍点就把该障碍点以及前面的所有节点全部干掉就可以了。

while (currNode != null)
{
    if (m_MapData[currNode.index - 1] != -1)
    {
        m_QueuePath.Enqueue(currNode.index);
        currNode = currNode.parent;
    }
    else if (m_QueuePath.Count > 0)//遇到障碍点则把之前入队的点全部出队
    {
        m_QueuePath.Dequeue();
    }
    else
    {
        currNode = currNode.parent;
    }
}