| Abstrakt: |
In video games, artificial intelligence is the effort of going beyond scripted interactions, however complex into the arena of truly interactive systems. To make a game world appear more real, these video games must be responsive, adaptive, and intelligent. For example, in real time strategy games, if there is an enemy seeking/hunting the player, it will be moving in paths, turning around and even maybe jumping in order to find the player. In this case, if the enemy acts/moves more real like human, it will be a benefit for making the game more attractive and exciting. This paper aims to develop a fast, intelligent, and realistic pathfinding approach that makes a user feel that he/she is playing with a human being instead of a machine. To achieve this, this paper presents a Heap Heuristic A* Algorithm as an enhancement of A* algorithm, in which the Chebyshev distance is used to control the smoothness of the resulted path and heapsort algorithm to sort the nodes easily without a lot of memory consumption. Compared to the pervious improved A* algorithms, the proposed algorithm produces a smoother path while consuming less memory to get a final result of human like movement. The experiments results showed that the proposed algorithm reduced the computing time by 66.6% using a grid size of 200*200 compared with A*MOD algorithm. Also, they showed that the proposed work takes almost 91ms to find the path compared to 363 ms and 116 ms when Native A* and A*MOD algorithms are used, respectively, Furthermore, the proposed algorithm performance remains stable in the case of increasing the number of visited nodes, despite the changing order of obstacles. [ABSTRACT FROM AUTHOR] |
