计算机科学

首页 > 计算机科学

A*搜索算法

2018-08-24 14:05:11     所属分类:游戏人工智能

A*搜索算法,俗称A星算法。这是一种在图形平面上,有多个节点的路径,求出最低通过成本的算法。常用于游戏中的NPC的移动计算,或网络游戏的BOT的移动计算上。

该算法综合了Best-First Search和Dijkstra算法的优点:在进行启发式搜索提高算法效率的同时,可以保证找到一条最优路径(基于评估函数)。

在此算法中,如果以表示从起点到任意顶点的实际距离,表示任意顶点到目标顶点的估算距离(根据所采用的评估函数的不同而变化),那么A*算法的估算函数为:

这个公式遵循以下特性:

  • 如果为0,即只计算任意顶点到目标的评估函数,而不计算起点到顶点的距离,则算法转化为使用贪心策略的Best-First Search,速度最快,但可能得不出最优解;
  • 如果不高于顶点到目标顶点的实际距离,则一定可以求出最优解,而且越小,需要计算的节点越多,算法效率越低,常见的评估函数有——欧几里得距离、曼哈顿距离、切比雪夫距离;
  • 如果为0,即只需求出起点到任意顶点的最短路径,而不计算任何评估函数,则转化为单源最短路径问题,即Dijkstra算法,此时需要计算最多的定点;

伪代码

 function A*(start,goal)
     closedset := the empty set                 //已经被估算的节点集合
     openset := set containing the initial node //将要被估算的节点集合,初始只包含start
     came_from := empty map
     g_scorestart := 0                        //g(n)
     h_scorestart := heuristic_estimate_of_distance(start, goal)    //通过估计函数 估计h(start)
     f_scorestart := h_scorestart            //f(n)=h(n)+g(n),由于g(n)=0,所以省略
     while openset is not empty                 //当将被估算的节点存在时,执行循环
         x := the node in openset having the lowest f_score value   //在将被估计的集合中找到f(x)最小的节点
         if x = goal            //x为终点,执行
             return reconstruct_path(came_from,goal)   //返回到x的最佳路径
         remove x from openset      //x节点从将被估算的节点中删除
         add x to closedset      //x节点插入已经被估算的节点
         for each y in neighbor_nodes(x)  //循环遍历与x相邻节点
             if y in closedset           //y已被估值,跳过
                 continue
             tentative_g_score := g_scorex + dist_between(x,y)    //从起点到节点y的距离
 
             if y not in openset          //y不是将被估算的节点
                 tentative_is_better := true     //暂时判断为更好
             elseif tentative_g_score < g_scorey         //如果起点到y的距离小于y的实际距离
                 tentative_is_better := true         //暂时判断为更好
             else
                 tentative_is_better := false           //否则判断为更差
             if tentative_is_better = true            //如果判断为更好
                 came_fromy := x                  //y设为x的子节点
                 g_scorey := tentative_g_score    //更新y到原点的距离
                 h_scorey := heuristic_estimate_of_distance(y, goal) //估计y到终点的距离
                 f_scorey := g_scorey + h_scorey
                 add y to openset         //y插入将被估算的节点中
     return failure
 
 function reconstruct_path(came_from,current_node)
     if came_fromcurrent_node is set
         p = reconstruct_path(came_from,came_fromcurrent_node)
         return (p + current_node)
     else
         return current_node

相关链接

  • 寻路
  • 广度优先搜索
  • 深度优先搜索

外部链接

  • A* 算法简介 (A* Algorithm Brief)

显示全文

取消

感谢您的支持,我会继续努力的!

扫码支持
无需打赏可直接关闭阅读全文
1分,2分不嫌少,钱不钱的无所谓,重要的是你的话语激励我前行!

愿你每天温暖如春!!!


相关推荐