A*算法入门浅谈

2017-03-27

A*算法浅析

在玩游戏时，我们遇到过这样的场景：接到一个任务，需要前往某个坐标（例如npc，某个地区），此时我们点击任务列表中的坐标，我们的角色就会自动前往该目标，并且可以自动的规避一些障碍或者死胡同。那么这种AI路径规划技术就是A算法。本文将会简单介绍A算法的概念，并且给出一个最为简单的例子。

概述

A*算法的原理呢，比较简单，这里我们就简单说明下。这个算法呢，是在状态空间上进行搜索的，通过检查某个状态的相邻状态来得到从起始状态到目标状态的最小代价路径。实质上就是反复检查它已经看到的但是还没有搜索到的最有希望的位置。而当目标位置被探索到时，算法终止。

原理

通过维护两张表（OPEN，CLOSED）来标记地图上的未检查状态和已检查状态，对于某个结点，检查其相邻状态，然后选择最好的状态继续检查，直至检查到目标点。

从上面这段描述来看，有没有感觉有点熟悉？dijktra算法。确实，有点像，不过看完下面这张图，你就知道和dj算法哪里不同了。

A*算法维护着一个父状态以保证最终可以从终点通过父结点来回溯找到完整的路径；而dj算法只是求最短路径。
A*算法使用场景比较广泛，可以直接运用至游戏世界中；而dj算法是相对抽象的图场景。
还有一点这个图中体现的不明显。A*算法是启发式搜索，即尽可能朝着目标方向搜索；而dj算法在这种场景下则是一层层向外扩展。

从原理描述，我们可以提一个问题：怎么选择最好的状态？仅仅是离目标点最近吗？显然不行。对于最简单的无障碍物来说，影响不大。而对于有障碍物的情况，那么这种启发式会仅仅考虑到达目标的代价，而忽略了当前已花费的代价，于是尽管路径变得很长，它仍然继续走下去。

所以我们结合一下，共维护两种代价：一种是从开始状态到该状态的代价；另一种则是到达目标位置剩余距离的代价的一个启发式估价函数（例如离目标点最近）。而整个路径的估价值（前面两种代价相加）用以决定下一个要检查的状态即选择相邻状态中最好的那个。

实现

目前A*的思路就很明显了。具体实现思路：closed表初始为空，open表只有初始状态。每次迭代，将open表中最好的状态（即Totalcost最小）取出检查。如不是目标状态，则检查它的相邻状态（如果是新状态，添加必要信息如父状态，CostFromStart，CostToGoal；如已经在open表中且代价更低，则更新该位置的信息如update新的父状态，代价等；如已经在closed表中，忽略）。

伪代码形式如下：

AStarSearch(Location StartLoc, Location EndLoc)
{
    //初始化起点
    StartNode.Loc=StartLoc
    StartNode.CostFromStart=0
    StartNode.CostToGoal=PathCost(StartLoc, EndLoc)
    StartNode.TotalCost=CostFromStart+CostToGoal
    StartNode.parent=NULL
    push StartNode on Open

    while Open is not empty
    {
        //按totalcost排序，将最小代价节点取出
        pop Node from Open

        if (Node is Goal)
        {
            构造路径
            return success
        }
        else
        {
            for each NewNode of Node
            {
                NewCost = Node.GetCostFromStart() + GetCost(Node,NewNode)
                //已存在的就忽略
                if (NewNode is in Closed or (NewNode is in Open and NewNode.CostFromStart 小于等于 NewCost))
                {
                    continue;
                }
                else
                {
                    //在open表中则只更新数据
                    if (NewNode is in Open)
                    {
                        NewNode.Parent=Node
                        NewNode.CostFromStart=NewCost
                        NewNode.CostToGoal=PathCost(NewNode.Loc, EndLoc)
                        NewNode.TotalCost=NewNode.CostFromStart+NewNode.CostToGoal
                    }
                    else
                    {
                        NewNode.Parent=Node
                        NewNode.CostFromStart=NewCost
                        NewNode.CostToGoal=PathCost(NewNode.Loc, EndLoc)
                        NewNode.TotalCost=NewNode.CostFromStart+NewNode.CostToGoal
                        push New Node to Open
                    }                
                }
            }//相邻状态遍历完毕
        }
        push Node to Closed
    }
    return failure
}

我用c++实现了一个最简单的形式，地图为方形栅格，无障碍物，取与目标点的欧几里得距离为启发式估价函数。设相邻状态对角的cost为14，直线的cost为10。

运行结果展示：
我假设的起始点为(5,5).终点为(15,10)

这里的open表我采用的是list，其实有一种更好的方法就是采用优先级队列。这种方式实现起来会更简单，而且效率也会较高。

程序源代码: https://github.com/LZleejean/AStar

这里给大家推荐一个写的特别好的A*算法的文章。http://theory.stanford.edu/~amitp/GameProgramming/

后续将会讨论一些A*算法优化问题。

转载请注明出处