Muhammad Alif Samudra, 4611418034 (2022) KOMPARASI PENCARIAN RUTE NON-PLAYABLE CHARACTER MENGGUNAKAN ALGORITMA A* DAN D* PADA SIMULASI VIDEO GAME. Under Graduates thesis, Universitas Negeri Semarang.

PDF - Published Version Restricted to Repository staff only Download (3MB) | Request a copy

Abstract

Permainan video (video game) merupakan sebuah sistem dimana pemain terlibat dalam sebuah konflik buatan yang didefinisikan oleh aturan-aturan yang menghasilkan hasil yang terukur. Video game membutuhkan banyak sistem yang kompleks dan terkoneksi untuk menunjang simulasi dunia lain sebagai nilai hiburan yang difokuskan. Salah satu nya yaitu sistem pencarian rute (pathfinding) Non�Playable Character (NPC). Algoritma A* pathfinding dan variasi perkembangannya merupakan metode yang paling banyak digunakan pada video game. Namun hasil pathfinding menggunakan algoritma A* hanya efektif untuk keadaan dengan halangan yang statis. Algoritma pathfinding D* memiliki solusi untuk keadaan dengan halangan yang dinamis seperti dalam sebuah video game, yaitu dengan proses Path Replanning. Karena itu, dengan fungsi pencarian heuristik dan proses Path Replanning yang dimiliki algoritma D*, algoritma tersebut cocok digunakan pada area dengan keadaan halangan yang dinamis. Penelitian ini bertujuan untuk menentukan algoritma apa yang lebih baik antara algoritma A* dan D* dalam lingkungan dengan halangan dinamis. Hasil penelitian menunjukan bahwa algoritma A* tetap memiliki kecepatan pencarian rute yang lebih cepat dibanding algoritma D* pada lingkungan tanpa halangan dinamis. Didapatkan selisih perbedaan waktu tempuh mencapai 6-8% antara algoritma A* dan D*. Namun jika pada lingkungan dengan halangan dinamis, algoritma A* tidak dapat menanggulangi hal tersebut pada semua kasus simulasi lingkungan dan terjadi error, sementara algoritma D* dapat menanggulangi halangan dinamis tersebut dengan selisih waktu tempuh mencapai 8-30% jika dibandingkan antara lingkungan tanpa halangan dinamis dan dengan halangan dinamis.

Actions (login required)

View Item