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

作     者：王滨 李健 高伦 

作者机构：北京工业大学计算机学院北京100124 

出 版 物：《电脑与信息技术》 (Computer and Information Technology)

年 卷 期：2012年第20卷第3期

页      码：14-16,65页

摘      要：游戏寻路中采用网格寻路可以极大的提高寻路效率,但是在斜45度2D游戏地图中使用网格寻路,采用传统的网格生成算法需要消耗非常长的时间。原因是使用Weiler-Athenton算法进行多边形融合时,会进行很多层递归与循环,消耗大量的时间。由于Weiler-Athenton算法是一种泛用性很强的多边形融合算法,而斜45度2D游戏地图的障碍物又具有很强的特殊性,由此我们针对45度2d游戏地图数据的特点,设计了一种名为边界爬行的多边形融合算法,把原来需要5-10小时才可以完成的融合操作缩短到了10-20秒。极大地提高了多边形融合的效率。为编辑器的地图寻路实时预览提供了有力的支持。

主 题 词：寻路 多边形融合 网格寻路 多边形寻路 

学科分类：12[管理学] 1201[管理学-管理科学与工程类] 081104[081104] 08[工学] 0835[0835] 0811[工学-水利类] 0812[工学-测绘类] 

D　O　I：10.19414/j.cnki.1005-1228.2012.03.005

馆 藏 号：203903814...