前些天看了些关于导航网格的资料，自己也动手实现了一个算法。主要是参考网上的资料，实现的也是局限于2维平面中，其实导航网格在3D场景中才能发挥其强大功能。但是，如何在3D中应用，这是一个需要考究的问题了，如果只是简单的把3D场景映射，不考虑一些复杂的环境，比如相交叉的上下层道路的话则会很简单。以及要在场景中如何获得导航网格都是一个需要解决的问题。下面是我在实现一个简单的导航网格算法的一些参考资料。实现的整个过程是是比较繁杂的，我并没有考虑一些多边形的相交合并等。

主要参考

http://blianchen.blog.163.com/blog/static/13105629920103211052958/

三个步骤

1.nav网格的生成

2.网格路径的搜索

3.在已经网格路径中找路径

1.1 参考

Delaunay三角剖分算法

http://www.cnblogs.com/renliqq/archive/2008/02/06/1065399.html

Voronoi图——定义介绍

http://zhmhd.spaces.live.com/blog/cns!A3336F71394B500F!957.entry

Delaunay三角剖分(Delaunay Triangulation)相关知识

http://www.cnblogs.com/soroman/archive/2007/05/17/750430.html

1.2 使用的算法

参考论文：

平面多边形域的快速约束 Delaunay 三角化 曾微 等等。

1.3 涉及的数学知识

（1）向量    

夹角的比较

向量间的关系（顺时钟，逆时针）

（2）直线 

     直线与直线的关系：

相交

不相交（如果是公共点都是顶点则判断为不相交，看具体算法如何实现）

（3）直线与点的关系

点在直线左边

点在直线右边

点在直线上

（所以直线需要有方向性）

（4）多边形

顶点的存储是否有序，按什么顺序都将对后面的算法有影响。

（5）矩形

快速判断是否相交

（6）三角形

顶点顺序的定义。边的顺序的定义。

求三角形的外接圆。

（7）圆

求圆的外界包围盒。

2.1 参考

深入A*算法 http://creativesoft.home.shangdu.net/AStart2.htm

2.2 使用A* 算法搜索的评估函数

f（n） = g（n）+ h（n）

g（n） = g（n-1） + 上一个三角形的中心到该三角形中心的欧拉距离。

h（n） = 该三角形中心到目标点的欧拉距离。

2.3 需要处理的一些东西

（1）数据结构

如何处理所有网格之间的联系

节点的数据结构设计

搜索路径的记录（除了是那个三角形，也应该记录是从那条边穿过）

（2）涉及到的（如果使用链表）

判断三角形之间是否共用边，共用了那条边

点是否在三角形上。

链表排序

3.1 参考

NAV导航网格寻路 -- 寻路方法 http://blianchen.blog.163.com/blog/static/1310562992010324046930/

3.2 算法使用（选择了拐点法）注意事项

（1）找到穿越边并办边的两个顶点分别定义为左点和右点（定义在整个算法过程中要一致）

（2）* 如果选择了一个点作为拐点，则要把拐点作为开始点重新进行

（3）* 对最后的目标点的处理

（4）*判断拐与不拐时的临界条件

4 整个过程的注意

  外边界，约束边的定义。

  多边形的相交（需要合并多边形）

  内嵌多边形的处理

  顶点是存储排序