《虚拟角色的智能感知与寻径的研究实现》由会员分享,可在线阅读,更多相关《虚拟角色的智能感知与寻径的研究实现(94页珍藏版)》请在金锄头文库上搜索。
1、l :尊f k分类号U D C 注l密级J 占工27 7学位论文虚拟角色的智能感知与寻径的研究实现( 题名和副题名)林玉洁( 作者姓名)指导教师姓每隆重霆塾握电子科技大学成都( 职务、职称、学位、单位名称及地址)申请专业学位级别硕士专业名称软件工程论文提交日期2 0 1 0 0 4论文答辩日期2 0 1 0 0 5学位授予单位和日期电子科技大学答辩委员会主席评阅人年月日注1 :注明国际十进分类法U D C 的类号。髯独创性声明舢l I I I I I I l l l l l l l l l I I l I I l l | | 1 l I l l Y 18 0 2 8 0 8本人声明所呈交的学位
2、论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所知,除了文中特别加以标注和致谢的地方外,论文中不包含其他人已经发表或撰写过的研究成果,也不包含为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。签名:日期:功,。年 Y 时,该栅格的“视线区间“ 标识为真,反之为假。当然,在应用,根据实际情况的不同,参数的数量( 比如视线方向为北偏东1 5 。,视线角度为1 3 5 。) 将有一定的增加,也会让这个标识转化复杂一点。b “阻挡”标识这个标识是判断栅格是否被障碍物阻挡了眼睛N P C 的视线。这个标识
3、可以用栅格坐标由与眼睛N P C 的位置坐标连接成一条线段,再判断该线段是否通过障碍物的方法来标识。但是,这种线段法要反复的调用环境参数,在每一个栅格的过程中都要调用一次线段经过的栅格数据,当地图规模变大以后,这样的计算量非常大,而且冗余度极高,完全不能满足一个要求实时的在家用计算机上能够运行的感知算法的需求,因此,本论文提出了螺旋遍历算法和射线遍历算法来完成该标识。本论文调用螺旋遍历算法,针对眼睛N P C 依次从近到远遍历栅格,当遍历到可被阻挡的栅格时:若该栅格已经被阻挡标识过了,则继续运行螺旋遍历算法;反之,则“阻挡“ 标识该栅格,然后调用射线遍历算法,并将遍历到的栅格进行“阻挡“ 标识
4、。螺旋遍历算法和射线遍历算法,是本论文模拟真人认知环境的思维方式提出的遍历算法,并在稍后章节中将具体展开描述。c “可见标识完成以上两种标识后,将两种标识进行逻辑判断若该栅格“视线区间”标识为真,且“阻挡标识为假,则“可见”标识为真;反之,为假。( 3 ) 标识三“射击“ 标识这个标识是判断栅格是否是射击点的标识,该标识需要的逻辑判断是“通过”标识为真,“可见”标识为假,且为“阻挡“ 标识运行期间,执行射线算法的起始栅格。2 1电子科技大学硕士学位论文3 2 2 1 螺旋算法螺旋算法即是以某一坐标位置作为中心,按图3 1 螺旋算法的遍历简图所示,进行遍历的一种遍历算法,这种算法保证了遍历以该坐
5、标位置为中心,从近到远的遍历。图3 一l 螺旋算法的遍历简图算法设计的伪代码如下:f o r ( i 从l 依次递加到某方向栅格数的总数)j = O : u p x = O :X 方向的增加量u p z = 一i :Z 方向的增加 确定i 层次循环没有结束;w h il e ( i 层次循环没有结束) 遍历到栅格的x 坐标= 中心x 坐标+ u p x 木栅格中心距离常数:遍历到栅格的z 坐标= 中心Z 坐标十u p z 水栅格中心距离常数: 确定遍历到的栅格;处理该栅格;寻找i 层循环的下一个栅格i f ( ( u p z O ) ( u p x = = i ) )U p z + + ;e
6、l s ei f ( ( u p z 0 ) ( u p z = = i ) ( u p x ! = 一i ) )U p X 一一:e l s ei f ( ( u p z ! 一i ) ( u p x E D A T E 的转换:可直接调用C E L L 结构中的CE D A T E 数据,即是C E L L 的中心坐标。( 3 ) E D A T E C E L L 的转换:这是一个较为复杂的过程,程序设计思路如图3 4 E D A T E | C E L L 转化示意图所示。由于c e l l i 】D 】中的i J 值C - - E D A T E 存在以下的代数关系:CE D A T
7、 E X s e t = - 0 0 5 i 丰( 地板的长度舢A X C E L I 窟讯n 订) ( 公式3 1 )C E D A T E - z s e 仁一0 0 5 I j 牛( 地板的宽度仃吼c E L I 詹n n v I ) ( 公式3 2 )因此我们通过E D A T E X s e t 是否在区间 ( CE D A T E 的X 坐标地板的长度 协x C E L U 姐n 以) ,( C E D A T E 的X 坐标+ 地板的长度懈C E L IM7 M ) 来确定返回i 值。电子科技大学硕士学位论文图3 4 E D A T E 一 C E L L 转化示意图2 6第三章
8、感知算法的研究与实现用E D A T E - Z s e t 是否在区间 ( c _ - E D A T E 的Z 坐标一地板的宽度 瓜脚( C E L L ,N U M ) ,( C j D A T E 的Z 坐标+ 地板的宽度1 儿X C E L L N U M ) 来确定返回的j 值。从而得到所在的c e l l i j 。经过以上处理,我们的n 0 0 r 就已经处理好了。其结构如表3 3 地板结构图所示。表3 3 地板f 1 0 0 r 结构l 地板- 长度地板宽度栅格化后的F j 饱L L 【M A x c E L L ,N u M 【M A x c E L L N U M 】3
9、3 1 2 障碍物加载就障碍物本身而言,就是否能移动可分为静态障碍物和动态障碍物。本论文提出一个新的分类,即是从障碍物能否穿越的性质分为不可穿越障碍物和可穿越障碍物,即是普通障碍物和特殊障碍物。我们的程序设计思路是:穿越每种障碍物方式不同,即是F S M 的不同,如助跑,跳,爬,弯腰,因此我们将障碍物类型与通过该障碍物所需调用的F S M 绑定,然后建立一个e I l 、,i r o n m e n t 类用以遍历和管理所有障碍物;通过e n v 衲n m e n t 遍历每一个障碍物,并对每一个障碍物范围内的c e l l 做以下处理:A 对于普通障碍物来说,当它处于c e l l 之上时,
10、c e l l 的c e l l s t a t e 状态将被恒置于“l ”。B 对于特殊障碍物来说,当它处于c e n 之上时,c e l l 的c e l l s t a t e 状态将被恒置于“2 ”,并将该障碍物关联的F s M 以某种方式储存到c e U 中。具体实现方式如下:( 1 ) 创建一个e l l v i r 0 胁e n t 类,其结构如表3 4 所示。此结构的作用是用单项链表储存所有的障碍物节点,并予以编号和计数。 表3 4 e n v i r o n m e n t 结构e n v i r o n m e n t,一8 i “¥。i ? o。? | f 盎,。j 。?
11、 一、一i ,”,: 巨嘞? 霉斗- l “誓:i 。掣气z ,7 :。,罐,o :j f :( 2 ) 我们创建一个0 b s t a c l e 的结构,用于对障碍物进行设置,其结构如表2 7电子科技大学硕士学位论文3 5 0 b s t a c l e 的结构所示。本论文暂时只支持长方体的障碍物。因此我们就可以用长宽高来完整描述障碍物的形状,并分别储存于1 a r g e o 】l a r g e 1 1 a r g e 2 】中。以障碍物右下角的坐标为障碍物坐标,其XY 值分别储存于p o s 0 ,p o s 【2 】,并用参数o br a t e 表示障碍物与垂直方向的夹角。另外,
12、针对障碍物的类型不同,我们设置一个变量0 bs p e c i a l ,储存障碍物的类型,0 代表普通障碍物,1 代表特殊障碍物,并通过变量s p e c i a l l i I l l ( 连接对应的穿越此障碍物的F s M 。 表3 5 0 b s t a c l e 的结构O b 8 t a c l e巨摹臣纂1 鼍:- 卜鼍:攀j 知。,? “。,r ls 口e e i a I f i n k 。 J,fo7 ,Jt ? “ i p ;pt ? 。i 一,i ,( 3 ) 当障碍物创建好之后,我们以它为基础,创建o b N o d e 节点,结构如表3 6 0 b N o d e 节
13、点结构所示,再把节点压入e n 啊r o 姗e n t 结构中储存,并把e n 啊r o l l l l l e m中的o bp l 】瑚+ 1 。图3 6 0 b N o d e 节点结构E n v 由- 0 1 1 I I l e n t 准备完成后,我们要做的就是把E n V i r o 姗e n t 以c e l l 为单位映射到n o o r 上面。具体程序思路如图3 5 加载环境示意图所示。顺序遍历E n 啊r o l l I I l e n t 里所有的障碍物节点,并对每个障碍物节点做如下处理,每个障碍物所占有的c e l l 的状态值根据障碍物的性质进行改变,如果障碍物为普通障
14、碍物,则其所占有的所有的c e l l ,其c e l l s t a t e 值为1 。如果如果障碍物为特殊障碍物,其c e l l S t a t e 值为2 ,并把对应F S M 映射到c e U 的相应位置中。我们如何判断一个障碍物占有哪些c e l l 呢? 这是一个影响系统效率的关键问题之一。本论文的解决方式如下:首先我们处理的障碍物都是长方体的规则障碍物,因此我们可以利用立体几何知识和相应公式来完成实现。针对每个障碍物,当该障碍物o br a t e - 9 0 。时,我们有明确的范围( 以1 1 x ,1 2 x ,1 3 z ,1 4 Z 为边界) ,公式如下:1 1 x =
15、 呻一 0 1 1 。 g e t ) ( O ;( 公式3 3 )1 2 x = 缸n p 一 o n - 0 b - g e t ) ( O 一缸I l p 一 o I l = 一9 b - g e t L o n g O ;( 公式3 4 )1 3 z = 廿I l p 一 o n 9 b 一 g e t z O ;( 公式3 5 )第三章感知算法的研究与实现1 4 z = 缸n p - 0 1 1 b - g e t Z O - 廿1 1 p 一 0 1 1 。如一 g e t w i d e 。( 公式3 6 )图3 5 加载环境示意图电子科技大学硕士学位论文从c e l l 0 【
16、o J l 顷序遍历,f l o o r 的所有c e l l ,当( c e n 的x 坐标 1 2 x ) & ( c e l l 的z 坐标 1 4 z ) 的值为真则判断c e l l 处于上述区间,则执行以障碍物的o bs p e c i a l 标识c e l l 的c e l l s t a t e ,当障碍物为特殊障碍物时,将s p e c i a l l i l l k 映射到c e l l 的对应储存位置。当0 br a t e ! = 9 0 。时,从c e l l 【O O 】J l 顷序便利,n o o r 的所有c e l l ,此时,障碍物范围的限制公式变为:1 1