本文由提供，转载请说明出处：
http://blog.csdn.net/crocodile__/article/details/18842739
我的邮箱：bluecoder@yeah.net 欢迎大家和我交流游戏编程心得
我的微博：BlueCoder_黎小华 欢迎光临
上期呢，我用C++写了一个简易框架BCF，从今起呢，我就会继续使用它来写游戏效果……
如果还没瞧见过BCF的朋友，请先看看BCF的庐山真面目吧：
【VC++游戏开发十一】用C++来架构一个适合windows游戏编程的框架——取名为BCF
今天我们来聊一聊游戏中最常见的一种AI(Artificial Intelligence，人工智能)：寻路 —— 最短路径 & 智能越过障碍
言下之意，就是人物能智能寻找到达目的地的最短路径，并能够越过障碍
这些功能在程序背后是有很多种算法可以来支撑的，可能大家最熟悉的就是A*算法，还有深度优先、广度优先搜索算法、递归、回溯…… 而本次呢，我决定先讲一个较为简单的算法 —— 回溯+递归
这个算法来的也很蹊跷，去年参加了一个程序设计竞赛，里面有类似的寻找最短路径的算法题，当时我想到的也就是今天要讲到的这个算法，不过我现在优化了许多
下面，我们切入正题……
想必你很像提前阅览一下程序效果吧？呵呵，那我们就先一睹为快：(截图中加入一些说明，方便阅览)
可以发现，人物是按照最短路径到达了目的地，并越过了途中的障碍。还有一点就是，当鼠标点击的位置是障碍点时，是不能到达的：
一、封装的C++类
类图如下：
可见，工程中有四个类(全为BlueCoder自己写的C++类)：
1、CCWindow类：熟悉BCF的朋友，应该知道这个类就是负责窗口的创建、消息的路由，整个程序的控制
2、CPathFind类：负责寻路(寻找最短可行路径)
3、CRole类：负责人物角色的控制(人物移动、切换下一帧构成动画==)
4、CScene类：负责场景的控制(贴地图、播放背景音乐)
二、回溯+递归寻路算法(重点)
用 回溯+递归 的算法进行深度优先搜索，将所有可行的路径进行比较，找出最短路径
这个算法，如前所诉，我封装一个c++类CPathFind，先看一看该类的定义：
class CPathFind { private: static const int BLOCK = 0; //障碍(不能通过) static const int PASS = 1; //非障碍(能通过) static const int YES = 1; //是否遍历(是) static const int NO = 0; //是否遍历(否) static const int R = 6; //行 static const int C = 7; //列 static int path[R][C]; //保存地图路径 private: int path_through[R][C]; //经过的当前最短路径 int least_path[R][C]; //最短路径 int least; //最短路径长度 PT end; //终点 public: bool IsPass(int i, int j); //是否能通过当前点 void Initial(); //初始化 void SetEndPoint(int i, int j); //设置终点 void GetCurLeastPath(); //获取当前最短路径 void PathFinding(int i, int j, int count); //回溯法计算最短路径 bool IsNext(int i, int j); //是否是下一个结点 int GetNextNode(int &i, int &j);//获取最短路径中的下一个结点 public: CPathFind(void); ~CPathFind(void); };
补充一点：为了让地图和实际寻路的路径关联，我们需要一个二维数组保存地图中对应的路径(0表示不能通过的障碍，1表示可通过的点)
如下：
//初始化路径(1表示能走, 0表示不能走(障碍)) int CPathFind::path[R][C] = { 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, };对应于地图中的路径状态：
具体的算法思路如下：
基本思路就是遍历所有的点，遇到不可行的点，就回溯到上一个点继续遍历。分步骤讲述如下：
(1)、从起点开始遍历，继续(2)。
(2)、如果当前点可以通过(即不是障碍点、且没有出边界)，那么继续(3)；否则，返回上一层。
(3)、如果还有未遍历到的方向(前后左右)，就继续(4)；否则，跳到(6)。
(4)、如果遍历到终点后，继续(5)；否则跳到(2)继续。
(5)、遍历到终点，比较当前获得的路径长度是不是比之前获得的要短，若是就记录；否则不管 。回溯到前一个点，回到(3)。
(6)、所有的可行路径都遍历完毕。
结合上面的步骤来看一看核心算法代码：
//回溯法递归寻找最短路径 void CPathFind::PathFinding(int i, int j, int count) { //如果能通过 if(IsPass(i, j)) { //如果遍历到了终点 if(i == end.i && j == end.j) { if(count < least) { //获取当前的最短路径, 最后一次获取的就一定是最短路径了 path_through[i][j] = YES; GetCurLeastPath(); path_through[i][j] = NO; least = count; } return;//返回上一层，继续遍历 } //标记当前节点已经遍历了 path[i][j] = BLOCK; path_through[i][j] = YES; //向各个方向遍历 PathFinding(i, j-1, count+1);//左(西) PathFinding(i, j+1, count+1);//右(东) PathFinding(i+1, j, count+1);//前(南) PathFinding(i-1, j, count+1);//后(北) /* 回溯时，取消标记已经遍历的点，设为允 许通过(因为其它方向也有可能遍历这些点 ，不能互相影响各个方向之间的遍历) */ path[i][j] = PASS; path_through[i][j] = NO; } }
三、UI类的代码剖析
下面分别讲述一下各个类的实现过程
<1>、场景CScene类：负责贴地图、播放背景音乐=
1>、头文件中的定义
class CScene { private: static const int R = 6;//行 static const int C = 7;//列 private: CImage m_map; //地图 CRect m_client; //窗口客户区 public: bool InitScene(); //初始化场景 void SetClientRect(CRect); //设置客户区大小 CSize GetBlockSize(); //获取每一块方块的大小 void PaintScene(CDC &); //绘制场景 void ReleaseScene(); //释放内存资源 public: CScene(void); ~CScene(void); };2>、成员函数的实现
//初始化场景 bool CScene::InitScene() { m_map.Load("res\\地图.png"); if(m_map.IsNull()) { return false; } //打开并播放背景音乐 mciSendString("open res\\bgm.mp3 alias bgm", 0, 0, 0); mciSendString("play bgm repeat", 0, 0, 0); return true; } //设置窗口客户区大小 void CScene::SetClientRect(CRect wndRect) { m_client = wndRect; } //获取每一块方块的大小 CSize CScene::GetBlockSize() { return CSize( m_client.Width() / C, m_client.Height() / R); } //绘制场景 void CScene::PaintScene(CDC &dc) { dc.SetStretchBltMode(COLORONCOLOR); m_map.StretchBlt(dc, 0, 0, m_client.Width(), m_client.Height(), SRCCOPY); } //释放内存资源 void CScene::ReleaseScene() { m_map.Destroy(); mciSendString("close bgm", 0, 0, 0); }<2>、人物角色CRole类：负责人物角色的逻辑控制
1>、头文件中的定义
class CRole { private: CImage m_img; //角色人物 CRect m_client; //窗口客户区大小 CPoint m_pos; //人物位置 int m_maxFrame; //最大帧 int m_curFrame; //当前帧 DIRECTION m_direct; //方向 public: bool InitRole(CString, int);//初始化角色 void SetClientRect(CRect); //设置窗口客户区大小 void SetPos(CPoint, CSize); //设置位置 void SetDirection(int); //设置方向 void NextFrame(); //下一帧 void PaintRole(CDC &); //绘制角色 void ReleaseRole(); //释放操作 public: CRole(void); ~CRole(void); };2>、成员函数的实现
先着重说一下人物位置的设定，先来看一张简易示意图：
然后结合实现代码再看一看：
//设置人物位置 void CRole::SetPos(CPoint point, CSize size) { int w = m_img.GetWidth() / m_maxFrame; int h = m_img.GetHeight() / 4; m_pos.x = point.x + size.cx / 2 - w / 2; m_pos.y = point.y + size.cy / 2 - h + 50; }
所有的函数成员的实现：
//初始化角色 bool CRole::InitRole(CString pngPath, int frame) { m_img.Load(pngPath); if(m_img.IsNull()) { return false; } m_maxFrame = frame; m_curFrame = 0; m_direct = SOUTH; return true; } //设置窗口客户区大小 void CRole::SetClientRect(CRect wndRect) { m_client = wndRect; } //设置人物位置 void CRole::SetPos(CPoint point, CSize size) { int w = m_img.GetWidth() / m_maxFrame; int h = m_img.GetHeight() / 4; m_pos.x = point.x + size.cx / 2 - w / 2; m_pos.y = point.y + size.cy / 2 - h + 50; } //设置方向 void CRole::SetDirection(int direct) { m_direct = (DIRECTION)direct; } //下一帧 void CRole::NextFrame() { m_curFrame++; if(m_curFrame == m_maxFrame) { m_curFrame = 0; } } //绘制角色 void CRole::PaintRole(CDC &dc) { int w = m_img.GetWidth() / m_maxFrame; int h = m_img.GetHeight() / 4; int x = m_curFrame * w; int y = h * m_direct; //透明贴图 m_img.TransparentBlt(dc, m_pos.x, m_pos.y, w, h, x, y, w, h, RGB(255, 255, 255)); } //释放操作 void CRole::ReleaseRole() { m_img.Destroy(); }<3>、CCWindow类：负责窗口的窗口、消息路由
1>、类定义就不多说了，前一篇文章中已经详细讲解过。这里就把变化的地方贴出来：
//==================成员==================== private: WNDCLASS m_wndclass; //窗口类结构体实例 public: HWND m_hwnd; //窗口句柄 CRect m_rect; //窗口户区大小 CScene m_scene; //场景 CRole m_man; //人物 CPathFind m_pathFind; //寻路 int curi;//当前点[i][j] int curj; bool isMoving;//人物是否在移动中2>、消息的路由：对消息的响应
//---------------------------------------------------------- // 消息响应函数 //---------------------------------------------------------- //WM_CREATE消息 void CCWindow::OnCreate() { //如果初始化失败 if(!m_scene.InitScene() || !m_man.InitRole("res\\man.png", 8)) { MessageBox(m_hwnd, "png加载失败", "提示", MB_OK); exit(0); } curi = 3;//初始化起点 curj = 1; //人物一开始还未移动 isMoving = false; //创建计时器 SetTimer(m_hwnd, ID_PAINTROLE, 120, NULL); } //WM_SIZE消息 void CCWindow::OnSize() { //获取客户区大小 GetClientRect(m_hwnd, m_rect); m_scene.SetClientRect(m_rect); m_man.SetClientRect(m_rect); CSize sBlock = m_scene.GetBlockSize(); //初始化人物状态(方向、位置) m_man.SetDirection(SOUTH); m_man.SetPos( CPoint(sBlock.cx * curj, curi * sBlock.cy), sBlock); } //WM_TIMER消息 void CCWindow::OnTimer(WPARAM wParam) { switch(wParam) { //绘制角色 case ID_PAINTROLE: m_man.NextFrame(); break; //移动人物 case ID_MOVEROLE: { //获取最短路径的下一个结点 int direct = m_pathFind.GetNextNode(curi, curj); //到达终点时(没有获取到方向)，停止移动人物 if(direct == NODTN) { KillTimer(m_hwnd, ID_MOVEROLE); isMoving = false; return; } else//未到达终点，继续移动 m_man.SetDirection(direct); CSize sBlock = m_scene.GetBlockSize(); //设置角色的位置 m_man.SetPos( CPoint(sBlock.cx * curj, curi * sBlock.cy), sBlock); } break; } InvalidateRect(m_hwnd, NULL, false);//重绘 } //WM_PAINT消息 void CCWindow::OnPaint() { CPaintDC dc(CWnd::FromHandle(m_hwnd)); CDC bufferDC; CBitmap bufferBmp; //双缓冲贴图 bufferDC.CreateCompatibleDC(NULL); bufferBmp.CreateCompatibleBitmap(&dc, m_rect.Width(), m_rect.Height()); bufferDC.SelectObject(bufferBmp); m_scene.PaintScene(bufferDC);//绘制场景 m_man.PaintRole(bufferDC); //绘制人物 dc.BitBlt(0, 0, m_rect.Width(), m_rect.Height(), &bufferDC, 0, 0, SRCCOPY); bufferBmp.DeleteObject(); bufferDC.DeleteDC(); } //WM_LBUTTONDOWN消息(重点) void CCWindow::OnLButtonDown(LPARAM lParam) { //如果人物没在移动 if(!isMoving) { CPoint lMouse;//获取鼠标左键点击的位置 lMouse.x = LOWORD(lParam); lMouse.y = HIWORD(lParam); //方块大小 CSize sBlock = m_scene.GetBlockSize(); //寻找鼠标左键点击的方块(目的地) for(int i=0; i<6; i++) { for(int j=0; j<7; j++) { CPoint point(sBlock.cx * j, i * sBlock.cy); CRect rect(point, sBlock); //找到鼠标点击的方块 if(rect.PtInRect(lMouse)) { //如果点击方块是能通过的(非障碍点) if(m_pathFind.IsPass(i, j)) { SetTimer(m_hwnd, ID_MOVEROLE, 800, NULL); //寻路 m_pathFind.Initial();//先初始化 m_pathFind.SetEndPoint(i, j);//设置终点 m_pathFind.PathFinding(curi, curj, 0);//开始寻找最短路径 //设置人物的位置 m_man.SetPos( CPoint(sBlock.cx * curj, curi * sBlock.cy), sBlock); isMoving = true;//此时人物开始移动 } else { //障碍点就提示一下 MessageBox(m_hwnd, "目的地是障碍点，不能到达", "提示(By BlueCoder)", MB_OK); } return;//处理完毕直接退出 } } } } } //WM_KEYDOWN消息 void CCWindow::OnKeyDown(WPARAM wParam) { //按下Esc键退出 if(wParam == VK_ESCAPE) { DestroyWindow(m_hwnd); } } //WM_DESTROY消息 void CCWindow::OnDestroy() { KillTimer(m_hwnd, ID_PAINTROLE); KillTimer(m_hwnd, ID_MOVEROLE); m_scene.ReleaseScene(); m_man.ReleaseRole(); PostQuitMessage(0); }
四、你期待的零积分学习资源
请稍后……
BlueCoder在这里感谢大家对此专栏【VC++游戏开发】的关注，也希望大家继续关注，并诚邀各位留下你的宝贵意见，你的忠言、我的回复就构成了交流，促进我们共同地进步，向游戏梦想更近一步
最后，依旧送上一段箴言，我觉得还不错^_^：
1、容易走的，都是下坡路。
2、自由不是想干什么就干什么，而是想不干什么就不干什么。
3、命，是失败者的借口；运，是成功者的谦词。
4、打动人心的最佳方法，是谈他最珍爱的东西。
5、品格不由你占有的东西决定，而是由你匮乏的东西塑造的。
6、郁闷时，坐下来犒劳自己，原谅别人，也放过自己。
今日游戏效果模拟到此结束……
新年将至，在这里预祝大家新年快乐，马年吉祥，马上有钱，哈哈：）
??
【VC++游戏开发十二】2D篇 —— 人工智能(二)：最短路径 & 智能越过障碍 By BlueCoder
原文：http://blog.csdn.net/crocodile__/article/details/18842739
