Efficient Grid-Based Path Finding Techniques For Android Games Environments

Path finding is one of the main challenges in the artificial intelligence system of game. Path finding is an expensive operation with large memory consumption; hence, it is not efficient in games that play on devices with memory constraints, like smart phones. This study aims at comparing memory consummation and execution time among A*, IDA* and our proposed algorithms on Android operating systems. The paper begins with an almost complete review of the current state of path finding algorithms for the different types of game environments. It then analyzes the search behavior of the aforementioned algorithms. The article presents novel works in the form of search algorithms for use in grid-based game maps: the SEA*, SEIDA*, DEA* and DEIDA* algorithms, which have significant improvements within testbeds and require less use of resources.

Keywords:

A* Search , IDA* Search , Android Games , Artificial Intelligence (AI) , Path Finding , Algorithm Performance