The Game Field Heuristic To Find The Use And Optimization Of The Routing Algorithm

The traditional path-finding system finds a path in the game scene using A~* algorithm. The A~* algorithm has been widely used and researched, so the A~* algorithm will be hardly optimized. Therefore the search space is focused for optimizing the path-finding system.This project is the path-finding system within a MMOG (Massively Multi-player Online Game) project. This project focuses how to optimize and generate the search space for 3D compound game scene. In the early version, the multi-height grid was used for creating the search space. But the multi-height grid cannot work for complex game scene because of higher space complexity. Finally, the polygon navigation mesh was used for search space generation. The polygon navigation mesh is the better solution for 3D game search space generation for its excellences, fewer nodes and higher covering rate. The navigation mesh can be generated from origin modeling data and optimized automatically.Using the polygon navigation mesh to replace the triangle navigation mesh 30% mesh checked nodes are reduced. It improves the performance of path-finding system. Now, it is setup into the game project and gets good response from game programmers and designers.Actually, the polygon navigation mesh has some shortages such as less precision of game terrain describing and not support movable blocks. And the system is focused on NPCs (non-player characters), which cannot jump up and down in the meshes. Because of weak moving ability, PCs (player characters) can find some special region to block NPCs. These problems will be fixed in the future.