Implementasi Algoritma Modified Bi-Directional A* pada NPC untuk pencarian rute terpendek dan Algoritma Fisher-Yates Shuffle untuk pengacakan konten pada Game Finding Diamond

ABSTRAK

Iman kepada nabi dan rasul Allah, merupakan salah satu rukun iman yang keempat. Karena pentingnya iman kepada nabi dan rasul Allah maka keimanan ini harus dimiliki oleh setiap umat islam, salah satu jalan untuk bisa mengimani adanya nabi dan rasul Allah adalah dengan mengenali nama-nama mereka dan mempelajari kisah-kisah kehidupan mereka. Selain melalui pendidikan, ada media yang lebih modern untuk mengenalkan nabi dan rasul yaitu dengan game. Maka dari itu peneliti tergerak untuk menciptakan sebuah aplikasi game modern yang bertujuan untuk memperkenalkan nabi dan rasul dengan media permainan komputer.

Pada aplikasi game yang dibuat ada koin perak, koin emas dan berlian yang harus dikumpulkan player. Khusus untuk setiap koin emas yang diambil, akan ditampilkan satu pengetahuan tentang nabi dan rasul yang telah diacak urutannya menggunakan algoritma Fisher-Yates Shuffle. Sehingga pengetahuan yang ditampilkan kelihatan lebih bervariasi dan setiap koin emas pasti menampilkan materi pengetahuan yang berbeda. Tetapi jika hanya menggunakan fitur random di unity game engine ada kemungkinan satu konten yang sama akan di tampilkan beberapa kali dalam satu permainan.

Pada game ini ada dua karakter NPC yaitu NPC Enemy dan NPC Army. NPC Enemy perilakunya adalah selalu mengejar player. Sedangkan NPC Army mengimplementasikan algoritma Modified Bi-Directional A*, untuk mengambil semua koin perak di arena permainan, sehingga pergerakannya lebih efektif, karena NPC Army bergerak menuju target sesuai dengan rute terpendek yang dihasilkan oleh algoritma tersebut. Berdasarkan hasil uji coba pada penelitian ini algoritma Modified Bi-Directional A* membangkitkan lebih sedikit node daripada algoritma A* sehingga memori yang digunakan lebih kecil dan waktu untuk menemukan rute terpendek lebih cepat.

ABSTRACT

Faith in the prophets and messengers of Allah, is one of the four pillars of faith. Because of the importance of faith in God's prophets and messengers so this faith must be owned by all the people of Islam, one of the ways to be able to believe in the prophets and messengers of Allah is to recognize their names and learn the stories of their lives. In addition through education, there are more modern media to introduce the prophets and messengers are with the game. Thus the researchers moved to create a modern game app that aims to introduce the prophets and messengers with media computer games.

In gaming applications was created there are silver coins, gold coins and diamonds to be collected by player. For each gold coin is taken, will be shown the knowledge of the prophets and messengers who had been randomized sequence using the Fisher-Yates Shuffle algorithm. So that the knowledge displayed look more varied and each gold coin will definitely display material different knowledge. But if only using the random feature in Unity game engine is likely the same content will be displayed several times in one game.

In this game there are two characters of NPC, there is NPC Enemy and NPC Army. NPC Enemy behavior is always pursuing player. While NPC Army implements Modified Bi-Directional A* algorithm, to take all the silver coins in the game arena, so that movement is more effective, because the NPC Army move towards the target in accordance with the route that is generated by the algorithm. Based on trial results on this study Modified Bi-Directional A* algorithm generate fewer nodes than A * algorithm so that the memory used is smaller and the time to find the shortest route more quickly