流场寻路算法简单实现

Flow field pathfinding algorithm implementation

• key words: OpenGl Dijkstra Flow Field Path Finding
  Flow field pathfinding algorithm implementation

• 当前实现的主要效果：
  1.地图上随机分布200个移动目标；
  2.移动目标可绕过障碍物，沿着地图的流场找到最短路径（最小代价的路径）到达目标点；
  3.可通过点击地图上的非障碍物区域，实时的更改目标地点，并更新流场；
  4.可通过按着鼠标左键在地图上拖拽，实时绘制障碍物，并动态更新流场；
  

• 效果图：
  蓝色点为终点，红色块为障碍物，蔚蓝色小点为移动目标，小点加线为流场方向指示箭头。这里的地图为均匀地图（即移动目标经过地图中每个网格的代价相同）
  

  1.初始地图效果：
  

  2.动态设置障碍物效果：
  

  3.重置终点效果：
  

• Bug：
  由于初次使用OpenGl，还有很多细节做得不到位
  1.窗口大小变换后，鼠标点击的坐标转换等功能仍未实现；
  2.由于效果需要导致的，移动目标在障碍物拐角处会跳到障碍物里面，然后穿过障碍物；
  3.……
  

• 算法步骤：
  1.初始化地图；
  2.使用Dijstra算法，从终点开始，逐一对最优的邻接节点计算路径，从而计算整张网格化地图上所有点到终点的最短路；
  3.根据最短路形成地图流场；
  

• 参考文章：
  主要参照了这篇文章，思路很简单。