大家好，欢迎来到IT知识分享网。
什么是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”); }
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://yundeesoft.com/55708.html
