MyException - 我的异常网
当前位置:我的异常网» 编程 » 【游戏编程】A*寻途算法原理及编程实现(C++类封装)

【游戏编程】A*寻途算法原理及编程实现(C++类封装)

www.MyException.Cn  网友分享于:2013-10-18  浏览:34次
【游戏编程】A*寻路算法原理及编程实现(C++类封装)

广度优先搜索和深度优先搜索都属于盲目型搜索算法,在选择下一个搜索节点的时候没有一个准则,去选择最优的。很多情况下需要会穷举整个空间,因此只适用于规模较小的搜索。因此需要用到另外一种算法---启发式搜索。


一、A*算法原理

启发式搜索就是在状态空间中对每一个搜索位置进行评估,得到最好的位置,再从这个位置进行搜素直到目标。这样可以省略大量无谓的搜索路径。在启发式搜索中,对位置的估计尤其重要,采用不同的估计函数会有不同的效果。

启发式搜索中的估价函数为:

f(n) = g(n) + h(n)

f(n):节点n的估价函数。

g(n):从起始点到n节点的实际代价。

h(n):从节点n到目标节点最佳路径的估计代价。

在这里,h(n)便是估价函数,体现了搜索的启发信息。g(n)是已知的。

启发式搜索有很多算法:局部最优搜索、最优优先搜索算法等等。A星算法也是。局部优先搜索是在搜索过程中选择最佳节点后舍弃其他的兄弟节点,其很明显的缺陷是可能舍弃了最好的节点。最好优先则没有舍弃节点,有效地防止了最佳节点的丢失。A星算法是一种最好优先算法。只不过要加上一些特定的约束条件。在一些问题求解时,希望可以求解出状态空间搜索的最短路径。

A*算法的估价函数可表示为:

  f'(n) = g'(n) + h'(n)

  这里,f'(n)是估价函数,g'(n)是起点到终点的最短路径值,h'(n)是n到目标的最短路经的启发值。由于这个f'(n)其实是无法预先知道的,所以我们用前面的估价函数f(n)做近似。g(n)代替g'(n),但g(n)>=g'(n)才可(大多数情况下都是满足的,可以不用考虑),h(n)代替h'(n),但h(n)<=h'(n)才可(这一点特别的重要),即小于n到目标的实际代价值。可以证明应用这样的估价函数是可以找到最短路径的,也就是可采纳的。我们说应用这种估价函数的最好优先算法就是A*算法,否则就不是A*算法。在这种情况下,搜索的范围大,效率低,但是能得到最优解。如果估价值>实际代价,搜索范围小,效率高,但是不能保证得到最优解。

注意:估价值与实际代价值越接近,估价函数选取得就越好。


关于h(n)启发函数的信息性的问题


h(n)的信息性通俗点说其实就是在估计一个节点的值时的约束条件,如果信息越多或约束条件越多则排除的节点就越多,估价函数越好或说这个算法越好。这就是为什么广度优先算法的那么臭的原因了,谁叫它的h(n)=0,一点启发信息都没有。但在游戏开发中由于实时性的问题,h(n)的信息越多,它的计算量就越大,耗费的时间就越多。就应该适当的减小h(n)的信息,即减小约束条件。但算法的准确性就差了,这里就有一个平衡的问题。


关于启发函数h(n)的相容性


如果h(n)满足h(n1) - h(n2) <= c(n1,n2),其中c(n1,n2)是n1节点到n2节点的实际代价,则称h(n)是相容的。也就是说状态转移时,下界h的减小值最多等于状态转移的实际代价,其实就是要求h不能减小得太快。

那么,对于节点n1以及其后继节点n2,有:

f(n1) = g(n1) + h(n1)

f(n2) = g(n2) + h(n2)

又由于:

g(n2) = g(n1) + c(n1,n2),推导出:

f(n2) = g(n1) + c(n1,n2) + h(n2)

如果h(n)是相容的,则有h(n1) <= h(n2) + c(n1,n2),两边同时加上g(n1),推导出:

h(n1) + g(n1) <= h(n2) + g(n2) + c(n1,n2),也就是:

f(n1) <= f(n2)

 可以看出,如果启发函数h(n)相容,那么估价函数f(n)单调非递减。就是说按照此算法搜索最先生成的路径一定是最短的。这样的话,搜索过程中就不再需要维持一个CLOSED表,只需维护一个已访问节点表OPEN表。

在选择启发函数的时候,最好选择相容的启发式函数。


A星算法步骤:

1,把起始格添加到开启列表。
   2,重复如下的工作:
      a) 寻找开启列表中F值最低的格子。我们称它为当前格。
      b) 把它切换到关闭列表。
      c) 对相邻的8格中的每一个?
          * 如果它不可通过或者已经在关闭列表中,略过它。反之如下。
          * 如果它不在开启列表中,把它添加进去。把当前格作为这一格的父节点。记录这一格的F,G,和H值。
          * 如果它已经在开启列表中,用G值为参考检查新的路径是否更好。更低的G值意味着更好的路径。如果是这样,就把这一格的父节点改成当前格,并且重新计算这一格的G和F值。如果你保持你的开启列表按F值排序,改变之后你可能需要重新对开启列表排序。
      d) 停止,当你
          * 把目标格添加进了关闭列表(注解),这时候路径被找到,或者
          * 没有找到目标格,开启列表已经空了。这时候,路径不存在。
   3.保存路径。从目标格开始,沿着每一格的父节点移动直到回到起始格。这就是你的路径。


二、A*算法编程实现

本文通过迷宫寻路实例,实现了A*算法的C++类封装。

迷宫地图:


起始点是绿色方格,目标点是景色方格,蓝色方格表示障碍物,不可通过。

在搜索过程中,横向移动或者纵向移动的代价都是10,对角线上的移动代价是14.需要注意的是:障碍物的角落不可通过。

将迷宫信息写在一个文本文件里面:


第一行的两个整数代表迷宫的行数和列数。第二行是起始点和目标点的坐标(x,y)。x是所在的行,y是所在的列(均以0开始计算)。

接下来便是迷宫的具体信息,0表示可以通过,1表示障碍物。


下面贴出代码,如有错误,欢迎批评指正(邮箱:xiajunhust@gmail.com)。

程序代码(C++):

AStarPathFinding.h:

#ifndef ASTARPATHFINDING_H
#define ASTARPATHFINDING_H

#include <queue>//为了使用优先级队列priority_queue
#include <stack>
#include <vector>

//迷宫地图中节点类型标记
enum{
	NODE_EMPTY,//可以通过的节点
	NODE_OBSTACLE,//障碍物,不可通过
	NODE_PATH//路径上的点
};

//记录路径上的点的坐标
typedef struct tagpathNode{
	int x,y;
}PathNode;

//节点数据结构定义
typedef struct tagNode{
	int x,y;//当前点在迷宫中的位置坐标
	int g;//起始点到当前点实际代价
	int h;//当前节点到目标节点最佳路径的估计代价
	int f;//估计函数:f = g + h。
	struct tagNode *father;//指向其父节点的指针
}Node;

//定义STL优先队列的排序方式
class HeapCompare_f{
public:
	bool operator()(Node* x,Node* y) const
	{
		return x->f > y->f;//依据估价函数进行排序:升序排列
	}
};

//迷宫寻路:A*算法
class AStarPathFinding{
public:

private:
	char *m_mapFileName;//存储地图信息的文件名
	int m_rows,m_cols;//迷宫的高度和宽度
	int **m_maze;//迷宫布局
	int m_startX,m_startY;//起始点坐标
	int m_endX,m_endY;//目标点坐标
	int dx[8],dy[8];//8个子节点移动方向:上、下、左、右、左上、右上、右下、左下

	Node *startNode,*endNode;//起始节点和目标节点
	int **m_path;//记录路径信息
	int m_steps;//搜索所花费的总步数

	//OPEN表:采用C++ STL中vector实现优先级队列功能
	//注意:存储的是Node*指针
	std::vector<Node*> OPENTable;
	//CLOSED表:存储的也是Node*指针
	std::vector<Node*> CLOSEDTable;

public:
	//构造函数
	AStarPathFinding(char* mapFileName);
	~AStarPathFinding();//析构函数
	void init();//初始化
	//读取地图信息
	bool readMap();
	//寻路主函数
	bool pathFinding();
	//产生路径信息
	void generatePath();
	//打印路径信息
	void printPath();
	//估计当前点到目标点的距离:曼哈顿距离
	int judge(int x,int y);
	//判断某一节点是否合法
	bool isIllegle(int x,int y);
};

#endif


AStarPathFnding.cpp:

#include "AStarPathFinding.h"

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <fstream>

using namespace std;

const int MaxDistance = 9999;

AStarPathFinding::AStarPathFinding(char* mapFileName)
:m_steps(0)
{
	m_mapFileName = (char *)malloc((strlen(mapFileName) + 1) * sizeof(char));
	strcpy(m_mapFileName,mapFileName);
}

AStarPathFinding::~AStarPathFinding()
{
	free(m_mapFileName);

	//千万不能有这句代码,因为startNode已加入OPEN表,会在释放OPEN表
	//的时候释放,否则会造成重复释放,出现bug
	//delete startNode;
	delete endNode;

	////释放迷宫布局数组:注意多维数组空间释放
	for (int i = 0;i < m_rows;++i)
	{
		delete[] m_maze[i];
	}
	delete[] m_maze;

	for (int i = 0;i < m_rows;++i)
	{
		delete[] m_path[i];
	}
	delete[] m_path;

	//释放OPEN表以及CLOSED表内存空间
	vector<Node*>::iterator iter;
	for (iter = OPENTable.begin();iter != OPENTable.end();++iter)
	{
		delete (*iter);
	}
	OPENTable.clear();

	vector<Node*>::iterator iter2;
	for (iter2 = CLOSEDTable.begin();iter2 != CLOSEDTable.end();++iter2)
	{
		delete (*iter2);
	}
	CLOSEDTable.clear();
}

void AStarPathFinding::init()
{
	dx[0] =dx[4] = dx[5] = -1;
	dx[1] =dx[3] = 0;
	dx[2] =dx[6] = dx[7] = 1;

	dy[3] = dy[4] = dy[7] = -1;
	dy[0] =dy[2] = 0;
	dy[1] =dy[5] = dy[6] = 1;

	readMap();

	//分配空间
	m_path = new int *[m_rows];
	for (int i = 0;i < m_rows;++i)
	{
		m_path[i] = new int[m_cols];
	}

	startNode = new Node;
	startNode->x = m_startX;
	startNode->y = m_startY;
	startNode->g = 0;
	startNode->h = judge(startNode->x,startNode->y);
	startNode->f = startNode->g + startNode->h;
	startNode->father = NULL;

	endNode = new Node;
	endNode->x = m_endX;
	endNode->y = m_endY;
	endNode->father = NULL;
}

bool AStarPathFinding::pathFinding()
{
	//判断起始点和目标点是否是同一点
	if (m_startX == m_endX && m_startY == m_endY)
	{
		cout << "WARNNING : The start point is the same as th destination " << endl;
		return true;
	}

	OPENTable.push_back(startNode);//起始点装入OPEN表

	//对vector中元素进行排序:将最后一个元素加入原本已序的heap内
	push_heap(OPENTable.begin(),OPENTable.end(),HeapCompare_f());

	Node *tempNode = new Node;

	//开始遍历
	for (;;)
	{
		if (OPENTable.empty())//判断OPEN表是否为空
		{
			cout << "ERROR : unable to find the destination" << endl;
			return false;
		}

		tempNode = OPENTable.front();//注意:OPEN表为空会导致未定义行为
		++m_steps;
		//将第一个元素移到最后,并将剩余区间重新排序,组成新的heap
		pop_heap(OPENTable.begin(),OPENTable.end(),HeapCompare_f());
		OPENTable.pop_back();//删除最后一个元素

		//判断是否已经搜寻到目标节点
		if (tempNode->x == m_endX && tempNode->y == m_endY)
		{
			cout << "OK : success to find the destination" << endl;
			endNode->g = tempNode->g;
			endNode->h = tempNode->h;
			endNode->f = tempNode->f;
			endNode->father = tempNode->father;

			generatePath();

			return true;
		}
		
		for (int i = 0;i < 8;++i)//针对每个子节点
		{
			int nextX = tempNode->x + dx[i];
			int nextY = tempNode->y + dy[i];
			if (isIllegle(nextX,nextY))
			{
				//注意:障碍物角落不能直接通过
				if (1 == *(*(m_maze + tempNode->x) + nextY) ||
					1 == *(*(m_maze + nextX) + tempNode->y))
				{
					continue;
				}
				//计算此子节点的g值
				int newGVal;
				if (!dx[i] && !dy[i])//位于对角线上
				{
					newGVal = tempNode->g + 14;
				}
				else
					newGVal = tempNode->g + 10;

				//搜索OPEN表,判断此点是否在OPEN表中
				vector<Node*>::iterator OPENTableResult;
				for (OPENTableResult = OPENTable.begin();
					OPENTableResult != OPENTable.end();++OPENTableResult)
				{
					if ((*OPENTableResult)->x == nextX &&
						(*OPENTableResult)->y == nextY)
					{
						break;
					}
				}

				//此子节点已经存在于OPEN表中
				if (OPENTableResult != OPENTable.end())
				{
					//OPEN表中节点的g值已经是最优的,则跳过此节点
					if ((*OPENTableResult)->g <= newGVal)
					{
						continue;
					}
				}

				//搜索CLOSED表,判断此节点是否已经存在于其中
				vector<Node*>::iterator CLOSEDTableResult;
				for (CLOSEDTableResult = CLOSEDTable.begin();
					CLOSEDTableResult != CLOSEDTable.end();++CLOSEDTableResult)
				{
					if ((*CLOSEDTableResult)->x == nextX &&
						(*CLOSEDTableResult)->y == nextY)
					{
						break;
					}
				}

				//此节点已经存在于CLOSED表中
				if (CLOSEDTableResult != CLOSEDTable.end())
				{
					//CLOSED表中的节点已经是最优的,则跳过
					if ((*CLOSEDTableResult)->g <= newGVal)
					{
						continue;
					}
				}

				//此节点是迄今为止的最优节点
				Node *bestNode = new Node;
				bestNode->x = nextX;
				bestNode->y = nextY;
				bestNode->father = tempNode;
				bestNode->g = newGVal;
				bestNode->h = judge(nextX,nextY);
				bestNode->f = bestNode->g + bestNode->h;

				//如果已经存在于CLOSED表中,将其移除
				if (CLOSEDTableResult != CLOSEDTable.end())
				{
					delete (*CLOSEDTableResult);
					CLOSEDTable.erase(CLOSEDTableResult);
				}

				//如果已经存在于OPEN表,更新
				if (OPENTableResult != OPENTable.end())
				{
					delete (*OPENTableResult);
					OPENTable.erase(OPENTableResult);

					//重新建堆,实现排序。注意不能用sort_heap,因为如果容器为空的话会出现bug
					make_heap(OPENTable.begin(),OPENTable.end(),HeapCompare_f());
				}

				OPENTable.push_back(bestNode);//将最优节点放入OPEN表

				push_heap(OPENTable.begin(),OPENTable.end(),HeapCompare_f());//重新排序
			}
		}

		CLOSEDTable.push_back(tempNode);
	}

	return false;
}

void AStarPathFinding::generatePath()
{

	Node *nodeChild = endNode;
	Node *nodeParent = endNode->father;
	do 
	{
		*(*(m_path + nodeChild->x) + nodeChild->y) = NODE_PATH;//标记为路径上的点
		nodeChild = nodeParent;
		nodeParent = nodeParent->father;
	} while (nodeChild != startNode);

	*(*(m_path + startNode->x) + startNode->y) = NODE_PATH;//标记为路径上的点
}

void AStarPathFinding::printPath()
{
	cout << "The path is " << endl;
	for (int i = 0;i < m_rows;++i)
	{
		for (int j = 0;j < m_cols;++j)
		{
			if (NODE_PATH == *(*(m_path + i) + j))
			{
				cout << "# ";
			}
			else
				cout << *(*(m_maze + i) + j) << " ";
		}
		cout << endl;
	}

	cout << "搜索总步数:"  << m_steps << endl;
}

bool AStarPathFinding::readMap()
{
	//从文本文件读取迷宫布局信息
	ifstream mapFileStream(m_mapFileName);
	if (!mapFileStream)
	{
		cerr << "ERROR : unable to open map file" << endl;
		return false;
	}

	mapFileStream >> m_rows >> m_cols;

	//多维数组空间分配
	m_maze = new int *[m_rows];
	for (int i = 0;i < m_rows;++i)
	{
		m_maze[i] = new int[m_cols];
	}

	mapFileStream >> m_startX >> m_startY;
	mapFileStream >> m_endX >> m_endY;

	for (int i = 0;i < m_rows;++i)
	{
		for (int j = 0;j < m_cols;++j)
		{
			mapFileStream >> *(*(m_maze + i) + j);
		}
	}

	return true;
}

int AStarPathFinding::judge(int x, int y)
{
	return (10 * (abs(m_endX - x) + abs(m_endY - y)));
}

bool AStarPathFinding::isIllegle(int x, int y)
{
	if (x >= 0 && x < m_rows &&
		y >= 0 && y < m_cols &&
		*(*(m_maze + x) + y) == 0)
		return true;
	else
		return false;
}


针对上面的迷宫问题的搜索结果:

注意:'#'代表该节点是路径上的点。


参考资料:

A*寻路初探 GameDev.net


1楼r10101010前天 12:28
同行,顶一个

文章评论

看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
Java 与 .NET 的平台发展之争
Java 与 .NET 的平台发展之争
为什么程序员都是夜猫子
为什么程序员都是夜猫子
当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
5款最佳正则表达式编辑调试器
5款最佳正则表达式编辑调试器
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
程序员应该关注的一些事儿
程序员应该关注的一些事儿
10个调试和排错的小建议
10个调试和排错的小建议
每天工作4小时的程序员
每天工作4小时的程序员
如何成为一名黑客
如何成为一名黑客
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
Java程序员必看电影
Java程序员必看电影
程序员的鄙视链
程序员的鄙视链
代码女神横空出世
代码女神横空出世
 程序员的样子
程序员的样子
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
老程序员的下场
老程序员的下场
一个程序员的时间管理
一个程序员的时间管理
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
我是如何打败拖延症的
我是如何打败拖延症的
如何区分一个程序员是“老手“还是“新手“?
如何区分一个程序员是“老手“还是“新手“?
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
那些争议最大的编程观点
那些争议最大的编程观点
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
旅行,写作,编程
旅行,写作,编程
编程语言是女人
编程语言是女人
“懒”出效率是程序员的美德
“懒”出效率是程序员的美德
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
我的丈夫是个程序员
我的丈夫是个程序员
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
总结2014中国互联网十大段子
总结2014中国互联网十大段子
程序员都该阅读的书
程序员都该阅读的书
鲜为人知的编程真相
鲜为人知的编程真相
科技史上最臭名昭著的13大罪犯
科技史上最臭名昭著的13大罪犯
团队中“技术大拿”并非越多越好
团队中“技术大拿”并非越多越好
什么才是优秀的用户界面设计
什么才是优秀的用户界面设计
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有