AStar算法的一种实现
最近两天，同事都没有回来，自己有点时间，于是翻看以前的一些代码。以前写的一个网游，看到地图场景加载和事件触发，忽然想看看有没有能力组成一个通用的组件。其实，走路，NPC事件触发，广播以及状态变化几乎在每一个MMO里面都是要面临一样的问题。这部分其实完全可以通用化。要想做到这一点，场景管理，地图加载，寻路，广播是其中的四个主要功能点。有时间写一个通用的共享给大家，呵呵，一步步来。
不过以前的工程代码比较乱，重新整理需要一点时间，看以前其他同事写的AStar算法（一种最短路径的求值方法），代码较多，还用到了二叉树，看了半天，感觉比较费力。（以前没有写过astar算法），于是翻看网上的AStar的其他算法，不知道是不是自己太笨还是别的什么原因，我不明白为什么很多网上的例子，要不不能用，要不就是代码异常复杂，给读者造成了很大的困难。
于是自己尝试写了一个，当然还只是框架，半天功夫倒腾出来一个，貌似架构比网上的好读一些，而且可以支持测试，实现考虑了未来跨平台的可能，于是尽量使用通用化的C++去实现。同时，根据AStar的算法，尽量做了一些优化。
贴在这里，如果大家有兴趣可以玩玩。
AStar的原理，其实很简单，其核心算法就是权值的问题。具体的算法请参考
http://www.acejoy.com/bbs/viewthread.php?tid=3041&extra=page%3D1
其实，根据如上的描述，AStar是很简单的。
先定义一些自己需要的中间结构体
//地图节点
struct _World
{
BYTE m_bState; //节点状态，1是可以通过，0是不能通过
BYTE m_bRoute; //节点范围
intm_nRow; //行标记
intm_nCol; //列标记
intm_nIndex; //当前区块ID
_World():m_bState(0), m_bRoute(4), m_nRow(0), m_nCol(0), m_nIndex(0)
{
}
};
//坐标信息
struct _WorldPos
{
intm_nRow;
intm_nCol;
_WorldPos():m_nRow(0), m_nCol(0)
{
}
};
//位置字典信息
struct _DX
{
short m_nCost; //权值
short m_nIndex; //对应的位置ID
int m_nInterval;//和*点的节点差距
};
//计算中的权值和节点位置对应关系结构
struct _WorldCostInfo
{
int m_nWorldIndex;
int m_nWorldCost;
};
typedef vector<_World*> vecPath;
//路线节点信息
struct _NodePath
{
vecPath m_vecPath; //路线节点信息
};
_World：是地图中的一个点的信息，包括横纵坐标，是否可以走，当前的Index(相对起始点的偏移)
_WorldPos：我们姑且认为，用户传入的是两个坐标点，里面包含X和Y，其实AStar可以扩展到三个轴向的计算，不过这会引起计算量的成倍增长。目前先讨论二维地图的情况。
_DX：这个结构体，是一个格子，周围给定的8个格子的信息，为了方便未来的计算，这里先算好，以后计算中直接从中去取比较方便。
_WorldCostInfo：这个结构体其实完全可以封在CPathFinder的Private里面。这是在计算权值中间状态时的一个结构体，外围程序完全不用知道它的存在。
_NodePath：这个结构体会存放找到的路线节点信息。穿成一个串，用于路线的返回。
建立一个类，姑且叫做CPathFinder
class CPathFinder
{
public:
CPathFinder(void);
~CPathFinder(void);
void Init();
void Close();
bool AStarFind(const _WorldPos PosStart, const _WorldPos PosEnd, _NodePath*& pNodePath);
private:
_World* CalculateEightQueen(const _World* pTarget, const _World* pEnd);
inline void CalculateCost(const int nTarget, const int nEnd, const int nIndex, _WorldCostInfo& nMinIndex);
inline int CalculateDirect(const _World* pTarget, const _World* pEnd);
private:
_World* m_pWorld;
int m_nMapWidth;
int m_nMapHeight;
int m_nMaxGridCount;
_DX* m_pDX;
};
这里的Init是架在地图，这里完全可以做成读取文件，fopen等等，这里为了简化，先用一个循环替代。
Close方法顾名思义，就是用完了这个类完成的清空动作。
对外只提供一个方法，AStarFind()
//PosStart是起始点，PosEnd是终点，pResult是路线中经过所需要的节点位置链表
函数返回一个bool，会告诉使用者astar是否寻路成功。
私有函数只有三个
CalculateEightQueen()负责计算给定格子周围的8个格子的权值。
CalculateCost()计算给定格子到目标格子之间的估算权值，这里使用了曼哈顿方法进行估算。
CalculateDirect()计算指定格子到目标个字的角度，目前角度一共有8个，对应周围的8个格子。
具体实现代码不在这里贴了，有兴趣的可以读读我的附件。
写了一个测试
int main(int argc, char* argv[])
{
printf("Begin.\n");
_ENTER_FUNCTION
CPathFinder PathFinder;
PathFinder.Init();
_WorldPos PosBegin;
_WorldPos PosEnd;
_NodePath* pNodePath = new _NodePath();
PosBegin.m_nRow = 1;
PosBegin.m_nCol = 0;
PosEnd.m_nRow = 3;
PosEnd.m_nCol = 0;
_ENTRYTIME
PathFinder.AStarFind(PosBegin, PosEnd, pNodePath);
_LEAVETIME
if(pNodePath->m_vecPath.size() > 0)
{
for(int i = 0; i < (int)pNodePath->m_vecPath.size(); i++)
{
printf("Find Path(%d, %d)\n", pNodePath->m_vecPath->m_nRow, pNodePath->m_vecPath->m_nCol);
}
}
else
{
printf("AStar fail,sorry.\n");
}
_LEAVE_FUNCTION
getchar();
return 0;
}
这里我创建了一个100*100的地图世界，故意造成了一个阻挡，0,2格子的组个，我从0,1到0，3，看看它是否会给我绕道。
返回结果是
Begin.
Cost = 0.
Find Path(1, 2)
Find Path(0, 3)
这里为了计算我的AStar的时间成本，我写了两个宏。
_ENTRYTIME和_ENTRYTIME
这两个宏会显示被包含的代码执行时间。
因为aStar的算法比较消耗循环，所以，我按照常理，给AStar增加了一个最大计算步数的限制，防止搜索过大的地图造成的时间消耗过长，从而影响用户的体验，这里你可以通过修改MAX_ASTAR_COUNT这个参数达到，由于系统硬件不同，你可以测试这段代码在你的本机上多少半径作为合理数值。
呵呵，有兴趣的可以跑一下，遇到问题，可以在这里留言。
本代码在winXP+VS2005下测试用过。
页:
[1]