自定义词典_自定义情感词典 - CSDN
精华内容
参与话题
  • C++实现A星算法自动寻路

    千次阅读 2013-12-13 18:28:44
    虽然网上已经有许多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++实现

    2017-09-23 16:54:06
    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



    展开全文
  • A星算法C++实现

    2020-07-17 17:53:07
    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

     

     在CODE上查看代码片派生到我的代码片

    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

     

     在CODE上查看代码片派生到我的代码片

    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++代码实现

    2020-07-21 10:00:12
    A星算法C++代码实现,可以实现从初始点到终点的最短路径规划,采用的是曼哈顿方法。
  • A星算法示例(多种实现

    热门讨论 2020-07-30 23:32:40
    A*(A星)算法示例,多种实现方法,语言为C++ 原创代码,
  • A星寻路算法的讲解有很多,这里不再论述,只给出实现程序。 AStar.h #pragma once #include <vector> #include <map> #include <queue> // 二维地图A*算法实现 const int OBLIQUE = 14; // ...
  • A星算法(简单直观)

    2020-07-30 23:32:29
    Astar C++源代码 Astar.h A*类头文件 Astar.cpp A*类源代码文件
  • A星算法自动寻路(C++源代码)

    热门讨论 2020-07-30 14:50:20
    A星算法 游戏中自动寻路的实现(C++源代码)
  • 打开//=====优化处理=======================================================里面的代码是优化处理。源码地址:https://github.com/haidragon/A-star 转载于:https://blog.51cto.com/haidragon/2082671...
  • A星算法-自动寻路-c++

    千次阅读 2014-03-26 11:34:05
    A星原理可以去网上搜。   那我就直接上代码啦!   A星的头文件   [cpp] view plaincopy /************************************************************************/ /
  • 本程序中的20个城市点的坐标是自己随便设的,两城市之间的费用是随机生成的,要么相通,想通则是大于两城市之间的欧几里得距离的,开发平台为VS2008 实现语言为C++
  • A星寻路算法简易版(代码实现)

    千次阅读 2019-07-26 16:48:23
    以下为A*寻路算法代码实现,核心思想就是只走F值(格子评估值)最小的格子,直至到达终点。 F值最小代表着从起点出发到达终点需要的最少的步数,只走最少的步数,那么路径就是最短的。 #include <iostream> #...
  • C++A星算法(很不错)

    2020-07-30 23:30:46
    内有N个范例,每个都可以使用,算法使用图形表示。上手容易。
  •  A*搜寻算法,俗称A星算法。这是一种在图形平面上,有多个节点的路径,求出最低通过成本的算法。常用于游戏中的NPC的移动计算,或线上游戏的BOT的移动计算上。 该算法像Dijkstra算法一样,可以找到一条最短路径;...
  • 如果角色可以360度走,要怎么使路径平滑呢???? ???????????????????????????????????
1 2 3 4 5 ... 20
收藏数 8,584
精华内容 3,433
关键字:

自定义词典