用C++和libSDL开发游戏系列(3) – 简单A*算法寻径

游戏中经常会用到寻径算法,最简单的寻径算法就是走直线或者总是往最接近目的地的方向走,遇到障碍物就不可以继续前进。这样虽然得到的路线一定是最短的,但是一旦碰到障碍物就被卡住了,显然不够灵活。BFS、A*是最常见的路径寻找算法。BFS算法从起始点一直向周围辐射扩张盲目地寻找目的地,虽然找到的路径一定是最短路,但是效率不高。A*算法加入了对每个发现了的位置的评估,选择与目的地接近的方向搜索,比较灵活,效率也很高。

A*算法是改进的BFS(宽度优先搜索)算法,区别在于A*算法在搜索下一个点的时候,会在等待搜索的点中寻找一个最优的。这里最优的意味着,最容易到达目的地。最简单的一个评估方法是,看当前位置到目的地还有多远。

设f(x, y)为对位置(x, y)的评估函数,g(x, y)为从起始点到当前点所经过的路程,h(x, y)为从当前点到目的地还需要的大概路程。则f的表达式可以为f(x, y) = g(x, y) + h(x, y)

以下面这个地图为例,比较BFS和A*的差异。

19 33
 ############################### 
 #                       #     # 
 #                       #     # 
 #                       #  @  # 
 #                       #     # 
 #                       #     # 
 #     #     #######     ### ### 
 #     #     #           #     # 
 #     #     #           #     # 
 #     #     #        x  #     # 
 #     #     #           #     # 
 #     #     #           #     # 
 #     #     #######     #     # 
 #                             # 
 #                             # 
 #                             # 
 #                             # 
 #                             # 
 ############################### 

地图中,#表示障碍物,x表示起始位置,@表示终点,.表示搜索过的位置,*表示最终找到的路径。
假设地图上的怪物只可以上下左右四个方向移动。

下面是使用BFS寻径得到的结果:

Found a path which needs 21 steps.
 ###############################
 #        ...............#     #
 #       ................#     #
 #      .................#  @  #
 #     ..................#  *  #
 #    ...................# .*. #
 #     #.....#######.....###*###
 #     #.....#...........#***..#
 #     # ....#...........#*....#
 #     #  ...#...........#*....#
 #     #  ...#........*..#*....#
 #     # ....#........*..#*....#
 #     #.....#######..*..#*....#
 #     ...............*****....#
 #     ........................#
 #      .......................#
 #       ......................#
 #        .....................#
 ###############################

下面是使用A*算法寻径的结果:

Found a path which needs 21 steps.
 ###############################
 #                  .....#     #
 #                 ......#     #
 #                .......#  @  #
 #                .......#  *  #
 #                .......#  *  #
 #     #     #######.....###*###
 #     #     #    .......#***  #
 #     #     #    .......#*..  #
 #     #     #    .....**#*..  #
 #     #     #     .....*#*..  #
 #     #     #      ....*#*..  #
 #     #     ####### ...*#*..  #
 #                    ..***..  #
 #                             #
 #                             #
 #                             #
 #                             #
 ###############################

使用BFS算法得到的一定是最短路径,但是用A*得到的不一定是最短路径,因为在A*中加入了猜测,而猜测不一定是正确的。有可能比最短路径多走了一些弯路。但是,在效率上,A*远远胜过BFS。从上面的例子可以看出,如果目的地再远一点,BFS算法就要搜索完整张地图了!如果地图设计得很大的话,需要的代价也是非常高。

假如始末位置之间没有障碍物,A*可以直接迫近目的地。

Found a path which needs 11 steps.
 ###############################
 #                       #     #
 #                       #     #
 #                       #     #
 #        .              #     #
 #        *              #     #
 #     #  *  #######     ### ###
 #     #  *  #           #     #
 #     #  *  #           #     #
 #     #  *  #           #     #
 #     #  *  #           #     #
 #     #  *  #           #     #
 #     #  *  #######     #     #
 #        *                    #
 #        @                    #
 #                             #
 #                             #
 #                             #
 ###############################

对于BFS,会向周围辐射它的搜索范围。

Found a path which needs 11 steps.
 ###############################
 # ...............       #     #
 #.................      #     #
 #..................     #     #
 #..................     #     #
 #........*........      #     #
 # ....#..*..#######     ### ###
 #  ...#..*..#           #     #
 #   ..#..*..#           #     #
 #    .#..*..#           #     #
 #     #..*..#           #     #
 #     #..*..#           #     #
 #     # .*. #######     #     #
 #        *                    #
 #        @                    #
 #                             #
 #                             #
 #                             #
 ###############################

评估函数的正确选取,会对寻径有很大的帮助。例如游戏中有的地方有沼泽或者雪地,开发者希望怪物可以绕开这些障碍物通过,迫不得已才走沼泽地或者雪地,则可以给地图上的不同地方设置不同的权值,作为评估函数的其中一个参数。

不同的评估函数对路径的选择也不尽相同。如果在评估的时候不加入之前走过的路程作为参考,直接衡量当前位置到目的地的距离,最终生成的路径虽然是弯路,但是比较真实,即碰壁后再掉头走。而不会有怪物对地理位置非常熟悉,总是能找到最短路的感觉。

Found a path which needs 33 steps.
 ###############################
 #              .........#     #
 #             ..........#     #
 #            ........***#  @  #
 #             .......*.*#  *  #
 #              ......*.*#  *  #
 #     #     #######..*.*###*###
 #     #     #    ....*.*#***  #
 #     #     #     ...*.*#*    #
 #     #     #      ....*#*    #
 #     #     #       ...*#*    #
 #     #     #        ..*#*    #
 #     #     #######   .*#*    #
 #                      ***    #
 #                             #
 #                             #
 #                             #
 #                             #
 ###############################

下面给出A*算法的C++代码,找到的路径保存在path堆栈中。使用堆栈保存路径点便于打印一条从起点到终点方向的路径。而游戏中的怪物只需要按照这条路径行走即可。一般来说,如果目标位置没有发生改变或者改变不大,都不需要重新寻径。曾经看过某同学的游戏里,每一秒钟就对所有的怪物使用BFS重新寻找路径,这样运行游戏的时候每一秒钟就卡一下,玩起来一点也不爽~~如果地图不是非常非常的复杂,使用A*寻径的代价是比较低的,在经过优化的算法中,它的时间复杂度可以达到O(n*logn)。

#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;

// #define BFS

/* Basic structure used in A* algorithm */
struct Point{ 
	int x, y; 
	Point(){} 
	Point(int __x, int __y){ x = __x, y = __y; }
	int getDistanceFrom(const Point& __p){ return abs(x - __p.x) + abs(y - __p.y); }
};

/* 搜寻过的点 */
struct ClosedPoint: Point{ 
	int previous; 
	ClosedPoint(Point& __p, int __pre): Point(__p), previous(__pre) {} 
};

/* 发现过用于评估的点 */
struct OpenPoint: ClosedPoint{ 
	int distanceToSource, distanceToTarget, assessValue; 
	OpenPoint(Point & __p, int __pre, int __ds, int __dt) : ClosedPoint(__p, __pre), 
		distanceToSource(__ds), distanceToTarget(__dt), assessValue(__dt + __ds) {}
};

/* Map Information */
const int MaxRows = 100, MaxColumns = 200;
int columns, rows;
char map[MaxRows][MaxColumns];
/* 出发点和终点信息 */
Point startPoint, endPoint;
stack<Point> path;
/* 寻径方向 */
int direction[4][2] = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};

/* Look for a path with Astar Algroithm */
bool findPath()
{
	/* open列表用于存放已经发现的节点,并记录这些节点的评估值。每次前进都从列表中找到
	 * 评估值最优的节点。
	 * closed列表用于存放已经搜索过的节点,这里也可以使用STL set来实现 */
	vector<OpenPoint> openList;
	vector<ClosedPoint> closedList;
	
	/* 首先把起始位置放进open列表,上一个节点位置为-1,与始点相距0,
	 * 与目的地相距即为始末距离 */
	openList.push_back(OpenPoint(startPoint, -1, 0, startPoint.getDistanceFrom(endPoint)));
	
	/* 检查发现的节点 */
	while(!openList.empty()){
		
		/* 在已发现节点列表里选择一个评估值最优的节点 */
		vector<OpenPoint>::iterator current = openList.begin();
#ifndef BFS
		for(vector<OpenPoint>::iterator it=openList.begin(); it!=openList.end(); it++)
			if(it->assessValue < current->assessValue)
				current = it;
#endif
		
		/* 检查是否到达终点 */
		if(current->x == endPoint.x && current->y == endPoint.y){
			/* 逆向获取路径 */
			path.push(endPoint);
			int previous = current->previous;
			while(previous != -1){
				path.push( *(closedList.begin() + previous) );
				previous = (closedList.begin() + previous)->previous;
			}
			return true;
		}
		
		/* 添加到已搜寻列表 */
		OpenPoint currentPoint = *current;
		openList.erase(current);
		closedList.push_back(currentPoint);
		map[currentPoint.y][currentPoint.x] = '.';
		
		/* 往各个方向寻找 */
		for(int i=0; i<4; i++){
			int nextX = currentPoint.x + direction[i][0];
			int nextY = currentPoint.y + direction[i][1];
			Point newPoint(nextX, nextY);
			
			/* 边界检查 */
			if(nextX < 0 || nextY < 0 || nextX >= columns || nextY >= rows || map[nextY][nextX] == '#')
				continue;
				
			/* 是否已经搜寻过该节点 */
			for(vector<ClosedPoint>::iterator it=closedList.begin(); it!=closedList.end(); it++)
				if(it->x == nextX && it->y == nextY)
					goto SearchNext;
					
			/* 是否已经发现过该节点 */
			for(vector<OpenPoint>::iterator it=openList.begin(); it!=openList.end(); it++)
				if(it->x == nextX && it->y == nextY)
					goto SearchNext;
					
			/* 添加到发现列表 */
			openList.push_back(OpenPoint(newPoint, closedList.size()-1, 
				currentPoint.distanceToSource+1, endPoint.getDistanceFrom(newPoint)));
			
SearchNext:;
		}
	}
	
	/* 无法找到路径 */
	return false;
}

void printMap()
{
	for(int i=0; i<rows; i++){
		for(int j=0; j<columns; j++)
			cout << map[i][j];
		cout << endl;
	}
	cout << endl;
}

int main(int argc, char **argv)
{
	cin >> rows >> columns;
	for(int i=0; i<rows; i++)
		for(int j=0; j<columns; j++){
			int ch = cin.get();
			switch(ch){
			case '\r':
			case '\n':
				j--;
				continue;
			case 'x':
				startPoint = Point(j, i);
				break;
			case '@':
				endPoint = Point(j, i);
				break;
			}
			map[i][j] = ch;
		}
	
	findPath();
	
	if(findPath){
		cout << "Found a path which needs " << path.size() << " steps." << endl;
		while(path.pop(), !path.empty())
			if(map[path.top().y][path.top().x] == '.')
				map[path.top().y][path.top().x] = '*';
		printMap();
	}
	return 0;
}

最后推荐一篇图文并茂介绍A*算法入门文章,
A* Pathfinding for Beginners:
http://www.policyalmanac.org/games/aStarTutorial.htm

用C++和libSDL开发游戏系列(3) – 简单A*算法寻径》上有12条评论

        1. Xiaoxia 文章作者

          Linux上的还是Windows上的?
          我改天写一些pthread的用法吧,你会用一些多线程基本概念的东西,再接触别的库都很容易了,关键是要积累经验,特别是对线程锁的使用。

          回复

发表评论

电子邮件地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>