astar基本算法.cpp

一个Astar算法的基本算法结构

#pragma once

#include <map>
using namespace std;

char op_y[8] = {-1,-1, -1, 0, 1, 1, 1, 0};
char op_x[8] = {-1, 0,   1, 1, 1, 0,-1,-1};

//char op_round[8] = {14,10,14,10,14,10,14,10};

//这是输入结构
struct InputAstarMap
{
  int width;    //地图的宽
  int height;    //地图的高
  char * map;    //以byte为单位的地图数据,大小应该是宽*高
  int start_x;  //开始点x地址(x是横方向,也就是宽)
  int start_y;  //开始点y地址(y是竖方向,也就是高)
  int end_x;    //结束点x地址
  int end_y;    //结束点y地址
  int wall_code;  //代表墙壁,障碍的数据(byte为单位的地图,一共有255个可代表的值)
  int end_code;  //结束点代表的值
  int way_code;  //这个值意思是,如果找到了路径,那么在地图上标识出来将用这个值
};

struct AStar_FGH
{
  int vF;
  int vG;
  int vH;
  int x;
  int y;
  int Father;
  int close;
  int my_n;
};

class AStar_Find
{
public:
   AStar_Find(void);
   ~AStar_Find(void);
  int Find_Way(InputAstarMap & IAM);

private:
  //int Push_Close(int pn);
   inline int Push_Open(int pn);
   inline int Pop_Open();
   inline int Pop_Open(int findn);
   inline int Find_Item(int findn);

   inline int GetFGH();

   multimap<int, int> OpenList;
   multimap<int, int> UseList;
  
   InputAstarMap * iam;
   AStar_FGH * AStar_FGH_Pool;
  int AStar_Pool_All;
  int AStar_Pool_n;
};

AStar_Find::AStar_Find(void)
{
   OpenList.clear();
   UseList.clear();
   AStar_FGH_Pool = (AStar_FGH * )malloc(sizeof(AStar_FGH) * 0x10);
   AStar_Pool_All = 0x10;
}

AStar_Find::~AStar_Find(void)
{
   OpenList.clear();
   UseList.clear();
  if(AStar_FGH_Pool) 
   {
     free(AStar_FGH_Pool);
   }
}

int AStar_Find::Find_Way(InputAstarMap & IAM)
{
   OpenList.clear();
   UseList.clear();
   AStar_Pool_n = 0;
   iam = &IAM;

  //将起始地址压入open列表
  int getn = GetFGH(), openn, roundn;
  //father为父路径的结构点编号,这里是起始点,所以没有父路径
  //因为这里采用的是编号而不是指针
   AStar_FGH_Pool[getn].Father = 0;
  //x,y是当前位置的坐标
   AStar_FGH_Pool[getn].x = IAM.start_x;
   AStar_FGH_Pool[getn].y = IAM.start_y;
  //vF是全局值,是vG和vH的和
  //vH是当前位置到目的地中间经过的步数(只算横竖,不算斜向),并将这个步数乘以10
   AStar_FGH_Pool[getn].vF = AStar_FGH_Pool[getn].vH = abs(AStar_FGH_Pool[getn].x - IAM.end_x) * 10 + abs(AStar_FGH_Pool[getn].y - IAM.end_y) * 10;
  //vG是移动到当前位置的代价,这里是起始点,所以代价是0
   AStar_FGH_Pool[getn].vG = 0;
   Push_Open(getn);

  do
   {
    //从open列表中取出一个vF值最小的,因为OpenList会自动按照vF的值从小到大排列
    //所以取出第一个就是最小的vF了
     openn = Pop_Open();

    //如果已经没有open列表,说明找不到一条活通向结束点,失败退出
    if(openn == -1) 
      return false;

    //将取出的open列表结构放入close列表
    //Push_Close(openn);
     AStar_FGH_Pool[openn].close = 1;

    //查找open列表取出的这个值的周围8个点位
    for(int roundi = 0; roundi < 8; roundi ++)
     {
      //计算这个周围点的权值
      //权值的算法就是这个位置在地图中是第几个方块(从0,0开始算)
      //权值 = y(纵轴长度) * 地图宽度 + x(横向长度)
      int get_roundn = (AStar_FGH_Pool[openn].y + op_y[roundi]) * IAM.width + 
         AStar_FGH_Pool[openn].x + op_x[roundi];

      //用这个周围点的权值查找地图文件
      //如果这个点存在墙壁,略过不分析
      if(IAM.map[get_roundn] == IAM.wall_code)
        continue;

      //这些是斜角算法,如果没有这一步,斜角可以通过,举例:
      //10
      //01
      //在1是wall(无法通过的障碍物)的情况下,两个0是可以通过的.就属于斜角可以通过
      if(roundi % 2 == 0)
       {
        int get_bef_roundn = (AStar_FGH_Pool[openn].y + op_y[(roundi - 1) % 8]) * IAM.width + 
           AStar_FGH_Pool[openn].x + op_x[(roundi - 1) % 8];

        int get_aft_roundn = (AStar_FGH_Pool[openn].y + op_y[(roundi + 1) % 8]) * IAM.width + 
           AStar_FGH_Pool[openn].x + op_x[(roundi + 1) % 8];

        if(IAM.map[get_bef_roundn] == IAM.wall_code || IAM.map[get_aft_roundn] == IAM.wall_code)
          continue;
       }

      //如果这个周围点是目的地
      if(IAM.map[get_roundn] == IAM.end_code)
       {
        //退栈并将路径逐步赋值给map文件
        //即设置沿路的的地图值为way_code
         AStar_FGH * fd_way = &AStar_FGH_Pool[openn];
        while(fd_way->Father)
         {
           IAM.map[fd_way->y * IAM.width + fd_way->x] = IAM.way_code;
           fd_way = &AStar_FGH_Pool[fd_way->Father];
         }
        return true;
       }

      //查找这个周围点的是否存在于Use列表内
      //Use列表存放的是所有进过列表(包括Open列表和Close列表)的点
       roundn = Find_Item(get_roundn);

      if(roundn == -1)
       {
         roundn = GetFGH();
        //如果这个周围点不在于Use列表中
        //开始建立这个周围点的fgh结构,并存放入open列表
         AStar_FGH_Pool[roundn].Father = openn;
         AStar_FGH_Pool[roundn].x = AStar_FGH_Pool[openn].x + op_x[roundi];
         AStar_FGH_Pool[roundn].y = AStar_FGH_Pool[openn].y + op_y[roundi];
         AStar_FGH_Pool[roundn].vH = abs(AStar_FGH_Pool[roundn].x - IAM.end_x) * 10 + abs(AStar_FGH_Pool[roundn].y - IAM.end_y) * 10;
         AStar_FGH_Pool[roundn].vG = AStar_FGH_Pool[openn].vG + (roundi % 2 == 0 ? 14 : 10);
         AStar_FGH_Pool[roundn].vF = AStar_FGH_Pool[roundn].vG + AStar_FGH_Pool[roundn].vH;
         Push_Open(roundn);
        //这里表示的是,如果经过查找的点,可以设置成某个值.用于在地图上表示出来
        //IAM.map[get_roundn] = 0x09;
       }  
      else
       {
        //如果这个周围点已经在Use列表中
        //再判断,是否在Close列表中
        //注意,这里并没有真正的Close列表,所谓Close列表只是点进过Open列表后,点的close值被设置成0
        //点要是出了Open列表,进入Push_Close函数处理,就将点的close值设置为1了
        if(AStar_FGH_Pool[roundn].close == 0)
         {
          //不在Close列表中(就是说这个周围点在Open列表中了)
          //计算从当前点位(中间点)到达这个周围点的路径是否更优
          if(AStar_FGH_Pool[openn].vG + (roundi % 2 == 0 ? 14 : 10) < AStar_FGH_Pool[roundn].vG)
           {
            //如果更优,将这个周围点的farther设置为当前点位(中间点),并重新设置fgh的值
            //更改了F值,需要重新弹出后重新进入列表,以重新排序
            if(Pop_Open(roundn))
             {
               AStar_FGH_Pool[roundn].vG = AStar_FGH_Pool[openn].vG + (roundi % 2 == 0 ? 14 : 10);
               AStar_FGH_Pool[roundn].vF = AStar_FGH_Pool[roundn].vG + AStar_FGH_Pool[roundn].vH;
               AStar_FGH_Pool[roundn].Father = openn;
               Push_Open(roundn);
              //这里表示的是,如果发现了新路径,改变了原来路径的,设置为一个改变值,在地图上表示出来
              //IAM.map[get_roundn] = 0x08;
             }
           }
         }
       }
     }
   }while(true);
    
  return true;
}
inline int AStar_Find::Find_Item(int findn)
{
   multimap<int, int>::iterator iter;
   iter = UseList.find(findn);
  if(iter != UseList.end())
   {
    return AStar_FGH_Pool[iter->second].my_n;
   }
  return -1;
}

//int AStar_Find::Push_Close(int pn)
//{
//   AStar_FGH_Pool[pn].close = 1;
//   return true;
//}

inline int AStar_Find::Push_Open(int pn)
{
   AStar_FGH_Pool[pn].close = 0;
   AStar_FGH_Pool[pn].my_n = pn;
   OpenList.insert(pair<int, int>(AStar_FGH_Pool[pn].vF, pn));
   UseList.insert(pair<int, int>(AStar_FGH_Pool[pn].y * iam-> width + AStar_FGH_Pool[pn].x, pn));
  return true;
}

inline int AStar_Find::Pop_Open()
{
   multimap<int, int>::iterator iter;
   iter = OpenList.begin();
  if(iter != OpenList.end())
   {
    int rtn = AStar_FGH_Pool[iter->second].my_n;
     OpenList.erase(iter);
    return rtn;
   }
  return -1;
}

inline int AStar_Find::Pop_Open(int findn)
{
  int rtn = false;
   multimap<int, int>::iterator iter, iterdel;
  for(iter = OpenList.begin(); iter != OpenList.end();)
   {
    if(AStar_FGH_Pool[iter->second].my_n == findn)
     {
       iterdel = iter;
       rtn = true;
       iter++;
       OpenList.erase(iterdel);
     }
    else
     {
       iter++;  
     }
   }
  return rtn;
}

inline int AStar_Find::GetFGH()
{
  if(AStar_Pool_n + 1 == AStar_Pool_All)
   {
     AStar_Pool_All *= 2;
     AStar_FGH_Pool = (AStar_FGH * )realloc(AStar_FGH_Pool, sizeof(AStar_FGH) * AStar_Pool_All);
   }
   AStar_Pool_n += 1;
  return AStar_Pool_n;
}