Research On Dynamic Routing Problem Based On Navmesh Automatic Routing Algorithms

The research and application of routing algorithms are mainly in the areas of road network routing,disaster relief and so on.With the further development of Internet technology,the rise of game-industry and more and more attention focusing on artificial intelligence and application by smart-cars-industry,correspondingly,the research heat of the pathfinding algorithm is also raised.In the past,the research of road network routing algorithms mainly focused on static grid routing.But in the field of virtualindustry and smart-cars-industry,the need to add the changing road condition information in the mobile process to the algorithm is increasing because of the significant improvement of data acquisition ability.The paper uses NavMesh technology as the research base,focusing on several key issues encountered by NavMesh in the application process,including congestion,blocking detection and traffic path change.The paper uses the new evaluation function F(n)=B*G(n)+H(n)to solve the dynamic path finding problem in the virtual scene running state,and combines the avoidance algorithm without changing the original preprocessing mechanism of NavMesh.The following four points are the improvement measures and improvement results of the four relatively serious problems in the actual application of NavMesh algorithm:1)Congestion problem.It is proved by experiments that the results of the CriterAI pathfinding algorithm used in NavMesh engineering are the same.The improved algorithm introduces the RoadSection data structure,divides the map into different RoadSections,and then calculates the saturation of the RoadSection,by affecting the valuation function.The way of the algorithm has an effect on the path finding of the algorithm,so that different paths are obtained in different congestion states,and the purpose of solving the congestion problem is achieved;2)Path self-adjustment problem.The NavMesh pathfinding algorithm can achieve the same self-adjustment of paths because the results of multiple pathfinding are the same.The improved algorithm solves this problem.According to the dynamics of saturation,the mobile unit re-plans its own moving path according to the actual situation;3)Path blocking detection problem.Due to the concept of adding saturation,when a special situation occurs in a RoadSection,the corresponding RoadSection can be directly accessed,and the saturation is modified through the interface to make the path impotable,which solves the problem of path blocking detection;4)For the problem of road traffic change,when the new path is generated or the old path is modified or even deleted,the algorithm needs to reconstruct the pretreatment operation to achieve re-planning,which is the same as all current traffic planning schemes.Dynamic algorithm does not make this problem more complex.Through the study of the above four problems,the paper verifies the feasibility of introducing saturation and new evaluation function to realize the algorithm,and achieves the basic requirements of dynamic routing.