当前位置:首页 >> 信息与通信 >>

一种高效的多边形寻路元数据融合方式——边界爬行算法_论文

第2 0卷 第 3期  2 01    2年 6 月     电   脑  与  信  息  技  术  Vo 2   .  L O No3 Co u e  n  If r to   c n l a   mp tr a d no main Te h oo v Jn 2 1  u .02 文章编号 :0 5 12 (0 2 0 — 0 4 0  10 — 2 82 1 )3 0 1 — 3 一 种高效 的多边形寻路元数据 融合方式—— 边界爬 行算法  王 滨, 李 健 , 伦  高 10 2 ) 0 1 4  ( 北京工业 大学计算机 学院, 北京 摘 要: 游戏寻路 中采用网格寻路 可以极大的提 高寻路效率 , 但是在斜 4 5度 2 D游戏地图中使用网格 寻路 , 采用传统的 网   格 生成算法需要 消耗非常长的时间。原 因是使 用 wee— h no irAtetn算法进行 多边形融合时 , l 会进行很 多层递 归与循环 , 消  耗 大量的时间。由于 Wee— tetn算法是一种 泛用性很 强的多边形融合算法, l fr Ah no 而斜 4 5度 2 D游戏地 图的障碍物又具  有很 强的特殊性 , 由此我们针对 4 度 2 游戏地图数据的特 点, 了一种名为边界爬行的 多边形融合 算法 , 原来需要  5 d 设计 把 51 — 0小时才可以完成的融合操作缩短到了 1 - 0秒。 大地提 高了多边形融合的效率。 02 极 为编辑 器的地图寻路 实时预览提  供 了有力的支持 。   关键词 : 寻路 ;多边形 融合 ; 网格寻路 ; 多边形寻路  中 图分 类 号 :P1  T 8 文献 标 识 码 :  A An Ef ce   l g n nt g a i n Al o ihm n Grd    f intPo y o I e r to   g rt i I  i Pa h n ng- bo d rCr wl   g rt   t f di i - r e   a i Al o ihm ng W A NG B n, I i   i L  a J n,GA0  u   Ln ( lg f o ue cecsB in   ie i f eh ooy,e ig10 2 , i ) Col eo C mp tr ine, eigUn rt o T cn lg B in 0 14 Chn   e S j v sy j a Ab t a t I   a   ah n i g , e sr c :n g me p tf d n t   i h d p t f d n   a  mp o e t e e iin   r a y u i  h   5 d g e s 2 g m e,u ig   a i i g c n i r v  h   fce tg e t .b t t e 4   e r e   D  a s s   hn l n n te rdt n l 酣 d e ea o   lo tm  ed t o sne  v r  o g i .Th   es n s h t h n s g h   h  t i a a i o  g n rt n a rh n e s o nu l i gi  c  a ey ln  t me e ra  i a o  t  w e  ui  te n W elr t n o lg rtm  poyg n i e rto i —A he t n a o ih e l o ntg a n t r  ae t  m uc  ieai n , t e t rto   c s m e a o  o  tTe  i he e r  oo h tr to s h  ie a ns on u    l t f i l. i l W el r At e t n ag rtm  s a a o t m  h t c n d a wi   n   i a o s u   h   5 d g e s 2 g l e ma   b tce  i — h no   loi e h i   l r h t a  a   e   t ma y s u t n ,b t t e 4   e e  D  a l  p o s l s   gi l h t i r T a h s v r    ̄o g p r c lr y a  e y s n   at u ai .Th s we f c s d o   e c aa tr t s o   e 4   e r e 2   a  ̄  p d t,d s n a c l d i t u     o u e   n t   h rce s c  f t   5 d g e   d g n e ma   aa ei     al   h ii h g e b u d r  rwl g oy o  u i n ag rtm.Us g t e n w  g r h o n y c a i p lg n f s   o h a n o l i i   h   e a o t m,i t ga o  i   alb   e u e   r m  5 0 h u S n l i n ert n t i me c r e r d c d fo   -1   0 r   t 1 o 0—2O e on s  sc d .U sng t i ag rt  c n g e t m p o  t  e ce c  o  n e rto i  hsl o h im a r al y i r ve he f in y f i t ga n o  he i i f t  poyg s nd l on a  pr i e   ov d  a sr n u por or ra —tTe pr ve oft   a   d t   tfn n