PERBANDINGAN ALGORITMA A* DAN ITERATIVE DEEPENING A* PADA PENCARIAN RUTE TERPENDEK TERHADAP NON-PLAYER CHARACTER DALAM ROLE PLAYING GAME
Total View This Week0
Total View This Week0
Institusion
Universitas Sriwijaya
Author
WAHYU HIDAYAT (STUDENT ID : 09021381320027)
Rusdi Efendi (LECTURER ID : 8826630017)
Anggina Primanita (LECTURER ID : 0206088901)
Rusdi Efendi (LECTURER ID : 8826630017)
Anggina Primanita (LECTURER ID : 0206088901)
Subject
T58.5 General works Management information systems Cf. HD30.213 Industrial management Cf. HF5549.5.C6+ Communication in personnel management Cf. TS158.6 Automatic data collection systems (Production control)
Datestamp
2019-10-18 03:57:45
Abstract :
Role Playing Game (RPG) needs realistic Artificial Intelligence, pathfinding is one of the requirements to achieve it. One of the popular algorithm for pathfinding is A*, but A* still has problem about its memory usage. Iterative Deepening A* (IDA*) is an algorithm like A* that uses Depth First Search to prevent the large memory usage. This research develops a game that implements pathfinding method to enemy character using A* and IDA* algorithms to compare their memory and time usages for pathfinding. Heuristic function that used is Manhattan Distance. This research uses 3 different types of map (without obstacle, simple obstacle, and complex obstacle) with 3 different samples in each type of map as tool for comparing the memory and time usage by A* and IDA*. The conclusion of this research are memory and time usage for A* and IDA* is affected by the size of map (node quantity), position of the obstacles on map, and the obstacle quantity. Then, IDA* Algorithm is generally better than A* in case of memory and time usage especially if the map doesn?t have any obstacle, but IDA* can be worse if the enemy character and player are at the parallel position that covered by obstacle
Role Playing Game (RPG) needs realistic Artificial Intelligence, pathfinding is one of the requirements to achieve it. One of the popular algorithm for pathfinding is A*, but A* still has problem about its memory usage. Iterative Deepening A* (IDA*) is an algorithm like A* that uses Depth First Search to prevent the large memory usage. This research develops a game that implements pathfinding method to enemy character using A* and IDA* algorithms to compare their memory and time usages for pathfinding. Heuristic function that used is Manhattan Distance. This research uses 3 different types of map (without obstacle, simple obstacle, and complex obstacle) with 3 different samples in each type of map as tool for comparing the memory and time usage by A* and IDA*. The conclusion of this research are memory and time usage for A* and IDA* is affected by the size of map (node quantity), position of the obstacles on map, and the obstacle quantity. Then, IDA* Algorithm is generally better than A* in case of memory and time usage especially if the map doesn?t have any obstacle, but IDA* can be worse if the enemy character and player are at the parallel position that covered by obstacle
File :
RAMA_ 55201_ 09021381320027_compressed.pdf
RAMA_ 55201_ 09021381320027_8826630017_0206088901_01_front_ref.pdf
RAMA_ 55201_ 09021381320027_8826630017_0206088901_02.pdf
RAMA_ 55201_ 09021381320027_8826630017_0206088901_03.pdf
RAMA_ 55201_ 09021381320027_8826630017_0206088901_04.pdf
RAMA_ 55201_ 09021381320027_8826630017_0206088901_05.pdf
RAMA_ 55201_ 09021381320027_8826630017_0206088901_06_ref.pdf
RAMA_ 55201_ 09021381320027_8826630017_0206088901_07_lamp.pdf
Download
book
BibTex
Latex, Jabref
cloud_download
Original Resource
url resource Institution
