An Efficient Polygon Integration Algorithm In Grid Pathfinding-border Crawling Algorithm
Lun Gao · Computer and Information Technology · 2012
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.