The pathway for agent and robot enemy in strategy game with high efficiency model

Path finding is importance for various areas such as robotic, game and transportation. It has a significant effect to the prosperity of economic increasingly. This research proposes three essential improvements. First, the position of each agent (player or robot) will be transferred to multilayer scene using Perspective Projection Method (PPM). It is able to send begin position and destination position to difference layer in the online game. These positions will be compressed at the server site before sending to revert at PC with projection algorithm. Second, we propose Depth Direction A*(DDA*) algorithm which is a newly improve method. It uses linear graph theory together with A* classic Algorithm. DDA* will help increase efficiency in avoiding hard obstacle of the scene. With this method, an agent can move more naturally than previous method. The method will reduce the number of expanding child nodes as compare to A* classic algorithm certainly. In addition, the agent takes less movement time than previous algorithm. This research emphasizes on a more reality environment of multi-layer together with multi-terrain types. Third, we propose technique to separate out different route by generate sub-begin point and sub-destination point in each part between the begin point and the destination point. With this technique, the search procedures will be adjusted automatically according to the heterogeneous environment. The experimental result shows that our method is able to decrease expansion of child nodes between 22.12 - 70.67% in a single layer environment. This depends upon the property of terrain types which will affect the movement speed obviously.