Research On Game Map Routing And Path Smoothing Optimization

In recent years,China's game industry has not only created a larger output value,but also promoted the development of related industries.The game industry has become an important pillar of the entertainment industry and network economy,and even has become one of the most potential growth points in the cultural industry.It is also because of the network technology is so developed,there are more and more games on the network.Therefore,if we want the game to be competitive in the market,we must improve the quality of the game,and the user experience of the game determines the quality of the game.In the game,the path search system of role automatic pathfinding has always been a very important part.Now the map of the whole scene of the game is becoming larger and larger,and the traditional a * pathfinding algorithm greatly reduces the computational efficiency in the face of huge amount of map data,which leads to the phenomenon that the screen gets stuck when players play,and then affects the user experience of the game.Therefore,how to solve the computational burden caused by the huge map data and optimize the traditional routing algorithm and path becomes very important.This paper has done two aspects of work to solve the problem of low computational efficiency of A* algorithm in the case of large-scale map data.The first aspect is to address the problem of too many nodes searched by the A*algorithm in a large-size map,and a map preprocessing method based on Mean-shift and A* is proposed;the second aspect is for the A* algorithm when circumventing obstacles.For the problem of too many inflection points on the route,a path smoothing optimization method based on the A* algorithm based on region division and Bezier curve is proposed:(1)Map preprocessing method based on Mean-shift and A*: first select a two-dimensional map,convert the data of the two-dimensional map into rasterized data through the rasterization method,and mark obstacles to generate obstacle data;Then use the Mean-Shift clustering algorithm to classify the obstacle data on the entire map,and get the clustering results to be used to divide the map;then the obtained clustering results are first generated into the area with obstacles,and then through the area with obstacles The data divides the barrier-free area,and then divides the entire map unevenly into several areas;and through the method of defining key points at the edges of each area of the map,the areas are connected through key points;finally,the design is based on the key point data The path-finding strategy between key points connects the path-finding results in each area to generate path results.The results of comparative experiments show that the proposed map preprocessing method can better reduce the number of search nodes of the A* algorithm in the large-size map,and improve the search efficiency.(2)A* algorithm path smoothing optimization method based on area division and Bezier curve: First,according to the area data in(1),a straight path is used to replace the A* path finding between key points in the obstacle-free area.The shortest straight path is obtained,thereby reducing a part of the inflection points;then through the Bezier N-order curve formula,the path near the inflection point of the path and the path near the key points of the area are respectively smoothed,so that the entire route is closer to the reality.The comparative experiment results show that the output path of the proposed smooth path method is shorter and the path at the inflection point is smoother,which is more in line with the actual walking path.