Artificial Intellegent
Firdaus Hasan
1830511092
Teknik Informatika C
Universitas Muhammadiyah Sukabumi
Uninformed Search (Pencarian Tanpa Informasi)
Breadth First Search (BFS)
1. Pengertian
Breadth-first search adalah algoritma yang melakukan pencarian secara melebar yang mengunjungi simpul secara preorder yaitu mengunjungi suatu simpul kemudian mengunjungi semua simpul yang bertetangga dengan simpul tersebut terlebih dahulu. Selanjutnya, simpul yang belum dikunjungi dan bertetangga dengan simpulsimpul yang tadi dikunjungi , demikian seterusnya. Jika graf berbentuk pohon berakar, maka semua simpul pada aras d dikunjungi lebih dahulu sebelum simpul-simpul pad aras d+1.
Algoritma ini memerlukan sebuah antrian q untuk menyimpan simpul yang telah dikunjungi. Simpulsimpul ini diperlukan sebagai acuan untuk mengunjungi simpul-simpul yang bertetanggaan dengannya. Tiap simpul yang telah dikunjungu masuk ke dalam antrian hanya satu kali. Algoritma ini juga membutuhkan table Boolean untuk menyimpan simpul yang te lah dikunjungi sehingga tidak ada simpul yang dikunjungi lebih dari satu kali. Dalam algoritma BFS, simpul anak yang telah dikunjungi disimpan dalam suatu antrian. Antrian ini digunakan untuk mengacu simpul-simpul yang bertetangga dengannya yang akan dikunjungi kemudian sesuai urutan pengantrian.
2. Contoh Masalah
OPTIMASI ALGHORITMA BREADTH FIRST SEARCH PADA GAME ENGINE 3D THIRD
PERSON SHOOTER MAZE BERBASIS AGEN CERDAS ANDROID
2.1. Pendahuluan
Pada Penelitian ini peneliti akan berfokus mengenai Game Engine pada Player dan belum adanya penelitian yang membahas tema ini, pada Game Engine Third Person Shooter labirin, Bagaimana cara untuk menyelesaikan game ini yang menggunakan pola labirin, maka di butuhkan suatu agen cerdas Alghoritma Artifical Intelligece pencarian melebar pertama (Breadth First Search), untuk mempermudah pemain menyelesaikan misi, sehingga menantang pemain untuk menyelesaikan misi.
2.2. Landasan Teori
Algoritma ini menggunakan metode pencarian yang di mulai dengan akar (Level 0) ke level selanjutnya.Pencarian ini di lakukan dengan mencari pada semua node atau simpul yang mempunyai level atau tingkatan sama sampai mennetukan hasil akhir (Goal) pada level tersebut, bila tidak aka akan pindah ke level selanjutnya.
Langkah-Langkah Alghoritma Breadth First Search :
1. Masukkan node akar ke dalam Queue.
2. Ambil node awal Queue, lalu cek apakah node merupakan solusi.
3. Jika node merupakan solusi, pencarian selesai dan hasil di kembalikan.
4. Jika node untuk solusi , masukkan seluruh node anak ke dalam Queue.
5. Jika Queue kosong dan setiap node sudah di cek, pencarian selesai.
6. Jika Queue tidak kosong, ulangi pencarian mulai dari poin 2.
Algoritma Breadth First Search (BFS) ini menjadi metode pendekatan unntuk masalah yang akan di hadapi.
3. Hasil Penelitian dan Pembahasan
a. Analisa Alghoritma Breadth First Search pada Game Third Person Shotter (BFS)
Pada penjelasan di atas di atas dapat di simpulkan bahwa Alghoritma Breadth First Search, pencarian buta pada semua node pada level n dan di kunjungi terlebih dahulu sebelum mengunjungi node node pada level n+1. Pencarian di mulai dari node masuk ke node exit, kemudian berpindah ke level berikutnya, demikian pula dari kanan ke kiri hingga menemukan goal.
b. Finite State Machine
Kriteria yang ada di dalam Game Labirin Third Person Shooter Dengan Alghoritma Breadth First Search dapat dijelaskan pada Finite State Machine sebagai berikut :
c. Implementasi Pada Game Labirin Third Person Shooter dengan menggunakan Unity 3D
Listing Coding Alghoritma Breadth First Search pada Game Third Person Shooter
1. private void ProgressStepCycle(float speed){
2. if (m_CharacterController.velocity.sqrMagnitude > 0 && (m_Input.x != 0 || m_Input.y != 0))
{m_StepCycle += (m_CharacterController.velocity.magnitude + (speed*(m_IsWalking ? 1f: m_RunstepLenghten)))*Time.fixedDeltaTime;}
3. if (!(m_StepCycle > m_NextStep)){ return;}m_NextStep = m_StepCycle + m_StepInterval};
4. Private void bfs(int x, int z, int depth, floatjump, float previousHeight)
5. {int resistance=1;
6. if (depth >=0) {CheckTile (x,z).GetComponentInChildren(CheckIfClicked)().Selected();
7. if (x+1 < 25){CheckTile(x+1, z, depth, jump,previous Height);}
8. if (x-1 >= 0){CheckTile(x-1, z, depth, jump, previousHeight);}
9. if (z+1 <25) {CheckTile(x, z+1, depth, jump, previousHeight);}
10. if (z-1 >=0){
11. CheckTile(x, z-1, depth, jump,previousHeight);}}}
12. private void CheckTile(int x, int z, int depth,float jump, float previousHeight){
13. float tileHeight = tiles(x, z).GetComponent(TileDimensions)().height;float difference = tileHeight - previousHeight;
14. if (difference<0) difference *=-1;
15. if CheckTile(x, z). GetComponentInChildren.CheckIfClicked().occupied && difference(jump);{
16. int resistance = tiles(x, z).GetComponent(TileDimensions)().getResistance();
17. if (resistance<0) resistance =1;BFS(x, z,depth-resistance, jump, tileHeight);}}
4. Kesimpulan
Untuk keterangan gambar di atas yang pada bagian kiri adalah tanpa menggunakan alghoritma, sehingga dalam menyelesaikan permainan lebih lama, sedangkan dibandingkan dengan menggunakan Alghoritma Breadth First Search pada bagian kanan menunjukan bahwa Alghoritma Breadth First Search lebih cepat menyelesaikan permainan dibandingkan dengan tanpa menggunakan alghoritma, sehingga mempermudah pemain dalam menyelesaikan permainan game labirin thrid person shooter.
Daftar Pustaka
Astrid Novita Putri, "Optimasi Alghoritma Breadth First Search Pada Game Engine 3D Third Person Shooter Maze Berbasis Agen Cerdas Android", Jurnal Transformatika, Volume 14, Nomor 1, Juli 2016.
Santi I Gede, ”Penggunaan Metode Kecerdasan Runut Maju Dalam Memecahkan Permasalahan Game Labirin,” Jurnal Ilmu Komputer Volume 5 No 1-April 2012.
Stuart, Russel and Peter Norvig.,“ Artifical Inteligence A Modern Approach.“, 2 Edition.United States Of America Prentice Hall, 2005.
Sutojo,dkk, ”Kecerdasan Buatan”.Penerbit Andi, 2011.
Nasution Rahmad, “Penerapan Alghoritma Backtracking Pada Permainan Math Maze”, Jurnal Pelita Informatika Budi Darma, Volume VII, Nomor : 3, Agustus 2014.
Santi I Gede Astawa, ” Penggunaan Metode Kecerdasan Buatan Runut Maju Dalam Memecahkan Permasalahan Game Labirin”, Jurnal Ilmu Komputer-Volume 5- No.1-April 2012 Universitas Udaya.
Komentar
Posting Komentar