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

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 star...

Full description

Saved in:
Bibliographic Details
Main Author: Rahmat, Mamat
Format: Final Project
Language:Indonesia
Online Access:https://digilib.itb.ac.id/gdl/view/42759
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Institut Teknologi Bandung
Language: Indonesia
id id-itb.:42759
spelling id-itb.:427592019-09-23T14:47:07ZSTUDY OF IMPACTS OF BLOCK SIZE ON BLOCK A* ALGORITHM PROCESSING TIME PERFORMANCE ON STATIC MAPS Rahmat, Mamat Indonesia Final Project pathfinding, graph, A* algorithm, Block A* algorithm INSTITUT TEKNOLOGI BANDUNG https://digilib.itb.ac.id/gdl/view/42759 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. text
institution Institut Teknologi Bandung
building Institut Teknologi Bandung Library
continent Asia
country Indonesia
Indonesia
content_provider Institut Teknologi Bandung
collection Digital ITB
language Indonesia
description 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.
format Final Project
author Rahmat, Mamat
spellingShingle Rahmat, Mamat
STUDY OF IMPACTS OF BLOCK SIZE ON BLOCK A* ALGORITHM PROCESSING TIME PERFORMANCE ON STATIC MAPS
author_facet Rahmat, Mamat
author_sort Rahmat, Mamat
title STUDY OF IMPACTS OF BLOCK SIZE ON BLOCK A* ALGORITHM PROCESSING TIME PERFORMANCE ON STATIC MAPS
title_short STUDY OF IMPACTS OF BLOCK SIZE ON BLOCK A* ALGORITHM PROCESSING TIME PERFORMANCE ON STATIC MAPS
title_full STUDY OF IMPACTS OF BLOCK SIZE ON BLOCK A* ALGORITHM PROCESSING TIME PERFORMANCE ON STATIC MAPS
title_fullStr STUDY OF IMPACTS OF BLOCK SIZE ON BLOCK A* ALGORITHM PROCESSING TIME PERFORMANCE ON STATIC MAPS
title_full_unstemmed STUDY OF IMPACTS OF BLOCK SIZE ON BLOCK A* ALGORITHM PROCESSING TIME PERFORMANCE ON STATIC MAPS
title_sort study of impacts of block size on block a* algorithm processing time performance on static maps
url https://digilib.itb.ac.id/gdl/view/42759
_version_ 1822270194800656384