Astar Algorithm

参考文献：https://www.gamedev.net/reference/articles/article2003.asp
这篇东西写的贼好。

介绍

A*算法主要用于寻路，比如游戏中的自动寻路系统。比其他算法优越的地方就在于他缩小了搜索空间。像迪杰斯特拉弗洛伊德算法这些都只是考虑了到原点的距离，他没有考虑到终点的代价，而且求出了很多不太必要的信息。如果我们仅仅只是求两点的距离，就没有必要用迪杰斯特拉和弗洛伊德了，因为他们把原点到所有点的距离都求了出来。
还有一些其他的算法比如广度和深度搜索，这些算法的都是遍历可能的空间，而深度优先不适用于最短路径的搜索，因为深度优先求出来的路径和代码编写的搜索方向有关系，也就是说深度优先搜索的路径有随机性。所以深度优先如果要做最短路径就只能遍历所有的路径了。广度优先搜索适用于最短路径，但是搜索空间还是很大的，比如如下的场景：

@是起点和终点，#是墙，如果是广度优先，需要把以起点到终点为半径的圆都搜索一遍。

这样的复杂度还是挺大的。为了能够缩小搜索区域，我们可以考虑把对终点的代价也计算在内。

算法细节

和迪杰斯特拉类似，迪杰斯特拉是寻找离原点最近的点，那么我们只需要加上终点代价即可，于是我们定义代价函数F = G + H，G是原点的距离，用勾股定理可以知道斜方向的距离是14，正方向的距离是10，乘10方便计算。H是到达原点的距离，用哈密顿距离即可。
事实上这样的估计只是一种粗略估计，求出来的就算不是最短路径那也和最短路径差不多了。如果存在场景使得哈密顿距离误差很大的话那么求出来的就未必是最短路径了。
需要注意的是，对于终点的计算，方块都是固定的，但是对于G的计算有些特别，讲道理每一方块到原点距离都是一样的，但是如果一直用这样用勾股定理计算，麻烦不说，并且在搜索过程中就没办法调整路径了。
比如，我们要计算路径，自然要保存父节点

如图，当前我们在绿色节点右下角的蓝色节点处，但是问题来了，蓝色节点左下角，也就是方块F值是88的节点如果按照勾股定理计算G就是20，但是目前由于这个节点是当前蓝色节点发现的，所以他的父节点是当前蓝色节点，但是事实上这并不是离原点最近的指向，他应该指向上才是最近的。我们就没办法更新这些父子关系了。
于是我们规定，G节点不再直接计算，方块上下左右移动增加10，斜方向移动增加14即可，这样就可以保留从父节点再到原点的G值了，在搜索过程中就可以对比G值更新父节点。
如图：

当前在节点2，我们通过节点2搜索得到的F=88的节点，此节点G为28（左上角是F值，左下角是G值，右下角是H值）。但是当我们搜索到节点3的时候，3也发现了F=88的节点，这个时候发现从3号更短，与是把F=88的节点父亲设置为3号。这样就达到了更新的目的。如果没有搜索到3号，那么说明这些节点太远了，没有用。
定义了代价函数后就是如何搜索了。
首先规定搜索规则，上下左右可以搜索，斜方向也可以搜索，但是斜方向的搜索不能被正向的挡住。比如往右上角移动，那么右方向和上方向就不可以有阻碍。
以#为墙为例子：
。# 。 | 。# 。 | 。 。 。
。起 # |。起 。 | 。起 #
上面的情况都不可以进行右上角的移动，以此类推即可。
准备openList和endList，openList用来存放候选节点，也就是最短路径的候选值，endList用来存放已经搜索完成的节点。
初始情况，我们把起点丢进openList里面，每一次从openList里面取出F值最小的节点，然后把这个节点上下左右斜方向都进行扩展，把扩展出来的候选值计算好F放进openList里面，这个时候从openList拿出的节点已经完成搜索，我们只需要加入endList即可。不断重复这个循环，从openList中取值。
在从openList取出值并扩展的获得候选点的时候有3个情况。如果扩展的候选点在endList里面了，那就不用管了，如果不在endList里面在openList里面，说明他已经有一个父亲和一个从父亲计算来的G了，这个时候你就要判断从当前节点到这个候选点是不是更近，也就是G是不是更小的，如果是更小的就替换父亲，替换G。如果不在openList也不在endList，那就计算FGH添加进openList即可。
流程非常简单。
接下来就是实现代码。

代码实现

class node {
private:
    int x, y;
    node *parent;
    double G;
    double H;
    double F;

节点node信息，getset方法不贴了。

    int nRow;
    int nColumn;
    pair<int, int> beginning;
    pair<int, int> ending;
    vector<pair<int, int>> walls;
    vector<string> maps;
    vector<bool> visited_open;
    vector<bool> visited_end;
    //F G node
    vector<node *> openList;
    vector<node *> endList;

map中存储数据结构。visited_open和visited_end是为了防止搜索重复遍历open和end列表。

    void generateMap() {
        vector<string> results;
        results.resize(nRow);
        visited_open.resize(nRow * nColumn);
        visited_end.resize(nRow * nColumn);
        for (int i = 0; i < nRow; i++) {
            for (int j = 0; j < nColumn; j++) {
                results[i][j] = '.';
            }
        }
        for (int i = 0; i < walls.size(); i++) {
            results[walls[i].first][walls[i].second] = '#';
        }
        results[beginning.first][beginning.second] = '@';
        results[ending.first][ending.second] = '@';
        maps = results;
    }

生成地图。
主算法：

        node *begin = new node(beginning.first, beginning.second, nullptr);
        begin->setF(0);
        begin->setG(0);
        begin->setH(0);
        //起始点丢进openlist里面,更新最小点
        openList.push_back(begin);
        visited_open[begin->getX() * nColumn + begin->getY()] = true;

可以把起点丢进open列表，begin->getX() * nColumn + begin->getY()是这个点的编号，把矩阵拉长变成一维编号留下的值。

        while (!openList.empty()) {
            int index = getLowestF();
            node *current = openList[index];

            //cout << current->getX() << " " << current->getY() << endl;

            openList.erase(openList.begin() + index);

            endList.push_back(current);
            visited_end[current->getX() * nColumn + current->getY()] = true;
            if (current->getX() == ending.first && current->getY() == ending.second) {
                return;
            }

            addPoint(current);
        }
    }

首先遍历获取最小的F值，从open取出并加入end中，别忘了维护visited，其次把扩展的候选点加入open。

代码效果

初始地图。

箭头即是最短路径。
我们来看看搜索空间：

*号是加入open的节点，也就是参与搜索的节点，可以看到搜索空间比广度优先几乎少了一半。

算法优化

很明显，这个算法优化的空间还是比较大的，之前在openList就考虑过能不能用优先队列，因为在迪杰斯特拉算法中有优先队列是有很大的效率提升，但是问题就在于，在候选点存在openList列表的时候，我们需要进行更新父节点，这个时候要搜索openList了，C++的优先队列没有提供遍历功能，总不能全部倒出来再塞回去吧。所以如果使用优先队列，就需要考虑如何在优先队列中获取特点元素并完成动态更新的过程，因为你找到这个节点如果更新了之后，优先队列需要再动态的排序一次的。而具有让priorityqueue能动态排序的我目前就知道pair。不知道其他的语言优先队列能不能遍历，C++可以自己实现一个二叉堆即可。
其次，代价还是对于算法影响是非常大的，当H是0的时候，就完全退化成了迪杰斯特拉算法，因为他之和原点距离有关了。当H比实际代价要小上许多时，我们的搜索复杂度就会增加，因为这个时候主要取决于G，于是就会在原点周围不断扩展，搜索的点会非常多。
我们上面的例子中代价都是乘10，H的代价也是乘10的，一个格子就是10，我们现在缩减十倍，对于G来说，上下左右+10，斜方向加14，而对于H来说一格只加1，我们看看搜索空间的变化。

可以看到基本就退化成了广度优先。
当H原大于实际代价的时候，这就有一点随机性了，得看你障碍物的位置和你代码编写遍历方向的顺序有关系了。因为这个时候主要取决于H的变化。这就有点像BFS了。
所以按照这个方向优化，我们可以考虑让H代价更准确一点，修改代价函数F = G + W * H。W可以影响H的权重，这里的W可能要根据不同场景进行设置，可以设置所有节点都一样，也可以设置没个节点都不同。或许可以随着搜索的增加不断的增大H，使得搜索空间成一个哑铃的形状。当然这只是个想法，是不是还得实验一下。

代码：https://github.com/GreenArrow2017/PracticeAlgorithm/tree/master/Astar