导航网格寻路C++实现版(入门级)

内容纲要

这个是俺的github上的一个导航网格寻路小demo的readme文件,如果读后兴趣的话可以去俺的github上去溜达一圈,可能会有点小收获呢,哈哈哈哈 🙂

小demo说明

每个mmorpg游戏中都会少不了有寻路模块,且还是开发中的一个难点,涉及到地形资源、客户端、服务器端,涉及到的算法还比较多,还得注意它的性能开销。相信不少游戏开发者都想弄清楚它是怎么实现的。网上讲解这方面的文章也有不少,github上的开源实现也有一些,不过有很大一部分是unity相关的,或者c#实现的。c++的实现也有,但是没几个像俺这样对初级中级程序员这么友好的。友好的原因如下:

  • 俺的这版是导航网格寻路的最简化版,仅是实现了平面多边形(没有嵌套的)的三角剖分和两点之间的寻路,代码量可谓相当少,实现的也比较通俗易懂。
  • 俺还会提供一些资料和一些线索来引导你去了解实现的过程。
    了解学习一个东西如果一下子把你带到一个很难很深的level的话,恐怕还多人都是吃不消的。就应该循序渐进,按部登阶,从简入深。俺这个就是遵循这样的精神滴。这个是个入门版的,相信聪明的你很快就能看懂学会,说不定修改就直接用到你们的游戏里面了呢!之后还会再发个高阶版的,功能会更丰富更强大。

使用说明

代码这都有,你需要的就是fork或者down下来,然后再你的电脑上编译一下。如果你是用的VS的话,你需要设置一下包含目录和库目录,然后把glut.dll放在你的程序运行目录。编译成功后再运行你会看到如下的程序运行界面:

其中红色的线是平面多边形,你可以把它看成游戏中的地型。
绿色的线表示经三角剖分后构成的线
蓝色的线代表寻路的路径
程序运行时在窗口点击第一下为寻路的起点,再点击第二下为寻路的终点。点击第三下会把之前的路径清空。

主要算法

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

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