导航网格寻路C++实现版(进阶版)

内容纲要

这个也是俺的github上的一个导航网格寻路小demo的readme文件,这个工程在原来的基础上有添加了些功能,如果有兴趣可以去俺的github上看看

小demo说明

这个小demo是导航网格寻路C++实现版(入门版)的进阶版,如果你没有看那个工程的话,可以先出门左转看看那个入门版的。那个实现了一个最基本的导航网格寻路,功能简单,代码量也不多,适合没有接触或刚接触寻路功能的朋友们。
而这个是在之前的基础上又新增了一些功能,可以支持更多种类的寻路地图。如果您看过之前那个版本的代码实现的话,再看这个应该是很好看懂的。

新增了那些功能

  1. 之前的版本一个地图是只支持一个多边形的,而且多边形不支持嵌套多边形。而这个版本的在一个地图中支持多个多边形,并且一个多边形支持嵌套多个多边形,可以映射大部分的游戏中的地图(此为主要的新增功能)
  2. 检测两点是否相通,即两点都在地图内且中间没有阻挡
  3. 从一个沿指定方向寻路,对应着游戏中用摇杆移动角色
  4. 把经过三角剖分的地图多边形信息以二进制形式保存到文件中,方便以后直接读取并还原成Path类

使用说明

  1. fork或者down下来
  2. 在你的电脑上新建个c++的工程,设置一下glut的包含目录和库目录
  3. 把glut.dll放在你的编译好的程序目录下
  4. 工程中的map目录是程序读取的地图文件,你需要在navmesh.cpp中的DrawLines方法中指定读取那个地图文件
  5. 运行程序,在程序窗口点击第一下为寻路的起点,再点击第二下为寻路的终点,并进行寻路。点击第三下会把之前的路径清空。
  6. 在程序窗口右击会出现一个菜单,可以选择要测试的方法

map目录中的地图文件怎么来?

这个文件是根据美术或者地编制做的游戏地图按照一定的格式导出来的供程序用的。其中描述了地图中有几个多边形构成、构成多边形的点的位置信息。文件格式如下:

childsize,parentlength, parentpoints,[0,child1length,child1points, [0,child2length, child2points]]
内嵌多边形数量,父多边形点的数量,父多边形的点,[0,子多边形1点的数量,子多边形1的点,[0, 子多边形1点的数量,子多边形1的点]]

其中每一个上述的格式代表一个多边形,且多边形可以嵌套。而文件是有多个上述格式构成的。

程序截图

其中红色的线是平面多边形,你可以把它看成游戏中的地图的边界和障碍区域。
绿色的线表示经三角剖分后构成的线
蓝色的线代表寻路的路径

  • 包含两个嵌套多边形的地图
  • 根据场景资源生成的地图

主要算法

这些都可以在网上查的到,在俺的小demo中应该也很容易找的到的

  • 平面多边形三角剖分(Delaunay剖分)
    • 多边形用什么数据结构来表示
    • 各种几何图形用什么数据结构来表示
    • 如何生成网格以及附带数据
    • 如何确定一个DT点
    • 如何遍历整个多边形来完成三角剖分
  • 寻路算法
  • 寻路拐点算法
  • 判断两条线段是否相交
  • 求两条直线的交点
  • 判断点是否在三角形中
  • 判断点在向量的那一侧
  • 已知三点求三点的夹角