COMMAX 2020 UiTM Kampus Kuala Terengganu

Video games has risen in popularity due to the increasing number of mobile phone sales. Its portability attracts a lot of people to play mobile games on the go anywhere. Video game industry see this opportunity to further increase the video game engagement by implementing a lot of Artificial Intelligence areas such as pathfinding. The most common pathfinding algorithm used in video game is A*. Even though A* is the most popular algorithm amongst game developers, it’s hardly the best algorithm in finding the true shortest path. This study explores one of the A* variants called Basic Theta*. A mobile game app is developed using Unity Engine. Basic Theta* is implemented in the game using grid-based map representation. Unity Engine provide its own pathfinding solution using A* algorithm with Navigation Mesh (NavMesh) map representation. A comparison is made between these two algorithms to test their performance. The test is done in three different map sizes, 50x50, 100x100 and 200x200. Each map size is tested three times with different starting and ending point. This study shows that Basic Theta* is able to produce the true shortest path compared to A* which produced slightly longer path. The downside is the computation time on Basic Theta* using grid is way higher compared to A* using NavMesh. On a smaller game map the algorithm still takes an acceptable computing time but on a larger size map, the computation time suffers a lot. It can be concluded that Basic Theta* can produce a shorter path compared to A* but with the price of having a higher computation time. Further optimization can be made to reduce the computation time.