荐 破“图”式（二）

图的应用案例

游戏中的自动寻路-A*算法






寻路步骤



















算法实现

Astar.h

#pragma once 

#include <list> 

const int kCost1 = 10; //直移一格消耗 
const int kCost2 = 14; //斜移一格消耗 

typedef struct _Point { 
	int x,y; 
	/*点坐标，这里为了方便按照 C++的数组来计算，x 代表横排，y 代表竖列*/
	
	int F,G,H; //F=G+H 
	
	struct _Point *parent; //parent 的坐标 
}Point; 


/*分配一个节点(格子)*/ 
Point* AllocPoint(int x, int y); 

/*初始化地图*/ 
void InitAstarMaze(int *_maze, int _lines, int _colums); 

/*通过 A* 算法寻找路径*/ 
std::list<Point *> GetPath(Point *startPoint, Point *endPoint); 

/*清理资源，结束后必须调用*/ 
void ClearAstarMaze();

Astar.cpp

#include <math.h> 
#include "Astar.h" 
#include <iostream> 
#include <vector> 

static int *maze; //迷宫对应的二维数组，使用一级指针表示 
static int cols; //二维数组对应的列数 
static int lines; //二维数组对应的行数 
static std::list<Point *> openList; //开放列表 
static std::list<Point *> closeList; //关闭列表 

/*搜索从起点到终点的最佳路径*/ 
static Point* findPath(Point *startPoint,Point *endPoint); 

/*从开启列表中返回 F 值最小的节点*/ 
static Point *getLeastFpoint(); 

/*获取当前点周围可达的节点*/ 
static std::vector<Point *> getSurroundPoints(const Point *point); 

/*判断某点是否可以用于下一步判断 */ 
static bool isCanreach(const Point *point,const Point *target); 

/*判断开放/关闭列表中是否包含某点*/ 
static Point *isInList(const std::list<Point *> &list,const Point *point); 

//计算 FGH 值 
static int calcG(Point *temp_start,Point *point); 
static int calcH(Point *point,Point *end); 
static int calcF(Point *point); 

/*分配一个节点(格子)*/ 
Point* AllocPoint(int x, int y){ 
	Point *temp = new Point; 
	memset(temp, 0, sizeof(Point));//初始值清零 
	temp->x = x; 
	temp->y = y; 
	return temp; 
}

/*初始化 A*搜索的地图*/ 
void InitAstarMaze(int *_maze, int _lines, int _colums) { 
	maze = _maze; 
	lines = _lines; 
	cols = _colums; 
}

/*通过 A* 算法寻找路径*/ 
std::list<Point *> GetPath(Point *startPoint, Point *endPoint){ 
	Point *result=findPath(startPoint, endPoint); 
	std::list<Point *> path; //返回路径，如果没找到路径，返回空链表 

	while(result){ 
		path.push_front(result); 
		result=result->parent; 
	}
	return path; 
}

/*搜索从起点到终点的最佳路径*/ 
static Point* findPath(Point *startPoint,Point *endPoint){ 
	openList.push_back(AllocPoint(startPoint->x, startPoint->y));//置 入起点,拷贝开辟一个节点，内外隔离 
	
	while(!openList.empty()){ 
		//第一步，从开放列表中取最小 F 的节点 
		Point *curPoint = getLeastFpoint();//找到 F 值最小的点 
		//第二步，把当前节点放到关闭列表中 
		openList.remove(curPoint); 
		closeList.push_back(curPoint); 
		//第三步，找到当前节点周围可达的节点，并计算 F 值 
		std::vector<Point *> surroundPoints = getSurroundPoints(curPoint); 
		std::vector<Point *>::const_iterator iter; 
	
		for(iter=surroundPoints.begin();iter!=surroundPoints.end(); iter++){ 
			Point *target = *iter;
			
			//对某一个格子，如果它不在开放列表中，加入到开启列表，设置 当前格为其父节点，计算 F G H 
			Point *exist = isInList(openList, target); 
			
			if(!exist){ 
				target->parent=curPoint; 
				target->G=calcG(curPoint,target); 
				target->H=calcH(target,endPoint); 
				target->F=calcF(target); 
				openList.push_back(target); 
			}else { 
				int tempG = calcG(curPoint, target); 
				if(tempG<target->G){ 
					exist->parent = curPoint; 
					exist->G=tempG; 
					exist->F=calcF(target); 
				}
				delete target; 
			} 
		}//end for 
		surroundPoints.clear(); 
		Point *resPoint = isInList(openList, endPoint); 
	
		if(resPoint){ 
			return resPoint; 
		} 
	}
	return NULL; 
}


/*从开启列表中返回 F 值最小的节点*/ 
static Point *getLeastFpoint(){ 
	if(!openList.empty()){ 
		Point *resPoint = openList.front(); 
		std::list<Point*>::const_iterator itor; 
		for(itor = openList.begin(); itor!= openList.end(); itor++){ 
			if((*itor)->F < resPoint->F){ 
				resPoint = *itor; 
			} 
		}
		return resPoint;
	}
	return NULL; 
}


/*获取当前点周围可达的节点*/ 
static std::vector<Point *> getSurroundPoints(const Point *point){ 
	std::vector<Point *> surroundPoints; 
	for(int x=point->x-1; x<=point->x+1; x++){ 
		for(int y=point->y-1; y<=point->y+1; y++){ 
			Point *temp = AllocPoint(x, y); 
			if(isCanreach(point, temp)){ 
				surroundPoints.push_back(temp); 
			}else { 
				delete temp; 
			} 
		} 
	}
	return surroundPoints; 
}


/*判断某点是否可以用于下一步判断 */ 
static bool isCanreach(const Point *point,const Point *target){ 
	
	if(target->x<0||target->x>(lines-1) ||
		target->y<0||target->y>(cols-1) ||
		maze[target->x *cols + target->y]==1 ||
		maze[target->x *cols + target->y]==2 ||
		(target->x==point->x && target->y==point->y) ||
		isInList(closeList, target)){ 
			return false; 
	}
	
	if(abs(point->x-target->x)+abs(point->y-target->y)==1){ 
		return true; 
	}else { 
		return false; 
	} 
}


static Point* isInList(const std::list<Point *> &list,const Point *point) { 
	/*判断某个节点是否在列表中，这里不能比较指针，
	因为每次加入列表是新 开辟的节点，只能比较坐标*/
	std::list<Point *>::const_iterator itor;
	for(itor = list.begin(); itor!=list.end();itor++){
		if((*itor)->x==point->x&&(*itor)->y==point->y) { 
			return *itor; 
		} 
	}
	return NULL; 
}



/*计算节点的 G 值*/ 
static int calcG(Point *temp_start, Point *point) { 
	int extraG=(abs(point->x-temp_start->x)+abs(point->y-temp_start->y))==1?kCost1:kCost2; 
	
	//如果是 初始节点，则其父节点是空
	int parentG=(point->parent==NULL? NULL:point->parent->G);  
	return parentG+extraG; 
}


static int calcH(Point *point,Point *end) { 
	//用简单的欧几里得距离计算 H，可以用多中方式实现 
	return (int)sqrt((double)(end->x-point->x)*(double)(end->x-point->x)+(double )(end->y-point->y)*(double)(end->y-point->y))*kCost1; 
}


/*计算节点的 F 值*/ 
static int calcF(Point *point) { 
	return point->G+ point->H; 
}


/*清理资源，结束后必须调用*/ 
void ClearAstarMaze(){ 
	maze = NULL; 
	lines = 0; 
	cols = 0; 
	std::list<Point *>::iterator itor; 
	
	//清除 openList 中的元素 
	for(itor = openList.begin(); itor!=openList.end();){ 
		delete *itor; 
		itor = openList.erase(itor);//获取到下一个节点 
	}
	
	//清理 closeList 中的元素 
	for(itor = closeList.begin(); itor!=closeList.end();){ 
		delete *itor; 
		itor = closeList.erase(itor); 
	}
}

main.cpp

#include "Astar.h" 
#include <list> 
#include <iostream> 
#include <windows.h> 

using namespace std; 

//定义地图数组 
//二维数组在内存顺序存储的
int map[13][13] = { 
	{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, }, 
	{ 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, }, 
	{ 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, }, 
	{ 0, 1, 0, 1, 0, 1, 2, 1, 0, 1, 0, 1, 0, }, 
	{ 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, }, 
	{ 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, }, 
	{ 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, }, 
	{ 2, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 2, }, 
	{ 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, }, 
	{ 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, }, 
	{ 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, }, 
	{ 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, }, 
	{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, } };


void AStarTest(){ 
	InitAstarMaze(&map[0][0], 13, 13); //设置起始和结束点 
	Point* start = AllocPoint(12, 4); 
	Point* end = AllocPoint(0, 0);
	
	//A*算法找寻路径 
	list<Point *> path = GetPath(start, end); 
	cout<<"寻路结果:"<<endl; list<Point *>::const_iterator iter; 
	
	for(iter=path.begin(); iter!=path.end(); iter++){ 
		Point *cur = *iter; 
		cout<<'('<<cur->x<<','<<cur->y<<')'<<endl; 
		Sleep(800); 
	}
	ClearAstarMaze(); 
}

int main(void){ 
	AStarTest(); 
	system("pause"); 
	return 0; 
}

本文地址：https://blog.csdn.net/qq_34850023/article/details/107326509