IMPLEMENTASI DAN ANALISIS ALGORITMA A* DAN JUMP POINT SEARCH UNTUK MENENTUKAN JALUR TERPENDEK PADA NON PLAYER CHARACTER

APRILYADI, DENI and Sazaki, Yoppy (2020) IMPLEMENTASI DAN ANALISIS ALGORITMA A* DAN JUMP POINT SEARCH UNTUK MENENTUKAN JALUR TERPENDEK PADA NON PLAYER CHARACTER. Undergraduate thesis, Sriwijaya University.

	Text RAMA_55201_09021381320034.pdf - Accepted Version Restricted to Repository staff only Available under License Creative Commons Public Domain Dedication. Download (4MB) | Request a copy
Preview	Text RAMA_55201_09021381320034_0006067406_01_front_ref.pdf - Accepted Version Available under License Creative Commons Public Domain Dedication. Download (1MB) | Preview
	Text RAMA_55201_09021381320034_0006067406_02.pdf - Accepted Version Restricted to Repository staff only Available under License Creative Commons Public Domain Dedication. Download (620kB) | Request a copy
	Text RAMA_55201_09021381320034_0006067406_03.pdf - Accepted Version Restricted to Repository staff only Available under License Creative Commons Public Domain Dedication. Download (1MB) | Request a copy
	Text RAMA_55201_09021381320034_0006067406_04.pdf - Accepted Version Restricted to Repository staff only Available under License Creative Commons Public Domain Dedication. Download (1MB) | Request a copy
	Text RAMA_55201_09021381320034_0006067406_05.pdf - Accepted Version Restricted to Repository staff only Available under License Creative Commons Public Domain Dedication. Download (33kB) | Request a copy
	Text RAMA_55201_09021381320034_0006067406_06_ref.pdf - Bibliography Restricted to Repository staff only Available under License Creative Commons Public Domain Dedication. Download (149kB) | Request a copy
	Text RAMA_55201_09021381320034_0006067406_07_Lamp.pdf - Accepted Version Restricted to Repository staff only Available under License Creative Commons Public Domain Dedication. Download (289kB) | Request a copy
	Text RAMA_55201_09021381320034_TURNITIN.pdf - Accepted Version Restricted to Repository staff only Available under License Creative Commons Public Domain Dedication. Download (16MB) | Request a copy

Abstract

Pathfinding is the way to find the shortest route between two points. The A* and Jump Point Search algorithms use the number of nodes that must be taken to determine the shortest path that can be traversed by the NPC. To reach the goal, the NPC must go through a node that is not an obstacle so it can form a path that will be taken as the shortest path. A * algorithm combines Uniform Cost Search and Greedy-Best First Search, with the calculated costs derived from actual costs plus estimated costs, whereas the JPS algorithm uses pruning rules and jumping rules to do a simple pruning, with the aim of jumping over many places that only considered necessary. From the 5 levels of testing that has been conducted, the result shows that JPS algorithm can reduce the amount of nodes that will be used to find the path with the range of 533% until 1700% shorter compared to A* algorithm.

Item Type:	Thesis (Undergraduate)
Uncontrolled Keywords:	Pathfinding, Pencarian Jalur Terpendek
Subjects:	Q Science > Q Science (General) > Q334-342 Computer science. Artificial intelligence. Algorithms. Robotics. Automation.
Divisions:	09-Faculty of Computer Science > 55201-Informatics (S1)
Depositing User:	Users 5418 not found.
Date Deposited:	09 Mar 2020 07:56
Last Modified:	09 Mar 2020 07:56
URI:	http://repository.unsri.ac.id/id/eprint/28032

Actions (login required)

View Item