前些天看了些关于导航网格的资料,自己也动手实现了一个算法。主要是参考网上的资料,实现的也是局限于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 整个过程的注意
外边界,约束边的定义。
多边形的相交(需要合并多边形)
内嵌多边形的处理
顶点是存储排序
posted on 2010-07-04 17:37
木华 阅读(6258)
评论(15) 编辑 收藏 引用