STUDY OF IMPACTS OF BLOCK SIZE ON BLOCK A* ALGORITHM PROCESSING TIME PERFORMANCE ON STATIC MAPS

• Main Author: Rahmat, Mamat
• Format: Final Project
• Language: Indonesia
• Online Access: https://digilib.itb.ac.id/gdl/view/42759
• Institution: Institut Teknologi Bandung

Pathfinding is the search for the shortest path from the starting point to the destination point on a map. The pathfinding algorithm is commonly used in computer games. In computer games, the pathfinding algorithm is not only run once, but generally runs many times during the game for different starting points and destination points. The need for real-time interaction in computer games and limited processor and memory resources requires the development of an efficient pathfinding algorithm so that the shortest path can be calculated quickly. Block A* algorithm is the development of A* algorithm on the grid. This algorithm divides the map in the form of a grid into blocks of the same size. Pre-computation is performed on each possible obstacle configuration in the block to obtain the shortest local distance data between the side cells of the block. This data is stored in a data structure called LDDB and is used to speed up the calculation of block expansion in the main algorithm of Block A*. Increasing block size has the potential to improve the performance of the Block A * algorithm's processing time. The results of this final project indicate that the block size affects the increase in the performance time of the Block A * algorithm. The performance increase logarithmically where in general there is a significant decrease in processing time at enlargement of block size for small block sizes. However, the increment of performance is became more insignificant when the block size is enlarged. In a large block size, in general there is a decrease in performance due to the initialization process which is more dominant in large block sizes.