什么是A-star算法

A*（A-Star)算法是一种静态路网中求解最短路最有效的方法，俗称A星算法。这是一种在图形平面上，有多个节点的路径，求出最低通过成本的算法。常用于游戏中的NPC的移动计算，或线上游戏的BOT的移动计算上。公式表示为：f(n)=g(n)+h(n)，其中f(n)是节点n从初始点到目标点的估价函数，g(n)是在状态空间中从初始节点到n节点的实际代价，h(n)是从n到目标节点最佳路径的估计代价。

A-star算法的原理

• 先引入二个概念：

节点(Node)：每个格子都可以称为节点。

代价(Cost)：描述角色移动到某个节点时所走的距离（或难易程度）。

• 三种基本的估价算法(也称估价公式)，其算法示意图如下：

对于“曼哈顿算法”，，笔直的走，然后转个弯，再笔直的继续。

“几何算法”的最好解释就是“勾股定理”，算出起点与终点之间的直线距离，然后乘上代价因子。

“对角算法”综合了以上二种算法，先按对角线走，一直走到与终点水平或垂直平行后，再笔直的走。

• 在计算机中我们将地图表现为单元格，分可走单元格和不可走单元格。，必须要让计算机“有选择地走”。

若以当前单元格为起点（称为父单元格，它的周围有八个方向），下一步走哪呢？

这时就得给下一步的单元格（称为子单元格）进行“估价”。

“估价”可用估价函数来实现。

入门级的估价函数是这样的：

终点到目前点的估计代价＝终点至当前点的直线距离

于是下一步的代价可以这样算

代价＝起点到当前点的实际步数（通过一个变量累加可以直接得到）+ 终点到目前点的估计代价

然后把估价后的单元格放入“待考察表”

从待考察表中取代价最小的单元格作为起点，对它周围8个方向的单元格进行估价，然后把它放入“已考察表”。

若对一个单元格估价时，发现它已经在“待考察表”中则比较该单元格原先的估价和当前的估价，保留小的估价，并更新其父单元格属性。

不断重复以上过程，直到在“待考察表”中取出的单元格是终点单元格为止，若“待考察表为空”则表示找不到路径。

到达终点单元格后，通过其“父单元格”属性，一直找到起点，便构成一条路径。

两个例子：

Enter the map's filename:
b.txt
Rows=7
Cols=13
. . . . . . . . . . . . .
. . . . . . x . . . . . .
. . . x x x x . . . . . .
. . . . . . x . . . . . .
. . . x x x x . . . . . .
. . . . . . x . . . . . .
. . . . . . . . . . . . .
Set the start point ( x , y ):
5 3
Set the end point ( x , y ):
12 3
Steps:
12,3
11,2
10,1
9,0
8,0
7,0
6,0
5,0
4,0
3,1
2,2
3,3
4,3
5,3
Rows=7
Cols=13
. . . . * * * * * * . . .
. . . * . . x . . . * . .
. . * x x x x . . . . * .
. . . * * * x . . . . . *
. . . x x x x . . . . . .
. . . . . . x . . . . . .
. . . . . . . . . . . . .
===========================
Enter the map's filename:
a.txt
Rows=7
Cols=7
. . . . . . .
. x x x . . .
. . . x . x .
. . . x . x .
. . . . . x .
. . . . . x .
. . . . . x .
Set the start point ( x , y ):
0 0
Set the end point ( x , y ):
6 6
Steps:
6,6
6,5
6,4
6,3
6,2
5,1
4,0
3,0
2,0
1,0
0,0
Rows=7
Cols=7
* * * * * . .
. x x x . * .
. . . x . x *
. . . x . x *
. . . . . x *
. . . . . x *
. . . . . x *

C++代码

• 1. 评价函数

以当前状态下各将牌到目标位置的距离之和作为节点的评价标准。距离的定义为：“某将牌行下标与目标位置行下标之差的绝对值 + 列下标与目标位置列下标之差的绝对值”。距离越小，该节点的效果越好。某个状态所有将牌到目标位置的距离之和用“h值”表示。

• 2. 主要函数

2.1 countH（state & st）;

countH函数功能是计算st状态的h值。

计算过程中将会用到rightPos数组，数组里记录的是目标状态下，0~9每个将牌在九宫格里的位置（位置 = 行下标 * 3 + 列下标）。

2.2 f（state * p）;

f()=h()+level

2.3 look_up_dup(vector<state*> & vec, state * p);

在open表或close表中，是否存在指定状态p，当找到与p完全相等的节点时，退出函数。

2.4 search(state & start)；

在open表不为空时，按f值由小到大对open表中元素进行排序。

调用findZero()函数找到0值元素的位置。空格可以向上下左右四个方向移动，前提是移动后不能越过九宫格的边界线。确定某方向可走后，空格移动一步，生成状态p’。

此时，检查open表中是否已有p’，若有，更新p’数据；检查close表中是否已有p’，若有，将p’从close表中删除，添加到open表中。 重复的执行这个过程，直到某状态的h值为零。

2.5 dump_solution(state * q)；

在终端输出解路径。

// A*算法 八数码问题

#include “stdafx.h”

#include<iostream>

#include<vector>

#include<time.h>

#include<algorithm>

using namespace std;

const int GRID = 3; //Grid表示表格的行数(列数)，这是3*3的九宫格

int rightPos[9] = { 4, 0, 1, 2, 5, 8, 7, 6, 3 }; //目标状态时，若p[i][j]=OMG,那么3*i+j = rightPos[OMG]

struct state{

int panel[GRID][GRID]; int level; //记录深度 int h;

state * parent;

state(int level) :level(level){}

bool operator == (state & q){

//判断两个状态是否完全相等（对应位置元素相等），完全相等返回true,否则返回false

for (int i = 0; i<GRID; i++){ for (int j = 0; j<GRID; j++){

if (panel[i][j] != q.panel[i][j]) return false; } }

return true; }

state & operator = (state & p){ //以状态p为当前状态赋值，对应位置元素相同

for (int i = 0; i<GRID; i++){ for (int j = 0; j<GRID; j++){ panel[i][j] = p.panel[i][j]; } }

return *this; } };

void dump_panel(state * p){ //将八数码按3*3矩阵形式输出 for (int i = 0; i<GRID; i++){ for (int j = 0; j<GRID; j++)

cout << p->panel[i][j] << ” “; cout << endl; } }

int countH(state & st){ //给定状态st，计算它的h值。

int h = 0;

for (int i = 0; i<GRID; i++){ for (int j = 0; j<GRID; j++){ if (st.panel[i][j] != 0)

h += abs(rightPos[st.panel[i][j]] / GRID – i) +

abs(rightPos[st.panel[i][j]] % GRID – j);

//h=各个将牌与其目标位置的距离之和.距离定义为：行下标之差的绝对值+列下标之差的绝对值。 } }

return h; }

int findZero(state & st){ //找到零值元素，返回其在表中的位置

for (int i = 0; i<GRID; i++){ for (int j = 0; j<GRID; j++){ if (st.panel[i][j] == 0) return i * 3 + j; } } }

int f(state * p){ //计算并返回f()值，即h值+level return countH(*p) + p->level; }

bool compare_state(state * p, state * q){ //比较两个状态的f值 return f(p) > f(q); }

vector<state *> open_table; //open表 vector<state *> close_table; //close表

vector<state*>::iterator look_up_dup(vector<state*> & vec, state * p){ vector<state*>::iterator it_r = vec.begin(); for (; it_r<vec.end(); it_r++){ if ((*(*it_r)) == *p){ break; } }

return it_r; }

state * search(state & start){ //A*算法进行搜索

int level = 0;

open_table.push_back(&start); int count = 0;

while (!open_table.empty()){

sort(open_table.begin(), open_table.end(), compare_state); //对open表中的元素进行排序

state * p = open_table.back(); open_table.pop_back();

if (countH(*p) == 0)

return p; //所有将牌到达目标位置，搜索过程结束 level = p->level + 1;

int zeroPos = findZero(*p);

int x = zeroPos / 3; //空格的行下标 int y = zeroPos % 3; //空格的列下标

for (int i = 0; i<4; i++){ //上下左右四个方向 int x_offset = 0, y_offset = 0; switch (i){

case 0:x_offset = 0, y_offset = 1; break; //右 case 1:x_offset = 0, y_offset = -1; break;//左 case 2:x_offset = 1, y_offset = 0; break;//上 case 3:x_offset = -1, y_offset = 0; break;//下 };

if (x + x_offset<0 || x + x_offset >= GRID || y + y_offset<0 || y + y_offset >= GRID){ continue;

//若移动一步后，将超出上/下/左/右边界，则这个方向不可走，尝试下一个方向

}

state * q = new state(level); //这个方向可走，扩展下一个节点

q->parent = p; *q = *p;

q->panel[x][y] = q->panel[x + x_offset][y + y_offset]; q->panel[x + x_offset][y + y_offset] = 0;//空格沿这个方向移一步

bool skip = false;

vector<state *>::iterator dup = look_up_dup(open_table, q); //若q已在open表中，则对open表中的信息进行更新

if (dup != open_table.end()){ if (f(q) < f(*dup)){

(*dup)->level = q->level; (*dup)->parent = q->parent; }

skip = true; }

dup = look_up_dup(close_table, q);

if (dup != close_table.end()){ //若q已在close表中，且f值比原值小，

if (f(q) < f(*dup)){ //则将q从close表清除，加入open表

delete *dup;

close_table.erase(dup); open_table.push_back(q); skip = true; } }

if (!skip){

open_table.push_back(q); } }

close_table.push_back(p); } }

void dump_solution(state * q) //输出解路径 {

vector<state *> trace; while (q){

trace.push_back(q); q = q->parent; }

int count = 0;

while (!trace.empty()){

cout << “Step ” << count << ” :^-^=^-^=^-^=^-^=^ ^=^-^=^-^=^-^=^-^=^-^=^@\n”;

dump_panel(trace.back());

cout << “h: ” << countH(*trace.back()) <<“\tg:”<<count<< “\tf: ”

<< f(trace.back()) << endl << endl; trace.pop_back(); count++; } }

int main() {

state p(0); state *q;

p.panel[0][0] = 2;//设置初始状态 p.panel[0][1] = 1; p.panel[0][2] = 6; p.panel[1][0] = 4; p.panel[1][1] = 0; p.panel[1][2] = 8; p.panel[2][0] = 7; p.panel[2][1] = 5; p.panel[2][2] = 3;

p.parent = NULL; q = search(p);

dump_solution(q);

system(“pause”); }