Corridor-based Heuristic Long-distance Pathfinding Algorithm Research And Its Implementation In Animation Collaboration System

With the rapid development in the field of virtual reality and artificial intelligence,multiplayer simultaneous online real-time strategy games have become the mainstream game product in the industry.As the basic operation of a game character,automatic pathfinding mainly studies how to plan the action path for a character in the dynamic changing game world,i.e.how to find a route with the shortest path in the shortest time.The traditional pathfinding algorithm cannot combine the scene and target points well in the process of node search and has certain blindness.In recent years,heuristic pathfinding algorithms have been widely studied and applied because of their good performance.This method uses the heuristic information of the problem to guide the search process to reduce the search range and the complexity of the problem.This method combines the advantages of a single-source shortest path algorithm and heuristic priority search to improve the efficiency of the algorithm while ensuring the path is relatively optimal.In RPG games,the reachability analysis of pathfinding and pathfinding computation often needs to be completed within the time frame from the time the task is issued to the start of the character pathfinding.Heuristic pathfinding algorithms have good time performance in local pathfinding over short distances.However,during long-distance global pathfinding,the heuristic pathfinding system often requires a certain response time as the scene scale becomes larger and the terrain more complex.This pathfinding delay is intolerable for framesynchronization-based MMO games.In this thesis,we focus on the heuristic long-distance pathfinding algorithm,improve and optimize it for the problems of redundant computation of similar paths in RPG games,the large computational scale of pathfinding nodes in large scenes,and cross-terrain pathfinding cooperation,introduce the concept of corridor and performance group system,and split the long-distance pathfinding problem into several pathfinding sub-problems among path points,to improve the time performance of the pathfinding algorithm and improve game animation effect and user experience.Specifically,the long-distance pathfinding is split into intracorridor pathfinding and direct pathfinding on the premise that the reachability of the pathfinding start and endpoints is judged to be true,and the optimal path between the waypoints in the corridor is precomputed.The optimal sequence of target waypoints within the undirected graph composed of waypoints is computed quickly to avoid redundant computation during game runtime.In addition,we partition the wayfinding nodes to save the wayfinding time by quickly determining the reachability between any two points in the scene and eliminating the illegal wayfinding target points.In addition,to address the problems of state management and inter-module collaboration in the state-machine-based animation system,we introduce the performance group system to realize the scene perception and performance transformation of game characters in different terrains during pathfinding,to realize the cross-terrain animation collaboration in long-distance pathfinding.In summary,based on the heuristic long-distance pathfinding,this thesis performs waypoint segmentation and path precomputation on the scene and integrates animation collaboration and pathfinding algorithms to finally complete a complete collaborative pathfinding system.Finally,this thesis shows that the proposed corridor-based heuristic long-distance pathfinding algorithm can effectively solve the problems of similar path redundancy calculation in long-distance pathfinding and the difficulties of animation system state management and inter-module collaboration in the process of multi-terrain pathfinding through result testing and comparison experiments.