PERBANDINGAN ALGORITMA A* DAN ITERATIVE DEEPENING A* PADA PENCARIAN RUTE TERPENDEK TERHADAP NON-PLAYER CHARACTER DALAM ROLE PLAYING GAME

HIDAYAT, WAHYU and Efendi, Rusdi and Primanita, Anggina (2018) PERBANDINGAN ALGORITMA A* DAN ITERATIVE DEEPENING A* PADA PENCARIAN RUTE TERPENDEK TERHADAP NON-PLAYER CHARACTER DALAM ROLE PLAYING GAME. Undergraduate thesis, Sriwijaya University.

	Text RAMA_ 55201_ 09021381320027_compressed.pdf - Accepted Version Restricted to Repository staff only Available under License Creative Commons Public Domain Dedication. Download (1MB) | Request a copy
Preview	Text RAMA_ 55201_ 09021381320027_8826630017_0206088901_01_front_ref.pdf - Accepted Version Available under License Creative Commons Public Domain Dedication. Download (429kB) | Preview
	Text RAMA_ 55201_ 09021381320027_8826630017_0206088901_02.pdf - Accepted Version Restricted to Repository staff only Available under License Creative Commons Public Domain Dedication. Download (141kB) | Request a copy
	Text RAMA_ 55201_ 09021381320027_8826630017_0206088901_03.pdf - Accepted Version Restricted to Repository staff only Available under License Creative Commons Public Domain Dedication. Download (568kB) | Request a copy
	Text RAMA_ 55201_ 09021381320027_8826630017_0206088901_04.pdf - Accepted Version Restricted to Repository staff only Available under License Creative Commons Public Domain Dedication. Download (433kB) | Request a copy
	Text RAMA_ 55201_ 09021381320027_8826630017_0206088901_05.pdf - Accepted Version Restricted to Repository staff only Available under License Creative Commons Public Domain Dedication. Download (17kB) | Request a copy
	Text RAMA_ 55201_ 09021381320027_8826630017_0206088901_06_ref.pdf - Accepted Version Restricted to Repository staff only Available under License Creative Commons Public Domain Dedication. Download (63kB) | Request a copy
	Text RAMA_ 55201_ 09021381320027_8826630017_0206088901_07_lamp.pdf - Accepted Version Restricted to Repository staff only Available under License Creative Commons Public Domain Dedication. Download (178kB) | Request a copy

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

Item Type:	Thesis (Undergraduate)
Uncontrolled Keywords:	Artificial Intelligence, Pathfinding, Non-Player Character, A* Algorithm, Iterative Deepening A* Algorithm, Role Playing Game
Subjects:	T Technology > T Technology (General) > T58.5-58.64 Information technology > 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)
Divisions:	09-Faculty of Computer Science > 55201-Informatics (S1)
Depositing User:	Mr Halim Sobri
Date Deposited:	18 Oct 2019 03:57
Last Modified:	18 Oct 2019 03:57
URI:	http://repository.unsri.ac.id/id/eprint/11993

Actions (login required)

View Item