A* 算法原理

1. Dim开放列表
   • 在当前位置找路和以及对于代价，写入
   • 找最小的代价的路并走，走了路后，删除那个路，若不删除，可能不走了
   • 同样代价，优先走晚加入的
2. Dim闭合列表
   • 加入走过的路
   • 防止反复横跳，因为不可能走同样的路
3. 找最短路径
   • 从终点找父节点，找到起始点
4. 观看链接
   • https://www.youtube.com/watch?v=06IEe3DS_aE

A*算法代码

1. 代码流程

   •   display->parseMapFile();display->printInitMap();gridmap->createGridMap(*display);Point *point = star->findWay(gridmap->get_start_point(0, 0),gridmap->get_end_point(3, 7),gridmap->get_map_(), *display);gridmap->printResultMap(point, *display);
     

2. display->parseMapFile()

   • 打开map文件，map文件是几行的0或1
   • _mapdata存入 该map转化的数组，char‘1‘和char‘0‘’’

3. display->printInitMap()

   • 打印出来地图信息

4. point信息

   • x是第几行，y是第几列
   • 类型有：位置，闭合，开放，障碍，路径，默认是未知，map图中0表示障碍
   • 父节点和8个方向
   • f g h

5. *gridmap->createGridMap(display)

   • 创建map数组，这个数组包含4*8，存着point

6. star->findWay

   • findWayPreprocess
     • openlist添加beginpoint
     • 并且更改beginpoint的类型为open以及计算代价f
     • computeFCost
       • point->_g + computeHCost(point, Direction::OCTAGONAL)
       • octagonal算的是斜着加横的距离
     • 由于枚举类direction默认为第一个，所以point的direction初始化为MANHATTAN,由于后序这个起始点的direction没意义，所以无所谓
     • 总结1：openlist加入起始点beginpoint这个指针，并且修改指针指向的type和代价
     • 总结2：改变openlist，beginpoint
   • other
     • 当前在openlist第一个，步数加一
     • openlist擦除第一个
     • 改变当前的点的type为close
     • closelist加入当前的点
     • 判断当前点是否到达终点，若是，则find_way标志位设置为true并且返回当前点
     • findNeighboringPoint
       • 对当前地点找8和邻居，先判断该点是否在边界，有无那种邻居，再判断该邻居是否是障碍物，设置该邻居的方向为正的设置为曼哈顿，斜的设置为incline，并把该点放到neighbourlist里面
       • tip:当斜着走时，如斜着右上走，如果右边和上边都堵住了，就不能这样走
     • computeNeighboringValue
       • computeValueNotInOpenList
         • 设置父节点，tmpoint->_g = _curpoint->_g + kManhattanMoveCost;
         • 设置g，h，f
         • g为父节点的g加100或140
         • h离终点距离，f为h+g
         • 加入openlist
         • 设置该点的type为open
       • computeValueInOpenList
         • 临时点的h比当前点的h小，则：
           • 设置临时点的父节点为当前节点
           • 改变临时的的g，f，由于h之前算过了，就不改了
           • g设置为当前点的g+100或140
           • 无需加入openlist，因为以及加入了
     • sort根据f代价，由小到大，对openlist里的point排序
     • 不断循环，知道openlist为空，若空后，还是cur没有到终点，则找不到路，返回nullptr
     • 总结1：计算步数，改变当前点以及当前点的类型，改变openlist和closelist，判断结束总结2：改变step_count，curpoint，openlist，closelist，
   • GridMap::createGridMap
     • 根据返回的终点，不断修改type为路径，然后再对父节点这样操作

• 大总结

  • openlist，closelist，neighbourlist，allpoints，endpoint，curpoint，findway

  • 把beginpoint设置为open，算出该点的f，并把beginpoint加入openlist

  • 循环内：

    • ++step_count

    • 讲curpoint从openlist拿出来，改为close，放入closelist

      • curpoint=openlist[0]
      • openlist擦除第一个
      • curpoint类型改为close
      • closelist加入curpoint

    • 通过curpoint找邻居，并且改变邻居点的direction为MANHATTAN或者INCLINE

    • 邻居大部分是unknown，小部分是open和close

      • 对unknown的，改变g，h，f，g为curpoint的g+100或140，并改为open,设置tmpoint的父节点为curpoint
      • 对open的，判断tmpoint的h和curpoint的h，如果tmpoint的小，则设置父节点为curpoint，改变g，f，不改变h，或者说不需要改变
        • 首先，判断h哪个小，如果距离反而更远，则保持tmpoint的g，f，h
        • 接着，如果距离不变或者更近，则加上curpoint的
      • 对close的，不操作，也不出打印g,h,f信息

    • 对openlist通过代价排序,而不是对neighbourlist排序

    • map如下，0是障碍

      1 1 1 1 0 0 0 0
      1 1 1 1 1 0 0 0
      0 0 1 0 0 1 1 1
      0 1 1 1 1 1 1 1

    • (1,2)和(0,2)的父节点重新设置为了(0,1)，之前是(1,1)

    • 这样，每一个点的父节点路线都会刷新为已知最短