自定义词典_自定义情感词典 - CSDN

• 虽然网上已经有许多A星算法实现，但大多过于繁琐。这是实现的精简版，必须要吐槽一下C++对象的指针和引用，还有那让人蛋疼的while和递归居然是两码事（这bug调了我一晚上）。不行你试试，把下面的start()的方法改...

虽然网上已经有许多A星算法的实现，但大多过于繁琐。这是实现的精简版，必须要吐槽一下C++对象的指针和引用，还有那让人蛋疼的while和递归居然是两码事（这bug调了我一晚上）。不行你试试，把下面的start()的方法改下成while() 注释可以参考http://blog.csdn.net/liucanlong/article/details/10334035

#include "iostream"
#include "set"
#include "stdlib.h"
#include "vector"
#define N 1000
using namespace std;
class Node{
public:
int x;
int y;
int g;
int h;
int f;
Node *parent;
Node(int,int);
Node(){}
bool operator <(const Node &other)const{
if(this->f!=other.f){
return this->f<other.f;
}else {
return true;//允许相同
}

}
};
set<Node> full;
set<Node> openL;
set<Node> closeL;
vector<Node> resultL;
int map[N][N]={ 	{0,0,0,0,0,0,0,0,0,0},

{0,0,0,0,1,0,0,0,0,0},

{0,0,0,0,1,0,0,0,0,0},

{0,0,0,0,1,0,0,0,0,0},

{0,0,0,0,1,0,0,0,0,0},

{0,0,0,0,1,0,0,0,0,0}};
int col;
int row;
int line = 10;
int xie = 14;

int isContains(int x,int y,set<Node> *pL){
set<Node>::iterator iter = pL->begin();
for(int i=0;iter!=pL->end();iter++,i++){
if(iter->x==x&&iter->y==y)
return i;
}
return -1;
}
int isContains(int x,int y,vector<Node> *pL){
vector<Node>::iterator iter = pL->begin();
for(int i=0;iter!=pL->end();iter++,i++){
if(iter->x==x&&iter->y==y)
return 1;
}
return 0;
}
int countH(int x,int y,int endX,int endY){
int xSub = abs(x-endX);
int ySub = abs(y-endY);
int minXY = xSub>ySub?ySub:xSub;
return minXY*xie+abs(xSub-ySub)*line;
}

void check(int x,int y,int cost,Node *parent,int endX,int endY){
if(x<0||x>=row||y<0||y>=col) return;
Node node(x,y);
node.parent = parent;

node.g = parent->g+cost;
if(isContains(x,y,&closeL)!=-1) return;
if(map[x][y]==1){
closeL.insert(node);
return;
}
int index = isContains(x,y,&openL);
if(index!=-1){
set<Node>::iterator iter = openL.begin();
for(int i=0;i<index;i++)
iter++;
if(node.g<iter->g){
node.f = node.g+iter->h;
node.h = iter->h;
openL.erase(iter);
openL.insert(node);
}
}else{
node.h = countH(x,y,endX,endY);
node.f = node.h+node.g;
openL.insert(node);
}
}
void getPath(Node *node){
while(node->parent==NULL){
resultL.push_back(*node);
return;
}
getPath(node->parent);
resultL.push_back(*node);
}

int start(int endX,int endY){
if(openL.empty()) return 0;
set<Node>::iterator iter = openL.begin();

Node n = *iter;
if(n.x==endX&&n.y==endY){
getPath(&n);
return 1;
}
check(n.x,n.y-1,line,&n,endX,endY); //左
check(n.x,n.y+1,line,&n,endX,endY); //右
check(n.x-1,n.y,line,&n,endX,endY); //上
check(n.x+1,n.y,line,&n,endX,endY); //下
check(n.x-1,n.y-1,xie,&n,endX,endY); //左上
check(n.x-1,n.y+1,xie,&n,endX,endY); //右上
check(n.x+1,n.y-1,xie,&n,endX,endY); //左下
check(n.x+1,n.y+1,xie,&n,endX,endY); //右下
closeL.insert(n);
openL.erase(iter);
return start(endX,endY);
}

int search(int startX,int startY,int endX,int endY){
if(map[startX][startY]==1||map[endX][endY]==1) return -1;
Node *root = new Node(startX,startY);
openL.insert(*root);
return start(endX,endY);
}

int main(){
col = 10;
row = 6;
int flag = search(3, 0, 4, 7);
if(flag==0){
cout<<"no find!"<<endl;
}else if(flag==-1){
cout<<"format error"<<endl;
}else if(flag==1){
for(int i=0;i<row;i++){
for(int j=0;j<col;j++){
if(map[i][j]==1) cout<<"#";
else{
if(isContains(i,j,&resultL)){
cout<<"@";
}else{
cout<<" ";
}
}
}
cout<<endl;
}
}
system("pause");
return 0;
}

Node::Node(int x,int y){
this->x = x;
this->y = y;
this->g = 0;
this->h = 0;
this->f = 0;
this->parent = NULL;
}

展开全文
• A*寻路算法C++实现，共两个文件 astar.h astar.cpp 代码如下 // astar.h BEGIN #ifndef ASTAR_H #define ASTAR_H #include #include #include // 地图格子数据结构 struct grid_t { int ...

A*寻路算法的C++实现，共两个文件 astar.h astar.cpp

代码如下

// astar.h BEGIN

#ifndef ASTAR_H
#define ASTAR_H

#include <stdio.h>
#include <vector>
#include <set>

// 地图格子数据结构
struct grid_t
{
int id; // grid id {1,100}
int x; // x location {0,9}
int y; // y location {0,9}
int g; // g value 10{front, back, left, right}
//14{east_north, east_south, west_east, west_south}
int h; // h value ( diffx + diffy ) * 10
int block; // if available
int total; // total = g + h*10

void show(){
printf("{%d,%d,%d,%d,%d,%d,%d}, ", id, x, y, g, h, block, total);
}
};

// 地图格子信息 规格 10*10
extern std::vector<grid_t> map;

// 地图初始化 大小: 10*10 以左下角(0,0)作为坐标起点
void init_map();

//经过的格子编号 因有先后顺序 因此需要用vector存储
extern std::vector<int> path_grid_id;
grid_t* find(int x, int y);
#endif

// astar.h END

// astar.cpp BEGIN

#include <sys/time.h>
#include <stdlib.h>
#include <time.h>
#include "astar.h"

std::vector<grid_t> map;
std::vector<int> path_grid_id;

int start = 12;
int end = 78;

int abs(int val)
{
if( val >= 0 ){
return val;
}
return -val;
}

//grid_t* end_grid = &map[end-1];
grid_t* end_grid = NULL;
void init_map()
{
map.clear();
for( int i=1; i<=100; i++ ){
grid_t grid;
grid.id = i;
grid.x = (i-1) % 10;
grid.y = (i - 1) / 10;
grid.h = 0;
grid.g = 0;
grid.block = 0;
grid.total = 0;

// 设置障碍
if( grid.x==4 && grid.y >= 3 && grid.y <= 6 ){
grid.block = 1;
}

map.push_back(grid);
}
}

struct id_val_t
{
int id;
int val;
};

grid_t* find(int x, int y)
{
if( x < 0 || x > 9 ){
return NULL;
}
if( y < 0 || y > 9 ){
return NULL;
}
int id = y*10 + (x+1);
if( id <= 0 || id > map.size() ){
return NULL;
}
return &map[id-1];
}

grid_t* find_next_grid(int id)
{
if( id <= 0 || id > 100 ){
return NULL;
}
grid_t* grid = &map[id-1];

// 8 grid around
//path_grid_id.push_back(id);

// all ready find the path
for( int i=0; i<path_grid_id.size(); i++ ){
if( path_grid_id[i] != end ){
continue;
}
return NULL;
}

std::vector<id_val_t> vec_id_val;

int loc[][2] = {
{grid->x+1, grid->y},
{grid->x-1, grid->y},
{grid->x, grid->y+1},
{grid->x, grid->y-1},
{grid->x+1, grid->y+1},
{grid->x+1, grid->y-1},
{grid->x-1, grid->y+1},
{grid->x-1, grid->y-1}
};

for( int i=0; i<8; i++ ){
int loc_x = loc[i][0];
int loc_y = loc[i][1];
grid_t* find_grid = find(loc_x, loc_y);
if( NULL == find_grid ){
continue;
}
if( find_grid->block == 1 ){
continue;
}
}

//front grid
grid_t* find_grid = find(grid->x+1, grid->y);
if( NULL != find_grid && find_grid->block == 0 ){
find_grid->g = 10;
find_grid->h = abs(end_grid->y - find_grid->y) + abs(end_grid->x - find_grid->x);
find_grid->total = find_grid->h * 10 + find_grid->g;
id_val_t id_val;
id_val.id = find_grid->id;
id_val.val = find_grid->total;
vec_id_val.push_back(id_val);
}

//back grid
find_grid = find(grid->x-1, grid->y);
if( NULL != find_grid && find_grid->block == 0 ){
find_grid->g = 10;
find_grid->h = abs(end_grid->y - find_grid->y) + abs(end_grid->x - find_grid->x);
find_grid->total = find_grid->h * 10 + find_grid->g;
id_val_t id_val;
id_val.id = find_grid->id;
id_val.val = find_grid->total;
vec_id_val.push_back(id_val);
}

//left grid
find_grid = find(grid->x, grid->y+1);
if( NULL != find_grid && find_grid->block == 0 ){
find_grid->g = 10;
find_grid->h = abs(end_grid->y - find_grid->y) + abs(end_grid->x - find_grid->x);
find_grid->total = find_grid->h * 10 + find_grid->g;
id_val_t id_val;
id_val.id = find_grid->id;
id_val.val = find_grid->total;
vec_id_val.push_back(id_val);
}

//right grid
find_grid = find(grid->x, grid->y-1);
if( NULL != find_grid && find_grid->block == 0 ){
find_grid->g = 10;
find_grid->h = abs(end_grid->y - find_grid->y) + abs(end_grid->x - find_grid->x);
find_grid->total = find_grid->h * 10 + find_grid->g;
id_val_t id_val;
id_val.id = find_grid->id;
id_val.val = find_grid->total;
vec_id_val.push_back(id_val);
}

//east-north
find_grid = find(grid->x+1, grid->y+1);
if( NULL != find_grid && find_grid->block == 0 ){
find_grid->g = 14;
find_grid->h = abs(end_grid->y - find_grid->y) + abs(end_grid->x - find_grid->x);
find_grid->total = find_grid->h * 10 + find_grid->g;
id_val_t id_val;
id_val.id = find_grid->id;
id_val.val = find_grid->total;
vec_id_val.push_back(id_val);
}

//east-south
find_grid = find(grid->x+1, grid->y+1);
if( NULL != find_grid && find_grid->block == 0 ){
find_grid->g = 14;
find_grid->h = abs(end_grid->y - find_grid->y) + abs(end_grid->x - find_grid->x);
find_grid->total = find_grid->h * 10 + find_grid->g;
id_val_t id_val;
id_val.id = find_grid->id;
id_val.val = find_grid->total;
vec_id_val.push_back(id_val);
}

//west-north
find_grid = find(grid->x-1, grid->y+1);
if( NULL != find_grid && find_grid->block == 0 ){
find_grid->g = 14;
find_grid->h = abs(end_grid->y - find_grid->y) + abs(end_grid->x - find_grid->x);
find_grid->total = find_grid->h * 10 + find_grid->g;
id_val_t id_val;
id_val.id = find_grid->id;
id_val.val = find_grid->total;
vec_id_val.push_back(id_val);
}

//west-south
find_grid = find(grid->x-1, grid->y-1);
if( NULL != find_grid && find_grid->block == 0 ){
find_grid->g = 14;
find_grid->h = abs(end_grid->y - find_grid->y) + abs(end_grid->x - find_grid->x);
find_grid->total = find_grid->h * 10 + find_grid->g;
id_val_t id_val;
id_val.id = find_grid->id;
id_val.val = find_grid->total;
vec_id_val.push_back(id_val);
}

int tid = vec_id_val[0].id;
int tval = vec_id_val[0].val;
for( int i=0; i<vec_id_val.size(); i++ ){
if( vec_id_val[i].val >= tval ){
continue;
}
tid = vec_id_val[i].id;
tval = vec_id_val[i].val;
}

return &map[tid-1];

//
}

int main(int argc, char* argv[])
{
init_map();
for( int i=0; i<100; i++ ){
if( i % 5 == 0 ){
printf("\n");
}
map[i].show();

// set grid 74 block
if( i>= 73 && i<= 75 ){
map[i].block = 1;
}

}
end_grid = &map[end-1];

int round = 1;
if( argc >= 2 ){
round = atoi(argv[1]);
}

struct timeval tv1;
struct timeval tv2;

gettimeofday(&tv1, NULL);
int time1 = time(NULL);
for( int round_num = 0; round_num < round; round_num++ ){
path_grid_id.clear();
path_grid_id.push_back(start);
int grid_id = start;
while(true){
grid_t* grid = find_next_grid(grid_id);
if( NULL == grid ){
break;
}
path_grid_id.push_back(grid->id);

bool is_over = false;
for( int i=0; i<path_grid_id.size(); i++ ){
if(path_grid_id[i] != end_grid->id){
continue;
}
is_over = true;
break;
}

if( is_over ){
break;
}

grid_id = grid->id;
}
}
int time2 = time(NULL);

gettimeofday(&tv2, NULL);

printf("path_grid_id size: %d\n", path_grid_id.size());
for( int i=0; i<path_grid_id.size(); i++ ){
printf("grid_id:%d\n", path_grid_id[i]);
}
printf("round:%d, use:%d\n", round, time2-time1);
printf("tv1_sec:%d, tv1_usec:%d\n", tv1.tv_sec, tv1.tv_usec);
printf("tv2_sec:%d, tv2_usec:%d\n", tv2.tv_sec, tv2.tv_usec);
return 0;
}

// astar.cpp END

编译

$g++ -g -o hello astar.cpp 测试$ ./hello  [round]

精确到微秒, 测试结果:
执行1次
round:1 use:0
tv1_sec:1506153329, tv1_usec:920483
tv2_sec:1506153329, tv2_usec:920516
时间为920516-920483=33微秒

执行1W次
round:10000, use:0
tv1_sec:1506154327, tv1_usec:283682
tv2_sec:1506154327, tv2_usec:770319

执行10W次
round:100000, use:2
tv1_sec:1506154390, tv1_usec:71109
tv2_sec:1506154392, tv2_usec:666823

round:1000000, use:25
tv1_sec:1506154417, tv1_usec:960088
tv2_sec:1506154442, tv2_usec:562360

展开全文
• C++实现A*寻路算法，经过测试，在有障碍物的情况下，路径为期望路径，内附测试结果，可以修改地图的大小及障碍物位置，比如大小改为1920*1080，使其更接近真实电脑屏幕或者手机屏幕分辨率，得到更为贴近实际的运算...
• ## C++A星算法

千次阅读 2015-10-23 18:20:15
#include #include #include #include using namespace std; class Node{ public: int x; int y; int f;//g+h int g;//起点到当前点的消耗 int h;//重点到当前点的理论消耗 ... this->x = x
#include <iostream>
#include <vector>
#include <stdio.h>
#include <algorithm>
using namespace std;
class Node{
public:
int x;
int y;
int f;//g+h
int g;//起点到当前点的消耗
int h;//重点到当前点的理论消耗
Node* parent;
Node(int x,int y){
this->x = x;
this->y = y;
this->f = 0;
this->g = 0;
this->h = 0;
this->parent = NULL;
}
Node(int x,int y,Node* parent){
this->x = x;
this->y = y;
this->f = 0;
this->g = 0;
this->h = 0;
this->parent = parent;
}
};

//0表示可通过1表示障碍物
int map[101][101] = {
{0,0,0,1,0,1,0,0,0},
{0,0,0,1,0,1,0,0,0},
{0,0,0,0,0,1,0,0,0},
{0,0,0,1,0,1,0,1,0},
{0,0,0,1,0,1,0,1,0},
{0,0,0,1,0,0,0,1,0},
{0,0,0,1,0,0,0,1,0}
};
vector<Node*> openList;
vector<Node*> closeList;
int row;//地图总行数
int col;//地图总列数
Node* startPos;//开始点
Node* endPos;//结束点
int weightW;//平移权重
int weightWH;//斜移权重

int countH(Node* sNode,Node* eNode){
int w = abs(sNode->x - eNode->x);
int h = abs(sNode->y - eNode->y);
int cost = min(w,h)*weightWH + abs(w-h)*weightW;
return cost;
}
void countFGH(Node* sNode,Node* eNode,int cost){
int h = countH(sNode,eNode);
int g = sNode->parent->g + cost;
int f = h + g;
sNode->f = f;
sNode->h = h;
sNode->g = g;
}
//检测列表是否包含指定节点
int isContains(vector<Node*>* v,int x,int y){
for(int i=0;i<v->size();i++){
if(v->at(i)->x==x&&v->at(i)->y==y){
return i;
}
}
return -1;
}
void initMap(){
row = 7;
col = 9;
weightW = 10;
weightWH = 15;
startPos = new Node(5,1);
endPos = new Node(3,8);
}

void printMap(){
for(int i=0;i<row;i++){
for(int j=0;j<col;j++){
printf("%d ",map[i][j]);
}
printf("\n");
}
}
bool compare(Node* n1,Node* n2){
return n1->f <= n2->f;
}
void checkMove(int x,int y,Node* parent,Node* end,int cost){
if(map[x][y]==1){
return;
}
if(isContains(&closeList,x,y)!=-1){
return;
}
int index = -1;
if((index = isContains(&openList,x,y))!=-1){
//是否存在更小的G值
Node* sNode = openList[index];
if(parent->g+cost < sNode->g){
sNode->g = parent->g+cost;
sNode->f = sNode->g + sNode->h;
}
}else{
Node* n = new Node(x,y,parent);
countFGH(n,end,cost);
openList.push_back(n);
}
}
void printPath(Node* node){
if(node->parent != NULL){
printPath(node->parent);
}
//将走过的点标记为2
//map[node->x][node->y] = 2;
printf("->%d,%d",node->x,node->y);
}
void releaseNode(Node* n){
if(n->parent != NULL){
releaseNode(n->parent);
}
delete n;
}
//-1错误0没找到1找到
int startSearch(Node* start,Node* end){
if(start->x<0||start->y<0||start->x>=row||start->y>=col
||end->x<0||end->y<0||end->x>=row||end->y>=col){
return -1;
}
if(map[start->x][start->y]==1||map[end->x][end->y]==1){
return -1;
}

start->h = countH(start,end);
start->f = start->h + start->g;
//查找算法
openList.push_back(start);
Node* root = NULL;
int find = 0;
while(openList.size()>0){
root = openList[0];
if(root->x==end->x&&root->y==end->y){
find = 1;
break;
}
//上下左右
if(root->x > 0){
checkMove(root->x-1,root->y,root,end,weightW);
}
if(root->y > 0){
checkMove(root->x,root->y-1,root,end,weightW);
}
if(root->x < row-1){
checkMove(root->x+1,root->y,root,end,weightW);
}
if(root->y < col-1){
checkMove(root->x,root->y+1,root,end,weightW);
}
if(root->x < row-1&&root->y>0){
checkMove(root->x+1,root->y-1,root,end,weightW);
}
if(root->y < col-1&&root->x>0){
checkMove(root->x-1,root->y+1,root,end,weightW);
}
if(root->x>0&&root->y>0){
checkMove(root->x-1,root->y-1,root,end,weightW);
}
if(root->y<col-1&&root->x<row-1){
checkMove(root->x+1,root->y+1,root,end,weightW);
}
closeList.push_back(root);
openList.erase(openList.begin());
sort(openList.begin(),openList.end(),compare);
}
if(find){
printPath(root);
printf("\n");
//printMap();
}
releaseNode(root);
openList.clear();
closeList.clear();
return find;
}

int main(int argc, char *argv[]){
initMap();
printMap();
int t = startSearch(startPos,endPos);
if(t==1){
printf("find!");
}else if(t==0){
printf("no find.");
}else{
printf("error!");
}
return 0;
}

展开全文
• A星算法实现原理看这里：http://www.cnblogs.com/technology/archive/2011/05/26/2058842.html    实现部分：  头文件：   [cpp] view plain copy   /*   A star 算法的基础处理  */  #...

A星算法的实现原理看这里：http://www.cnblogs.com/technology/archive/2011/05/26/2058842.html

实现部分：

头文件：

[cpp] view plain copy

1. /*
2.     A star 算法的基础处理
3. */
4. #ifndef _A_STAR_BASE_H_
5. #define _A_STAR_BASE_H_
6. #include "windows.h"
7.
8. typedef struct _APoint{
9.     int x; // x 坐标
10.     int y; // y 坐标
11.     int type; // 类型
12.     int f; // f = g + h
13.     int g;
14.     int h;
15. } APoint,*PAPoint;
16.
17. enum APointType{
18.     APT_UNKNOWN, // 未知状态
19.     APT_OPENED, // 开放列表中
20.     APT_CLOSED, // 关闭列表中
21.     APT_STARTPOINT, // 起始点
22.     APT_ENDPOINT // 结束点
23. };
24.
25.
26. class CAStarBase{
27. public:
28.     CAStarBase();
29.     ~CAStarBase();
30. private:
31.     PAPoint m_pAPointArr;
32.     int m_nAPointArrWidth;
33.     int m_nAPointArrHeight;
34.
35.     PAPoint m_pStartPoint,m_pEndPoint,m_pCurPoint;
36.     char* m_pOldArr;
37. public:
38.     BOOL Create(char* pDateArr,int nWidth,int nHeight);
39.     void SetStartPoint(int x,int y);
40.     void SetEndPoint(int x,int y);
41.     void SetOpened(int x,int y);
42.     void SetClosed(int x,int y);
43.     void SetCurrent( int x,int y );
44.     void PrintCharArr();
45.
46.     PAPoint CalcNextPoint(PAPoint ptCalc); // 应用迭代的办法进行查询
47. };
48.
49. #endif

实现cpp文件：

[cpp] view plain copy

1. #include "stdafx.h"
2. #include "AStarBase.h"
3.
4.
5. CAStarBase::CAStarBase()
6. {
7.     m_pAPointArr = NULL;
8.     m_nAPointArrWidth = 0;
9.     m_nAPointArrHeight = 0;
10.
11.     m_pStartPoint = NULL;
12.     m_pEndPoint = NULL;
13.     m_pCurPoint = NULL;
14.
15. }
16.
17. CAStarBase::~CAStarBase()
18. {
19.
20. }
21.
22. BOOL CAStarBase::Create( char* pDateArr,int nWidth,int nHeight )
23. {
24.     if(!pDateArr) return FALSE;
25.     if(nWidth<1 || nHeight<1) return FALSE;
26.     m_pAPointArr = new APoint[nWidth*nHeight];
27.     if(!m_pAPointArr) return FALSE;
28.     m_pOldArr = pDateArr;
29.     m_nAPointArrWidth = nWidth;
30.     m_nAPointArrHeight = nHeight;
31.     // 初始化数组内容
32.     for ( int y = 0;y<m_nAPointArrHeight;y++)
33.     {
34.         for ( int x=0;x<m_nAPointArrWidth;x++)
35.         {
36.             m_pAPointArr[y*m_nAPointArrWidth+x].x = x;
37.             m_pAPointArr[y*m_nAPointArrWidth+x].y = y;
38.             m_pAPointArr[y*m_nAPointArrWidth+x].g = 0;
39.             m_pAPointArr[y*m_nAPointArrWidth+x].f = 0;
40.             m_pAPointArr[y*m_nAPointArrWidth+x].h = 0;
41.
42.             if ( pDateArr[y*m_nAPointArrWidth+x] == '0')
43.             {
44.                 m_pAPointArr[y*m_nAPointArrWidth+x].type = APT_OPENED;
45.             }else if ( pDateArr[y*m_nAPointArrWidth+x] == '1')
46.             {
47.                 m_pAPointArr[y*m_nAPointArrWidth+x].type = APT_CLOSED;
48.             }else if ( pDateArr[y*m_nAPointArrWidth+x] == 'S')
49.             {
50.                 m_pAPointArr[y*m_nAPointArrWidth+x].type = APT_STARTPOINT;
51.                 m_pStartPoint = m_pAPointArr + y*m_nAPointArrWidth+x;
52.                 m_pCurPoint = m_pStartPoint;
53.             }else if ( pDateArr[y*m_nAPointArrWidth+x] == 'E')
54.             {
55.                 m_pAPointArr[y*m_nAPointArrWidth+x].type = APT_ENDPOINT;
56.                 m_pEndPoint = m_pAPointArr + y*m_nAPointArrWidth+x;
57.             }else{
58.                 m_pAPointArr[y*m_nAPointArrWidth+x].type = APT_UNKNOWN;
59.             }
60.
61.         }
62.     }
63.     return TRUE;
64. }
65.
66. void CAStarBase::SetStartPoint( int x,int y )
67. {
68.     if ( m_pStartPoint && m_pAPointArr[y*m_nAPointArrWidth+x].type!=APT_CLOSED )
69.     {
70.         m_pStartPoint->type = APT_OPENED;
71.         // 设置新的值
72.         m_pStartPoint = m_pAPointArr + y*m_nAPointArrWidth+x;
73.         m_pStartPoint->type = APT_STARTPOINT;
74.         m_pCurPoint = m_pStartPoint;
75.     }
76. }
77.
78. void CAStarBase::SetEndPoint( int x,int y )
79. {
80.     if ( m_pStartPoint && m_pAPointArr[y*m_nAPointArrWidth+x].type!=APT_CLOSED )
81.     {
82.         m_pStartPoint->type = APT_OPENED;
83.         // 设置新的值
84.         m_pStartPoint = m_pAPointArr + y*m_nAPointArrWidth+x;
85.         m_pStartPoint->type = APT_ENDPOINT;
86.     }
87. }
88.
89. void CAStarBase::SetCurrent( int x,int y )
90. {
91. //  if ( m_pAPointArr[y*m_nAPointArrWidth+x].type==APT_OPENED )
92.     {
93.         m_pCurPoint = m_pAPointArr+y*m_nAPointArrWidth+x;
94.     }
95. }
96.
97. void CAStarBase::SetOpened( int x,int y )
98. {
99.     if ( m_pAPointArr[y*m_nAPointArrWidth+x].type!=APT_OPENED )
100.     {
101.         m_pAPointArr[y*m_nAPointArrWidth+x].type = APT_OPENED;
102.     }
103. }
104.
105. void CAStarBase::SetClosed( int x,int y )
106. {
107.     if ( m_pAPointArr[y*m_nAPointArrWidth+x].type!=APT_CLOSED )
108.     {
109.         m_pAPointArr[y*m_nAPointArrWidth+x].type = APT_CLOSED;
110.     }
111. }
112.
113. void CAStarBase::PrintCharArr()
114. {
115.     if ( m_pOldArr )
116.     {
117.         for ( int y=0; y<m_nAPointArrHeight;y++)
118.         {
119.             for ( int x=0;x<m_nAPointArrWidth;x++)
120.             {
121.                 printf("%c ",m_pOldArr[x+m_nAPointArrWidth*y]);
122.             }
123.             printf("\r\n");
124.         }
125.         printf("\r\n");
126.     }
127. }
128.
129. PAPoint CAStarBase::CalcNextPoint( PAPoint ptCalc )
130. {
131.     if ( ptCalc == NULL )
132.     {
133.         ptCalc = m_pStartPoint;
134.     }
135.     int x = ptCalc->x;
136.     int y = ptCalc->y;
137.     int dx = m_pEndPoint->x;
138.     int dy = m_pEndPoint->y;
139.     int xmin = x,ymin = y,vmin = 0; // 最优步骤的坐标和值
140.     // 判断是否已经到了最终的位置
141.     if ( (x==dx && abs(y-dy)==1) || (y==dy && abs(x-dx)==1) )
142.     {
143.         return m_pEndPoint;
144.     }
145.     // 上
146.     if ( m_pAPointArr[(x+0)+m_nAPointArrWidth*(y-1)].type == APT_OPENED && y>0)
147.     {
148.         m_pAPointArr[(x+0)+m_nAPointArrWidth*(y-1)].g = 10;
149.         m_pAPointArr[(x+0)+m_nAPointArrWidth*(y-1)].h =
150.             10*(abs(x - dx) + abs(y-1 - dy));
151.         m_pAPointArr[(x+0)+m_nAPointArrWidth*(y-1)].f =
152.             m_pAPointArr[(x+0)+m_nAPointArrWidth*(y-1)].g + m_pAPointArr[(x+0)+m_nAPointArrWidth*(y-1)].h;
153.         if ( vmin==0 )
154.         {
155.             xmin = x;
156.             ymin = y-1;
157.             vmin = m_pAPointArr[(x+0)+m_nAPointArrWidth*(y-1)].f;
158.         }else{
159.             if ( vmin > m_pAPointArr[(x+0)+m_nAPointArrWidth*(y-1)].f )
160.             {
161.                 xmin = x;
162.                 ymin = y-1;
163.                 vmin = m_pAPointArr[(x+0)+m_nAPointArrWidth*(y-1)].f;
164.             }
165.         }
166.     }
167.     // 下
168.     if ( m_pAPointArr[(x+0)+m_nAPointArrWidth*(y+1)].type == APT_OPENED && y<m_nAPointArrHeight)
169.     {
170.         m_pAPointArr[(x+0)+m_nAPointArrWidth*(y+1)].g = 10;
171.         m_pAPointArr[(x+0)+m_nAPointArrWidth*(y+1)].h =
172.             10*(abs(x - dx) + abs(y+1 - dy));
173.         m_pAPointArr[(x+0)+m_nAPointArrWidth*(y+1)].f =
174.             m_pAPointArr[(x+0)+m_nAPointArrWidth*(y+1)].g + m_pAPointArr[(x+0)+m_nAPointArrWidth*(y+1)].h;
175.         if ( vmin==0 )
176.         {
177.             xmin = x;
178.             ymin = y+1;
179.             vmin = m_pAPointArr[(x+0)+m_nAPointArrWidth*(y+1)].f;
180.         }else{
181.             if ( vmin > m_pAPointArr[(x+0)+m_nAPointArrWidth*(y+1)].f )
182.             {
183.                 xmin = x;
184.                 ymin = y+1;
185.                 vmin = m_pAPointArr[(x+0)+m_nAPointArrWidth*(y+1)].f;
186.             }
187.         }
188.     }
189.     // 左
190.     if ( m_pAPointArr[(x-1)+m_nAPointArrWidth*y].type == APT_OPENED && x>0)
191.     {
192.         m_pAPointArr[(x-1)+m_nAPointArrWidth*y].g = 10;
193.         m_pAPointArr[(x-1)+m_nAPointArrWidth*y].h =
194.             10*(abs(x-1 - dx) + abs(y - dy));
195.         m_pAPointArr[(x-1)+m_nAPointArrWidth*y].f =
196.             m_pAPointArr[(x-1)+m_nAPointArrWidth*y].g + m_pAPointArr[(x-1)+m_nAPointArrWidth*y].h;
197.         if ( vmin==0 )
198.         {
199.             xmin = x-1;
200.             ymin = y;
201.             vmin = m_pAPointArr[(x-1)+m_nAPointArrWidth*y].f;
202.         }else{
203.             if ( vmin > m_pAPointArr[(x-1)+m_nAPointArrWidth*y].f )
204.             {
205.                 xmin = x-1;
206.                 ymin = y;
207.                 vmin = m_pAPointArr[(x-1)+m_nAPointArrWidth*y].f;
208.             }
209.         }
210.     }
211.     // 右
212.     if ( m_pAPointArr[(x+1)+m_nAPointArrWidth*y].type == APT_OPENED && x<m_nAPointArrWidth)
213.     {
214.         m_pAPointArr[(x+1)+m_nAPointArrWidth*y].g = 10;
215.         m_pAPointArr[(x+1)+m_nAPointArrWidth*y].h =
216.             10*(abs(x+1 - dx) + abs(y - dy));
217.         m_pAPointArr[(x+1)+m_nAPointArrWidth*y].f =
218.             m_pAPointArr[(x+1)+m_nAPointArrWidth*y].g + m_pAPointArr[(x+1)+m_nAPointArrWidth*y].h;
219.         if ( vmin==0 )
220.         {
221.             xmin = x+1;
222.             ymin = y;
223.             vmin = m_pAPointArr[(x+1)+m_nAPointArrWidth*y].f;
224.         }else{
225.             if ( vmin > m_pAPointArr[(x+1)+m_nAPointArrWidth*y].f )
226.             {
227.                 xmin = x+1;
228.                 ymin = y;
229.                 vmin = m_pAPointArr[(x+1)+m_nAPointArrWidth*y].f;
230.             }
231.         }
232.     }
233.
234.     // 如果有最优点则迭代，则否就返回NULL
235.     if ( vmin )
236.     {
237.         SetCurrent(xmin,ymin);
238.         SetClosed(xmin,ymin);
239.         *(m_pOldArr+xmin+m_nAPointArrWidth*ymin) = '-';
240.         PrintCharArr();
241.         PAPoint pApoint = CalcNextPoint(m_pCurPoint);
242.         if ( pApoint == NULL )
243.         {
244.             SetCurrent(x,y);
245.             SetClosed(xmin,ymin);
246.             *(m_pOldArr+xmin+m_nAPointArrWidth*ymin) = '0';
247.             return CalcNextPoint(m_pCurPoint);
248.         }
249.         return pApoint;
250.     }else{
251.         return NULL;
252.     }
253.
254. }

测试文件：

[cpp] view plain copy

1. // AStarMath.cpp : 定义控制台应用程序的入口点。
2. //
3.
4. #include "stdafx.h"
5. #include "AStarBase.h"
6.
7. CAStarBase Astarbase;
8.
9. int _tmain(int argc, _TCHAR* argv[])
10. {
11.     char pBuff[5][7] = {
12.         '0','0','0','1','0','0','0',
13.         '0','1','1','0','0','1','1',
14.         '0','S','1','0','1','E','0',
15.         '0','1','0','0','0','1','0',
16.         '0','0','0','1','0','0','0'
17.     };
18.     Astarbase.Create(&pBuff[0][0],7,5);
19.     Astarbase.PrintCharArr();
20.     PAPoint pPoint = Astarbase.CalcNextPoint(NULL);
21.     if ( pPoint == NULL )
22.     {
23.         printf("no path can arrive!\r\n");
24.     }else{
25.         printf("success arrived!\r\n");
26.     }
27.     getchar();
28.     return 0;
29. }
展开全文
• A*，那个传说中的算法堪称最好的A*算法自己在github上找到了一个比较简单的用C++实现的版本(点击打开链接)，自己在此基础上添加了opencv绘制简单图块，将结果可视化了，如下图。其中，红色为障碍块，白色绿边为自由...
• A星算法C++代码实现，可以实现从初始点到终点的最短路径规划，采用的是曼哈顿方法。
• A*(A星)算法示例，多种实现方法，语言为C++ 原创代码，
• A星寻路算法的讲解有很多，这里不再论述，只给出实现程序。 AStar.h #pragma once #include <vector> #include <map> #include <queue> // 二维地图A*算法实现 const int OBLIQUE = 14; // ...
• Astar C++源代码 Astar.h A*类头文件 Astar.cpp A*类源代码文件
• A星算法 游戏中自动寻路的实现(C++源代码）
• 打开//=====优化处理=======================================================里面的代码是优化处理。源码地址：https://github.com/haidragon/A-star 转载于:https://blog.51cto.com/haidragon/2082671...
• A星原理可以去网上搜。   那我就直接上代码啦！   A星的头文件   [cpp] view plaincopy /************************************************************************/ /
• 本程序中的20个城市点的坐标是自己随便设的，两城市之间的费用是随机生成的，要么相通，想通则是大于两城市之间的欧几里得距离的，开发平台为VS2008 实现语言为C++
• 以下为A*寻路算法代码实现，核心思想就是只走F值(格子评估值)最小的格子，直至到达终点。 F值最小代表着从起点出发到达终点需要的最少的步数，只走最少的步数，那么路径就是最短的。 #include <iostream> #...
• 内有N个范例，每个都可以使用，算法使用图形表示。上手容易。
•  A*搜寻算法，俗称A星算法。这是一种在图形平面上，有多个节点的路径，求出最低通过成本的算法。常用于游戏中的NPC的移动计算，或线上游戏的BOT的移动计算上。 该算法像Dijkstra算法一样，可以找到一条最短路径；...
• 如果角色可以360度走,要怎么使路径平滑呢???? ???????????????????????????????????
...