AStar算法的一种实现

freeeyes

最近两天，同事都没有回来，自己有点时间，于是翻看以前的一些代码。以前写的一个网游，看到地图场景加载和事件触发，忽然想看看有没有能力组成一个通用的组件。其实，走路，NPC事件触发，广播以及状态变化几乎在每一个MMO里面都是要面临一样的问题。这部分其实完全可以通用化。
要想做到这一点，场景管理，地图加载，寻路，广播是其中的四个主要功能点。有时间写一个通用的共享给大家，呵呵，一步步来。
不过以前的工程代码比较乱，重新整理需要一点时间，看以前其他同事写的AStar算法（一种最短路径的求值方法），代码较多，还用到了二叉树，看了半天，感觉比较费力。（以前没有写过astar算法），于是翻看网上的AStar的其他算法，不知道是不是自己太笨还是别的什么原因，我不明白为什么很多网上的例子，要不不能用，要不就是代码异常复杂，给读者造成了很大的困难。
于是自己尝试写了一个，当然还只是框架，半天功夫倒腾出来一个，貌似架构比网上的好读一些，而且可以支持测试，实现考虑了未来跨平台的可能，于是尽量使用通用化的C++去实现。同时，根据AStar的算法，尽量做了一些优化。
贴在这里，如果大家有兴趣可以玩玩。
AStar的原理，其实很简单，其核心算法就是权值的问题。具体的算法请参考
http://www.acejoy.com/bbs/viewthread.php?tid=3041&extra=page%3D1

其实，根据如上的描述，AStar是很简单的。
先定义一些自己需要的中间结构体

1. //地图节点
2. struct _World
3. {
4.         BYTE m_bState;          //节点状态，1是可以通过，0是不能通过
5.         BYTE m_bRoute;          //节点范围
7.         int  m_nRow;            //行标记
8.         int  m_nCol;            //列标记
9.         int  m_nIndex;          //当前区块ID
11.         _World():m_bState(0), m_bRoute(4), m_nRow(0), m_nCol(0), m_nIndex(0)
12.         {
13.         }
14. };
16. //坐标信息
17. struct _WorldPos
18. {
19.         int  m_nRow;
20.         int  m_nCol;
22.         _WorldPos():m_nRow(0), m_nCol(0)
23.         {
24.         }
25. };
27. //位置字典信息
28. struct _DX
29. {
30.         short m_nCost;      //权值
31.         short m_nIndex;     //对应的位置ID
32.         int   m_nInterval;  //和*点的节点差距
33. };
35. //计算中的权值和节点位置对应关系结构
36. struct _WorldCostInfo
37. {
38.         int m_nWorldIndex;
39.         int m_nWorldCost;
40. };
42. typedef vector<_World*> vecPath;
44. //路线节点信息
45. struct _NodePath
46. {
47.         vecPath m_vecPath;     //路线节点信息
48. };

复制代码

_World：是地图中的一个点的信息，包括横纵坐标，是否可以走，当前的Index(相对起始点的偏移)
_WorldPos：我们姑且认为，用户传入的是两个坐标点，里面包含X和Y，其实AStar可以扩展到三个轴向的计算，不过这会引起计算量的成倍增长。目前先讨论二维地图的情况。
_DX：这个结构体，是一个格子，周围给定的8个格子的信息，为了方便未来的计算，这里先算好，以后计算中直接从中去取比较方便。
_WorldCostInfo：这个结构体其实完全可以封在CPathFinder的Private里面。这是在计算权值中间状态时的一个结构体，外围程序完全不用知道它的存在。
_NodePath：这个结构体会存放找到的路线节点信息。穿成一个串，用于路线的返回。

建立一个类，姑且叫做CPathFinder

1. class CPathFinder
2. {
3. public:
4.         CPathFinder(void);
5.         ~CPathFinder(void);
7.         void Init();
8.         void Close();
10.         bool AStarFind(const _WorldPos PosStart, const _WorldPos PosEnd, _NodePath*& pNodePath);
12. private:
13.         _World* CalculateEightQueen(const _World* pTarget, const _World* pEnd);
14.         inline void CalculateCost(const int nTarget, const int nEnd, const int nIndex, _WorldCostInfo& nMinIndex);
15.         inline int CalculateDirect(const _World* pTarget, const _World* pEnd);
17. private:
18.         _World* m_pWorld;
19.         int     m_nMapWidth;
20.         int     m_nMapHeight;
21.         int     m_nMaxGridCount;
22.         _DX*    m_pDX;
23. };

复制代码

这里的Init是架在地图，这里完全可以做成读取文件，fopen等等，这里为了简化，先用一个循环替代。
Close方法顾名思义，就是用完了这个类完成的清空动作。
对外只提供一个方法，AStarFind()
//PosStart是起始点，PosEnd是终点，pResult是路线中经过所需要的节点位置链表
函数返回一个bool，会告诉使用者astar是否寻路成功。

私有函数只有三个
CalculateEightQueen()负责计算给定格子周围的8个格子的权值。
CalculateCost()计算给定格子到目标格子之间的估算权值，这里使用了曼哈顿方法进行估算。
CalculateDirect()计算指定格子到目标个字的角度，目前角度一共有8个，对应周围的8个格子。
具体实现代码不在这里贴了，有兴趣的可以读读我的附件。


写了一个测试

1. int main(int argc, char* argv[])
2. {
3.         printf("[main]Begin.\n");
4.         _ENTER_FUNCTION
6.         CPathFinder PathFinder;
7.         PathFinder.Init();
9.         _WorldPos PosBegin;
10.         _WorldPos PosEnd;
11.         _NodePath* pNodePath = new _NodePath();
13.         PosBegin.m_nRow = 1;
14.         PosBegin.m_nCol = 0;
16.         PosEnd.m_nRow = 3;
17.         PosEnd.m_nCol = 0;
19.         _ENTRYTIME
20.         PathFinder.AStarFind(PosBegin, PosEnd, pNodePath);
21.         _LEAVETIME
22.                
23.         if(pNodePath->m_vecPath.size() > 0)
24.         {
25.                 for(int i = 0; i < (int)pNodePath->m_vecPath.size(); i++)
26.                 {
27.                         printf("[Main]Find Path(%d, %d)\n", pNodePath->m_vecPath[i]->m_nRow, pNodePath->m_vecPath[i]->m_nCol);
28.                 }
29.         }
30.         else
31.         {
32.                 printf("[Main]AStar fail,sorry.\n");
33.         }
35.         _LEAVE_FUNCTION
37.         getchar();
38.         return 0;
39. }

复制代码

这里我创建了一个100*100的地图世界，故意造成了一个阻挡，0,2格子的组个，我从0,1到0，3，看看它是否会给我绕道。
返回结果是


[main]Begin.
[TimeCost]Cost = 0.
[Main]Find Path(1, 2)
[Main]Find Path(0, 3)

这里为了计算我的AStar的时间成本，我写了两个宏。
_ENTRYTIME和_ENTRYTIME
这两个宏会显示被包含的代码执行时间。
因为aStar的算法比较消耗循环，所以，我按照常理，给AStar增加了一个最大计算步数的限制，防止搜索过大的地图造成的时间消耗过长，从而影响用户的体验，这里你可以通过修改MAX_ASTAR_COUNT这个参数达到，由于系统硬件不同，你可以测试这段代码在你的本机上多少半径作为合理数值。

呵呵，有兴趣的可以跑一下，遇到问题，可以在这里留言。
本代码在winXP+VS2005下测试用过。