聊聊游戏辅助那些事上部第四篇——优化 A*路径搜索 算法。

先上一段路径搜索的伪代码

CAltList<Node> list;
list.AddTail(起点);

while(!list.IsEmpty())
{
 /*取出队列中第一点*/
 POINT now = list.RemoveHead;
 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 ActualCost;   // 保存从起点到该节点的实际开销
 int EstimateCost;  // 保存此点的估价开销
 int SumCost;   // 上面两者之和
 int Modified;    // 该节点是否被修改过，记录而备清除 1空, 2 Open, 4 Close, 16 最终路径节点, 256 丢弃节点
 TAstarNode *Father; // 此点的父节点
 TAstarNode *Prev;  // 在Open或者Next中的上一个节点
 TAstarNode *Next;  // 在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_pCurrent;      // 获取坐标时使用的当前坐标值
 TAstarNode* m_pTail;      // 指向链表最后一个结构

public:
 int JudgeCost(int x, int y, int endx, int endy)
 {
  int dx = x - endx;
  int dy = y - endy;
  return ABS(dx) + ABS(dy);
 }

 //
 // 尝试下一步移动到 x,y 可行否
 //
 template <const ULONG t_ucost>
 int TryTile(LPCBYTE pln, int x, int y, TAstarNode *Father)
 {
  register TAstarNode *node;
  int ActualCost;

  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 = Father;
   node->ActualCost = ActualCost;
   node->EstimateCost = JudgeCost(pt.x, pt.y, pt.z, TargetX, TargetY);
   node->SumCost = ActualCost + node->EstimateCost;
   node->Modified = NM_EMPTY;
   AddToOpenQueue(node);
  }
  return 0;
 }

 //
 // 将离目的地估计最近的方案出队列
 //
 TAstarNode* GetFromOpenQueue()
 {
  POSITION pos = m_treeOpened.GetHeadPosition();
  if (pos)
  {
   TAstarNode* r = m_treeOpened.GetAt(pos)->m_value;
   m_treeOpened.RemoveAt(pos);

   return r;
  }

  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->EstimateCost;
  root->Father = NULL;
  root->Modified = NM_EMPTY;

  AddToOpenQueue(root);

  int MinJudge = root->EstimateCost;

  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 pln;
   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 - endx;
  int dy = y - endy;
  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 时，寻径需要的时间已经在秒级，显然不够用了。但如果愿意牺牲地图的精度的缩小到 2500*2500，甚至是1250*1250时，速度就可以大大提高，那么有没有什么办法让地图缩小后不丢失精度呢。答案是有的，引入马赛克地图，保留地图的边缘精度，中心的在大块则进行马赛克处理，在算法中对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 findPath;
findPath.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(); pos; )
{
 D3DPOINT pt;
 findpath.GetNextPos(pos, &pt);
};

或者在寻路时使用，返回当前点的直线路径：
int AstarPathFind::GetNextPath(LPD3DPOINT ppt, int distance); // distance为取最短的距离。

最后预告一下，本系列的第五篇，聊聊游戏辅助那些事上部第五篇——做一个奇葩的DLL，看你怎么找到我？如何隐藏DLL，用的还是老方法，下一章见分晓。

[招生]科锐逆向工程师培训(2024年11月15日实地，远程教学同时开班, 第51期)