这个是俺的github上的一个导航网格寻路小demo的readme文件，如果读后兴趣的话可以去俺的github上去溜达一圈，可能会有点小收获呢，哈哈哈哈 :)
小demo说明
每个mmorpg游戏中都会少不了有寻路模块，且还是开发中的一个难点，涉及到地形资源、客户端、服务器端，涉及到的算法还比较多，还得注意它的性能开销。相信不少游戏开发者都想弄清楚它是怎么实现的。网上讲解这方面的文章也有不少，github上的开源实现也有一些，不过有很大一部分是unity相关的，或者c#实现的。c++的实现也有，但是没几个像俺这样对初级中级程序员这么友好的。友好的原因如下：
- 俺的这版是导航网格寻路的最简化版，仅是实现了平面多边形(没有嵌套的)的三角剖分和两点之间的寻路，代码量可谓相当少，实现的也比较通俗易懂。
- 俺还会提供一些资料和一些线索来引导你去了解实现的过程。 了解学习一个东西如果一下子把你带到一个很难很深的level的话，恐怕还多人都是吃不消的。就应该循序渐进，按部登阶，从简入深。俺这个就是遵循这样的精神滴。这个是个入门版的，相信聪明的你很快就能看懂学会，说不定修改就直接用到你们的游戏里面了呢！之后还会再发个高阶版的，功能会更丰富更强大。
使用说明
代码这都有，你需要的就是fork或者down下来，然后再你的电脑上编译一下。如果你是用的VS的话，你需要设置一下包含目录和库目录，然后把glut.dll放在你的程序运行目录。编译成功后再运行你会看到如下的程序运行界面：
主要算法
这些都可以在网上查的到，在俺的小demo中应该也很容易找的到的
- 平面多边形三角剖分(Delaunay剖分)
- 多边形用什么数据结构来表示
- 各种几何图形用什么数据结构来表示
- 如何生成网格以及附带数据
- 如何确定一个DT点
- 如何遍历整个多边形来完成三角剖分
- 寻路算法
- 寻路拐点算法
- 判断两条线段是否相交
- 判断点是否在三角形中
- 判断点在向量的那一侧
- 已知三点求三点的夹角
Delaunay剖分是啥？
Delaunay三角剖分其实并不是一种算法，而是一种三角剖分的标准，实现它有多种算法。它只是给出了一个“好的”三角网格的定义，它的优秀特性是空圆特性和最大化最小角特性，这两个特性避免了狭长三角形的产生，也使得Delaunay三角剖分应用广泛。 空圆特性其实就是对于两个共边的三角形，任意一个三角形的外接圆中都不能包含有另一个三角形的顶点，这种形式的剖分产生的最小角最大(比不满足空圆特性的最小角大)
主要类说明
// Polygon类，代表寻路多边形的类，主要实现多边形的三角剖分和寻路
Polygon
vector<Point> points;
vector<Triangle> triangles;
vector<Edge> edges;
Grid grid;
// 三角化
Delaunay()
eindexs // k->v (Pindex->edges的index)，存放着已经处理过的所有三角形的边
restrains // 存放着所有的约束边，在处理开始就已经知道
// 寻路
FindPath()
// 多边形对应的网格结构类，由纵横的线分割的Cell（格子）组成
Grid
vector<Cell> cells;
int gride;
double minx;
double miny;
double maxx;
double maxy;
int xnum;
int ynum;
//格子类，其中包含构成多边形的顶点链表和边链表
Cell
vector<int> points;
vector<int> edges;
// Triangle类，三角形的表示类
Triangle
int p1;
int p2;
int p3;
int edges[3];
Point icenter;//重心
Point lt;
Point rb;
// Edge类，表示经过剖分后的线段，一条线段可能包含一个或两个三角，包含两个点
Edge
int triangles[2];
int points[2];
// Line类，画网格线的时候用到
Line
Point p1;
Point p2;
// Point类，点的表示类
Point
double x;
double y;
// Circle类，表示圆
Circle
Point center;
double r;