• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

A*算法的C++实现

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

算法的介绍在:http://www.vckbase.com/document/viewdoc/?id=1422

英文地址:http://www.gamedev.net/page/resources/_/technical/artificial-intelligence/a-pathfinding-for-beginners-r2003

本文的代码是完全按照上面的介绍文章写的,包括使用的数据也是文中6*8的矩阵。这只是一个最简单的实现,当数据规模变大后,“开启列表”的策略需要相应调整。除此外感觉算法的模块化和封装写的不好,请路过的读者指教。


#include<iostream>
#include<cmath>
#include<deque>
using namespace std;

const int ROW = 6;
const int COLUMN = 8;
enum status{open,closed,obstacle,unsorted};
struct node{
int row;
int col;
node* father;
int gvalue;
int hvalue;
int fvalue;
status st;
};
node map[ROW][COLUMN];
deque<node*> openTable;
deque<node*> closeTable;

int init(node source,node dest)
{
for(int i=0;i<ROW;i++)
{
for(int j=0;j<COLUMN;j++)
{
map[i][j].row = i;
map[i][j].col = j;
map[i][j].father = NULL;
map[i][j].hvalue = (abs(i-dest.row)+abs(j-dest.col))*10;
map[i][j].st = unsorted;
}
}
//障碍物

  map[1][3].st = obstacle;
map[2][3].st = obstacle;
map[3][3].st = obstacle;

map[source.row][source.col].st = open;
map[source.row][source.col].gvalue = 0;
openTable.push_back(&map[source.row][source.col]);
}

//把当前扩展点周围没有进入“开启列表”的节点加入开启列表,并更新G值

void openNeighbor(int row,int col

{
deque<node*>::iterator it;
for(it=openTable.begin();it<openTable.end();it++)
{
if((*it)==(&map[row][col]))
{
map[row][col].st = closed;
openTable.erase(it);
closeTable.push_back(&map[row][col]);
break;
}
}
//
if(row-1>=0)
{
if(map[row-1][col].st == open)//检查该节点是否有更优的G值

{
if(map[row-1][col].gvalue>map[row][col].gvalue+10)
{
map[row-1][col].gvalue = map[row][col].gvalue+10;
map[row-1][col].father = &map[row][col];
}
}
else if(map[row-1][col].st == unsorted)
{
map[row-1][col].st = open;
map[row-1][col].father = &map[row][col];
map[row-1][col].gvalue = 10+map[row][col].gvalue;
openTable.push_back(&map[row-1][col]);
}
}
//
if(col+1<COLUMN)
{
if(map[row][col+1].st == open)
{
if(map[row][col+1].gvalue>map[row][col].gvalue+10)
{
map[row][col+1].gvalue = map[row][col].gvalue+10;
map[row][col+1].father = &map[row][col];
}
}
else if(map[row][col+1].st == unsorted)
{
map[row][col+1].st = open;
map[row][col+1].father = &map[row][col];
map[row][col+1].gvalue = 10+map[row][col].gvalue;
openTable.push_back(&map[row][col+1]);
}
}
//
if(row+1<ROW)
{
if(map[row+1][col].st == open)
{
if(map[row+1][col].gvalue>map[row][col].gvalue+10)
{
map[row+1][col].gvalue = map[row][col].gvalue+10;
map[row+1][col].father = &map[row][col];
}
}
else if(map[row+1][col].st == unsorted)
{
map[row+1][col].st = open;
map[row+1][col].father = &map[row][col];
map[row+1][col].gvalue = 10+map[row][col].gvalue;
openTable.push_back(&map[row+1][col]);
}
}
//
if(col-1>=0)
{
if(map[row][col-1].st == open)
{
if(map[row][col-1].gvalue>map[row][col].gvalue+10)
{
map[row][col-1].gvalue = map[row][col].gvalue+10;
map[row][col-1].father = &map[row][col];
}
}
else if(map[row][col-1].st == unsorted)
{
map[row][col-1].st = open;
map[row][col-1].father = &map[row][col];
map[row][col-1].gvalue = 10+map[row][col].gvalue;
openTable.push_back(&map[row][col-1]);
}
}
//左上
if(row-1>=0 && col-1>=0&& map[row-1][col].st != obstacle && map[row][col-1].st != obstacle)
{
if(map[row-1][col-1].st == open)
{
if(map[row-1][col-1].gvalue>map[row][col].gvalue+14)
{
map[row-1][col-1].gvalue = map[row][col].gvalue+14;
map[row-1][col-1].father = &map[row][col];
}
}
else if(map[row-1][col-1].st == unsorted)
{
map[row-1][col-1].st = open;
map[row-1][col-1].father = &map[row][col];
map[row-1][col-1].gvalue = 14+map[row][col].gvalue;
openTable.push_back(&map[row-1][col-1]);
}
}
//右上
if(row-1>=0 && col+1<COLUMN && map[row-1][col].st != obstacle && map[row][col+1].st != obstacle)
{
if(map[row-1][col+1].st == open)
{
if(map[row-1][col+1].gvalue>map[row][col].gvalue+14)
{
map[row-1][col+1].gvalue = map[row][col].gvalue+14;
map[row-1][col+1].father = &map[row][col];
}
}
else if(map[row-1][col+1].st == unsorted)
{
map[row-1][col+1].st = open;
map[row-1][col+1].father = &map[row][col];
map[row-1][col+1].gvalue = 14+map[row][col].gvalue;
openTable.push_back(&map[row-1][col+1]);
}
}
//右下
if(row+1<ROW && col+1<COLUMN && map[row+1][col].st != obstacle && map[row][col+1].st != obstacle)
{
if(map[row+1][col+1].st == open)
{
if(map[row+1][col+1].gvalue>map[row][col].gvalue+14)
{
map[row+1][col+1].gvalue = map[row][col].gvalue+14;
map[row+1][col+1].father = &map[row][col];
}
}
else if(map[row+1][col+1].st == unsorted)
{
map[row+1][col+1].st = open;
map[row+1][col+1].father = &map[row][col];
map[row+1][col+1].gvalue = 14+map[row][col].gvalue;
openTable.push_back(&map[row+1][col+1]);
}
}
//左下
if(row+1<ROW && col-1>=0&& map[row+1][col].st != obstacle && map[row][col-1].st != obstacle)
{
if(row+1<ROW && col-1>=0 && map[row+1][col-1].st == open && map[row+1][col].st != obstacle && map[row][col-1].st != obstacle)
{
if(map[row+1][col-1].gvalue>map[row][col].gvalue+14)
{
map[row+1][col-1].gvalue = map[row][col].gvalue+14;
map[row+1][col-1].father = &map[row][col];
}
}
else if(row+1<ROW && col-1>=0 && map[row+1][col-1].st)
{
map[row+1][col-1].st = open;
map[row+1][col-1].father = &map[row][col];
map[row+1][col-1].gvalue = 14+map[row][col].gvalue;
openTable.push_back(&map[row+1][col-1]);
}
}
}

bool findPath(node source,node dest)
{
int minDistence;
int pos;
int rowNum,colNum;
deque<node*>::iterator i;
while(openTable.size()>0)
{
//反复遍历“开启列表”并寻找最下F值的节点

minDistence = numeric_limits<int> ::max();
for(i=openTable.begin();i<openTable.end();i++)
{
if((((node*)*i)->gvalue + ((node*)*i)->hvalue)<minDistence)
{
minDistence = ((node*)*i)->gvalue + ((node*)*i)->hvalue;
rowNum = ((node*)*i)->row;
colNum = ((node*)*i)->col;
}
}
if(rowNum==dest.row && colNum==dest.col)//达到目标节点
{
openNeighbor(rowNum,colNum);
return true;
}
else
{
openNeighbor(rowNum,colNum);
}
}
return false;
}

void printPath(node source,node dest)
{
deque<node*> dq;
node* p = &map[dest.row][dest.col];
while(!(p->row==source.row&&p->col==source.col))
{
dq.push_back(p);
p=p->father;
}
dq.push_back(p);
for(int i=dq.size()-1;i>=0;i--)
{
cout<<"("<<dq[i]->row<<","<<dq[i]->col<<")"<<endl;
}
}

int main()
{
node source,dest;
source.row = 2;
source.col = 1;
dest.row = 2;
dest.col = 5;

init(source,dest);
if(findPath(source,dest))
{
printPath(source,dest);
}
else
{
cout<<"不存在从起点到终点的路径!"<<endl;
}

system("pause");
return 0;
}

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
(转).Net/C#获取字节流编码发布时间:2022-07-13
下一篇:
C#语言的多线程编程,完全是本科OS里的知识发布时间:2022-07-13
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap