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

摘要

In game pathfinding ,the grid pathfinding can improve the efficient greatly, butin the 45 degrees 2D games, using the traditional grid generation algorithm needs to consume a very long time. The reason is that when using the Weiler-Athenton algorithm polygon integration there are too much iterations, the iterations consume a lot of time. Weiler-Athenton algorithm is a algorithm that can deal with many situations, but the 45 degrees 2D game map obstacles has very strong particularity. Thus we focused on the characteristics of the 45 degree 2d game map data, design a called boundary crawlingpolygon fusion algorithm. Using the new algorithm, integration time can be reduced from 5-10 hours to 10-20 seconds. Using this algorithm can greatly improve the efficiency of integration of the polygons and provide a strongsupport for real-time preview of the map editor pathfinding.%游戏寻路中采用网格寻路可以极大的提高寻路效率，但是在斜45度2D游戏地图中使用网格寻路，采用传统的网格生成算法需要消耗非常长的时间。原因是使用weiler—Athenton算法进行多边形融合时，会进行很多层递归与循环，消耗大量的时间。由于Weiler-Athenton算法是一种泛用性很强的多边形融合算法，而斜45度2D游戏地图的障碍物又具有很强的特殊性，由此我们针对45度2d游戏地图数据的特点，设计了一种名为边界爬行的多边形融合算法，把原来需要5—10小时才可以完成的融合操作缩短到了10-20秒。极大地提高了多边形融合的效率。为编辑器的地图寻路实时预览提供了有力的支持。