[原创][求助]聊聊游戏辅助那些事上部第四篇——优化到极致的 A星路径搜索 算法。
聊聊游戏辅助那些事上部第四篇——优化 A*路径搜索 算法。先上一段路径搜索的伪代码CAltList&Node&list.AddTail(起点);while(!list.IsEmpty()){&/*取出队列中第一点*/&POINT now = list.RemoveH&if(now == 终点)&{&&/*结束，取路径*/&&return TRUE;&}&&/*尝试走到下一步，一般是四连通是上下左右四个点，八连通则是周围八个点，如果可能走通且没有处理过则加入到结点中;*/&if(MoveAble(now.x - 1, now.y))&{&&list.AddTail(now.x - 1, now.y);&}&.....&if(MoveAble(now.x - 1, now.y - 1))&{&&list.AddTail(now.x - 1, now.y - 1);&}}上面是路径搜索并非 A*路径搜索，A*搜索要比上面算法多一个与终点的估价排序。AddTail(x, y) 要换成插入算法。说完伪代码，进入真正算法：先用一个结构来描述结点：class TAstarNode{public:&int ActualC&&&// 保存从起点到该节点的实际开销&int EstimateC&&// 保存此点的估价开销&int SumC&&&// 上面两者之和&int M &&&// 该节点是否被修改过，记录而备清除 1空, 2 Open, 4 Close, 16 最终路径节点, 256 丢弃节点&TAstarNode&*F&// 此点的父节点&TAstarNode&*P&&// 在Open或者Next中的上一个节点&TAstarNode&*N&&// 在Open或者Next链表中的下一个节点private:&TAstarNode()&{&&Modified = NM_INIT;&&ActualCost = COST_MAX;&&Father = Prev = Next = NULL;&}&friend CAtlMap&TPOINT, TAstarNode&;};用一个哈希表保存使用过的结点class CNodeMap : public CAtlMap&TPOINT, TAstarNode&{public:};用一个二叉树来加快插入算法，这个二叉树是 VS20XX alt模板库可以直接使用。这里的 key 是估价值，是个 int 值class COpenedTree : public CRBTree&int, TAstarNode*&{public:&POSITION Insert(/* _In_ */ KINARGTYPE key,&/* _In_ */ VINARGTYPE value) throw(...)&{&&return (POSITION)RBInsert(key, value);&}};定义A*路径搜索算法结构，先摘一些主要的代码，主要是帮助算法的理解，完全的源码贴在最后。class AstarPathFind{public:&TAstarNode* m_pC&&&&&&//&获取坐标时使用的当前坐标值&TAstarNode* m_pT&&&&&&//&指向链表最后一个结构public:&int JudgeCost(int x, int y, int endx, int endy)&{&&int dx = x -&&int dy = y -&&return ABS(dx) + ABS(dy);&}&//&//&尝试下一步移动到 x,y 可行否&//&template &const ULONG t_ucost&&int TryTile(LPCBYTE pln, int x, int y, TAstarNode *Father)&{&&register TAstarNode *&&int ActualC&&if(!MoveAble(pln, x))&&{&&&return -1;&&}&&POINT pt = {x, y};&&int mosaic = cost - 255 + MOSAIC;&&TAstarNode& node = &m_mapAstarNode[pt];&&//&&//&需要判断一下结点是否已经使用过&&//&&if (node-&Modified == NM_INIT)&&{&&&node-&Father = F&&&node-&ActualCost = ActualC&&&node-&EstimateCost = JudgeCost(pt.x, pt.y, pt.z, TargetX, TargetY);&&&node-&SumCost = ActualCost + node-&EstimateC&&&node-&Modified = NM_EMPTY;&&&AddToOpenQueue(node);&&}&&return 0;&}&//&//&将离目的地估计最近的方案出队列&//&TAstarNode* GetFromOpenQueue()&{&&POSITION pos = m_treeOpened.GetHeadPosition();&&if (pos)&&{&&&TAstarNode* r = m_treeOpened.GetAt(pos)-&m_&&&m_treeOpened.RemoveAt(pos);&&&&&}&&return NULL;&}&//&//&待处理节点入队列, 依靠对目的地估价距离插入排序&//&int AstarPathFind::AddToOpenQueue(TAstarNode *node)&{&&m_treeOpened.Insert(node-&SumCost, node);&&return 0;&}&//&//&有目的地址的路径搜索&//&BOOL FindPath(int startx, int starty, int startz, int endx, int endy, int endz, int cost_max/* = INT_MAX*/)&{&&m_mapAstarNode.RemoveAll();&&m_treeOpened.RemoveAll();&&m_pCurrent = m_pTail = NULL;&&//&&//&将坐标更改为地图地址&&//&&TPOINT startpt = { startx, starty, startz };&&TPOINT endpt = { endx, endy, endz };&&//&&//&需要保存起点和终点都有可移动结点上&&//&&if (!ValidPoint&CMoveFromAble&(&startpt, endpt))&&{&&&return FALSE;&&}&&if (!ValidPoint&CMoveToAble&(&endpt, startpt))&&{&&&return FALSE;&&}&&TAstarNode *root = &m_mapAstarNode[startpt];&&root-&ActualCost = 0;&&root-&EstimateCost = JudgeCost(startpt.x, startpt.y, startpt.z, endpt.x, endpt.y);&&root-&SumCost = root-&EstimateC&&root-&Father = NULL;&&root-&Modified = NM_EMPTY;&&AddToOpenQueue(root);&&int&MinJudge = root-&EstimateC&&while (root = GetFromOpenQueue())&&&//&取出Open队列估价值最小的节点&&{&&&TPOINT now = GetPosition(root);&&&if (now.x == endpt.x && now.y == endpt.y && now.z == endpt.z)&&&{&&&&//&&&&//&走到终点了, 整理链表, 使链表是由Father构造的单向链表, 转换为由Next,Pre构造的双向链表, 并优化路径的通过性&&&&//&&&&return ImprovePath(root);&&&}&&&if ((cost_max != INT_MAX) && (root-&ActualCost &= cost_max))&&&{&&&&//&&&&//&走得足够远了, 整理链表, 使链表是由Father构造的单向链表, 转换为由Next,Pre构造的双向链表, 并优化路径的通过性&&&&//&&&&return ImprovePath(root);&&&}&&&LPCBYTE&&&if (now.y & 0)&&&{&&&&pln = m_pWalkedHdr + m_pLineHdr[now.y - 1];&&&&TryTile&1&(pln, now.x - 1, now.y - 1,&now.z, root);&&&&TryTile&1&(pln, now.x, now.y - 1,&&now.z, root);&&&&TryTile&1&(pln, now.x + 1, now.y - 1,&now.z, root);&&&}&&&pln = m_pWalkedHdr + m_pLineHdr[now.y];&&&TryTile&1&(pln, now.x - 1, now.y, now.z, root);&&&TryTile&1&(pln, now.x + 1, now.y, now.z, root);&&&if (now.y & m_nHeight - 1)&&&{&&&&pln = m_pWalkedHdr + m_pLineHdr[now.y + 1];&&&&TryTile&1&(pln, now.x - 1, now.y + 1,&now.z, root);&&&&TryTile&1&(pln, now.x, now.y + 1,&&now.z, root);&&&&TryTile&1&(pln, now.x + 1, now.y + 1,&now.z, root);&&&}&&}&&return FALSE;&}};绝大多数的A*大概不过如此，而且出来的路径有个大问题，总是沿着边缘走，而且速度慢。为解决这两个问题，进行算法上四个优化。1、直线叠代。&for(;;)&{&&if(直线通过(检测起点,检测终点))&&{&&&直线路径(检测起点,检测终点);&&&检测起点 = 检测终点;&&&检测终点 = 路径终点;&&}&&else&&{&&&检测终点 = 检测起点与检测终点的中点;&&}&}&通过性明显改善。2、灰级地图。还是为了解决沿着边缘走的问题，引入灰级地图，可通过性分 0 不通过，1 - 64 分为 64 级可通过性。&int JudgeCost(int x, int y, int z, int endx, int endy)&{&&int dx = x -&&int dy = y -&&int cost = ABS( dx ) + ABS( dy );&&if( x & 0 || x &= m_nWidth || y & 0 || y &= m_nHeight || z & 0 || z &= m_nFloor )&&{&&&return cost + 255;&&}&&else&&{&&&ULONG smooth = m_pWalkedHdr[m_pFloorHdr[z] + m_pLineHdr[y] + x];&&&return (smooth &= RESERVED + SMOOTH) ? cost : (cost + (RESERVED + SMOOTH - smooth) * (256 / SMOOTH));&&}&}3、马赛克地图。前面两个优化都是针对通过性的优化，第三个优化是针对速度的优化。当地图大于 5000 * 5000 时，寻径需要的时间已经在秒级，显然不够用了。但如果愿意牺牲地图的精度的缩小到 ，甚至是时，速度就可以大大提高，那么有没有什么办法让地图缩小后不丢失精度呢。答案是有的，引入马赛克地图，保留地图的边缘精度，中心的在大块则进行马赛克处理，在算法中对2*2,4*4,8*8,16*16,32*32,64*64的区块当作一个点来处理，从而大大加块寻径的速度。4、主干线与支线优化。这种优化对地图有特别要求，所有主干线是相连的。先从起点寻径到最近的主干线，再从终点寻径到最近的主干线，然后再在两人主干线这间寻径。源码中的 BOOL AstarPathFind::FastFindPath(int startx, int starty, int startz, int endx, int endy, int endz); 不过未经测试，因为绝大多数情况，试用马赛克地图已经足够了。最后就是代码了，头文件 AStar.h，源文件 AStar.cpp，总共两个文件。请自行下载附件，并附带一个大地图。典型的使用文法：AstarPathFind findPfindPath.Create(biMap, biDirect);&&//第一个参数是地图，必须的，第二个参数是方向图，与一图大小一致，8位位图，表示当前坐标点是否可以住8个方向走动，可设为NULL,默认每一个点都可以住8个方向走动。findPath.FindPath(x0,y0,z0,x1,y1,z1);&&//有参数 z ，支持3D寻径，z 是楼层号，如果地图有两层，z 取值就是0和1遍历路径：for (POSITION pos = findpath.GetStartPosition(); ){&D3DPOINT&findpath.GetNextPos(pos, &pt);};或者在寻路时使用，返回当前点的直线路径：int AstarPathFind::GetNextPath(LPD3DPOINT ppt, int distance);&// distance为取最短的距离。最后预告一下，本系列的第五篇，聊聊游戏辅助那些事上部第五篇——做一个奇葩的DLL，看你怎么找到我？如何隐藏DLL，用的还是老方法，下一章见分晓。
上传的附件：
（2.59MB，93次下载）
支付方式：
最新回复 (6)
不贴边的办法简单暴力,设置一个FPathSpace,表示与边缘的距离.& & & & If& (& X& && FMapWidth& -& FPathSpace& )& And& (& X& && FPathSpace& )& And& (& Y& && FMapHeight& -& FPathSpace& )& And& (& Y& && FPathSpace& )& Then& & & & Begin& & & & & & Cost& :=& TerrainParams[& FMapData[& X& -& FPathSpace& ,& Y& ].TerrainType& ].MoveCost& +& TerrainParams[& FMapData[& X& +& FPathSpace& ,& Y& ].TerrainType& ].MoveCost& +& TerrainParams[& FMapData[& X& ,& Y& -& FPathSpace& ].TerrainType& ].MoveCost& +& TerrainParams[& FMapData[& X& ,& Y& +& FPathSpace& ].TerrainType& ].MoveC& & & & & & If& Cost& && 4& *& TerrainParams[& TtPath& ].MoveCost& Then& & & & & & Begin& & & & & & & & Result& :=& -1;& & & & & & E& & & & E
& & & & 期待第五篇& & &
看你怎么隐藏过腾讯的三方
请问楼主，如果只传入二值地图怎么改造Create，能力有限改了后报错···BOOL& AstarPathFind::Create(BYTE& *& _Map,& DWORD& Width,& DWORD& Height){ & & & &m_nFloor& =& 1; & & & &m_nHeight& =& H & & & &m_nWidth& =& W & & & &// & & & & & & & &// & & & &计算保存地图数据需要的缓冲 & & & &// & & & &size_t& nLnbytes& =& W//& (((m_nWidth& *& 8)& +& 31)& && (~31))& /& 8; & & & &wxxk::goutf(L&我:%d\n&,& nLnbytes); & & & &size_t& nFrbytes& =& nLnbytes& *& m_nH & & & &// & & & &// & & & &分配内存时同时分配每行行首的坐标 & & & &// & & & &m_pLineHdr& =& new& size_t[m_nHeight]; & & & &m_pFloorHdr& =& new& size_t[m_nFloor]; & & & &// & & & &// & & & &移动控制 & & & &// & & & &RGBQUAD& bmiColors[256]; & & & &m_pWalkedHdr& =& (LPCBYTE)&& bmiC & & & &wxxk::goutf(L&我1:%d;%d\n&,& m_pWalkedHdr,& m_pWalkedHdr[627]); & & & &// & & & &// & & & &初始化每行 & & & &// & & & &BYTE& *m_pd& =& new& BYTE[m_nWidth& *& m_nHeight]; & & & &memcpy_s(m_pd,& m_nWidth& *& m_nHeight,& _Map,& m_nWidth& *& m_nHeight); & & & &m_pLineHdr[0]& =& 0; & & & &for& (int& y& =& 1;& y& && m_nHeight& +& 1;& y++) & & & &{ & & & & & & & &BYTE& *pd& =& new& BYTE[m_nWidth]; & & & & & & & &for& (int& x& =& 0;& x& && m_nW& x++) & & & & & & & & & & & &pd[x]& =& _Map[(y& -& 1)& *& m_nWidth& +& x]; & & & & & & & &m_pLineHdr[y]& =& (size_t) & & & &} & & & &// & & & &// & & & &初始化每个地板 & & & &// & & & &m_pFloorHdr[0]& =& 0; & & & &for& (int& i& =& 1;& i& && m_nF& i++) & & & &{ & & & & & & & &m_pFloorHdr[i]& =& m_pFloorHdr[i& -& 1]& +& nF & & & &} & & & &m_nFloorBytes& =& nF & & & &MaxSize& =& m_nHeight& *& m_nW & & & &SetDirMask(0xFF); & & & &m_mapAstarNode.InitHashTable(m_nHeight); & & & &m_pDirectedHdr& =& NULL; & & & &return& TRUE;}
1.请先关注公众号。
2.点击菜单"更多"。
3.选择获取下载码。