Research On Hierarchical Pathfinding And Complexity Measure Of Game Maps

Electronic game is a popular style of entertainments enjoyed by the people. Thedevelopment of Electronic games is often accompanied by continuousupdate of computer technology. In the past few years, the powerful sound and finescreen is an important factor to attract game players who prefer games closer to thereal environments. With the improvements of computer hardware and software, thetechnology of picture and sound in games has got its limitation. The competition ofthe game technology has been moved from picture and sound to game plot andintelligence of characters. Therefore, artificial intelligence technology is more andmore used to the field of electronic games.Pathfinding technology in games is an important application in Game AI.Efficient pathfinding algorithms can reduce searching time and the consumption ofhost resource. A*is an often used algorithm in pathfinding. It can always find theoptimal path if there is such a path. The shortcomings of A*is the high cost of spaceand time when the map is large. Then hierarchical pathfinding algorithms occur inrecent years. HPA*algorithm is a typical hierarchical pathfinding algorithm whichgreatly improved the efficiency of A*. However, HPA*does not consider the terraininformation when partitioning maps, lowering the path-finding optimal degree in openareas. In this research, we present a method based on finding a minimal rectanglewhich can cover the obstacles. By doing this, large open areas change into a fewrectangle clusters of which number is smaller than that of HPA*. In such clusters,path-finding can be done like the beeline path-finding. In this way, the proposedmethod reduces the number of key points and enhances the optimal degree ofpathfinding. Finally the experiment verifies the effectiveness of this method.On the other hand, game map is the platform of pathfinding and the design ofgame maps will affect the game complexity and the pathfinding efficiency. A methodis required which can measure the map complexity and then further measure thedesign of maps. In this work, firstly, we introduce a map complexity measure basedon Hamming-distance, and then we define a relative Hamming-distance which canmeasure the complexity of maps in difference scales by computing the ratio of theactual complexity of map and maximum complexity the map can achieve. Finally, theconcept of map region variance is introduced in the complexity measure.Experimental results show that the new measure can better reflect the complexity ofmaps with different sizes and different obstacle distributions, and has a strongcorrelation to the efficiency of a hierarchical pathfinding algorithm, HPA*.