随笔-15  评论-18  文章-9  trackbacks-0

    前些天看了些关于导航网格的资料,自己也动手实现了一个算法。主要是参考网上的资料,实现的也是局限于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 木华 阅读(6281) 评论(15)  编辑 收藏 引用

评论:
# re: 导航网格 2011-11-18 13:12 | 深海妖妖精
楼主,源代码发我一份吧,不胜感激啊,175841074@qq.com,qq175841074  回复  更多评论
  
# re: 导航网格 2011-11-24 21:10 | 木华
发了@深海妖妖精
  回复  更多评论
  
# re: 导航网格 2012-06-12 22:38 | liuct
liuct2001@sina.com 代码能分享一下吗。谢谢了。正好需要这方面  回复  更多评论
  
# re: 导航网格 2015-03-02 17:07 | 镜子蓝玉
455786463@qq.com 楼主有github类似的开源主页吗?我也想阅读以下你的源码,正好遇到类似的问题。因为还不知道怎么自动生成网格,暂不打算直接使用此算法。  回复  更多评论
  
# re: 导航网格 2015-03-08 15:27 | 木华
@镜子蓝玉
电脑不在身边,改天找到再推上github吧。  回复  更多评论
  
# re: 导航网格 2015-03-17 15:24 | valiant
三角网格导航可以看看我的博客
http://programsdog.com/?thread_category=github  回复  更多评论
  
# re: 导航网格 2015-03-17 15:24 | valiant
# re: 导航网格 2015-04-16 17:30 | souluo
也可以参照moba类游戏之导航网格寻路及RVO碰撞思路
http://51souluo.com/?p=465  回复  更多评论
  
# re: 导航网格 2015-06-08 16:02 | 游戏小码农
求大神导航网格相关源码
65126648@qq.com
万分感激  回复  更多评论
  
# re: 导航网格 2015-07-21 22:22 | 流浪猫
求大神一份远吗!不胜感激!
cs1994726@163.com  回复  更多评论
  
# re: 导航网格 2015-09-02 10:20 | 迷途杨
求大神给一份源代码,谢谢
yangtai_ming@163.com  回复  更多评论
  
# re: 导航网格 2016-03-11 09:46 | 金萧山
150376844@qq.com
求一份代码,谢谢  回复  更多评论
  
# re: 导航网格 2016-03-16 10:19 | 忆艺
求师傅给一份源代码,徒弟万分感谢!  回复  更多评论
  
# re: 导航网格 2016-03-16 10:21 | 忆艺
求师傅给一份源代码,徒弟万分感谢!1170429762@qq.com  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理