游戏中经常会用到寻径算法，最简单的寻径算法就是走直线或者总是往最接近目的地的方向走，遇到障碍物就不可以继续前进。这样虽然得到的路线一定是最短的，但是一旦碰到障碍物就被卡住了，显然不够灵活。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
BFS用来产生唯一路径、全部连通的迷宫不错~
DFS吧！！！我是用DFS实现的
嗯，DFS
另：我最早看的A星算法也是看的你最后发的那个链接里的那篇。。。。。。。
那个文章有很多年历史了，已经成为入门经典！
厉害….顶顶，急需发一些多线程的东西嘛….
你的意思是……写一些关于多线程的介绍？
是啊….我记得你会的啊…但是我不知道你放在那里的呢？？？简单为好
Linux上的还是Windows上的？
我改天写一些pthread的用法吧，你会用一些多线程基本概念的东西，再接触别的库都很容易了，关键是要积累经验，特别是对线程锁的使用。
恩恩…….其实之前也看了很多啦….知识需要实践…
是啊….我记得你会的啊…但是我不知道你放在那里的呢？？？简单为好
写好了，发表了，评论吧！