KECERDASAN BUATAN (AI) UNTUK MEMBANGKITKAN OBJECT 3D DENGAN ALGORITMA BSP

Seminar Nasional Universitas Negeri Malang Fakultas Teknik Elektro Universitas Negeri Malang

KECERDASAN BUATAN (AI) UNTUK MEMBANGKITKAN OBJECT 3D DENGAN ALGORITMA BSP Edy Prabowo Atanasius1) Supeno Mardi SN2) Moch.Hariadi3) 1,2,3

Pasca Sarjana Jaringan Cerdas Multimedia (Game Teknologi) Teknik Elektro,Teknologi Industri ITS Jurusan Teknik Elektro, Fakultas Teknologi Industri ITS Jl. Keputih Sukolilo,Surabaya, 60111 E-mail : [email protected] 1),[email protected]), [email protected]

Abstrak. Perkembangan dunia kreatif industri menuntut adanya penciptaan inovasi dengan berbagai selera pasar yang bervariatif. Penumbuhan variatif game khususnya dalam teknologi game simulasi semakin menarik minat pencinta permainan digital.Perkembangan teknologi permainan pada saat ini lebih banyak mengarah pada teknik pengembangan game berbasis objek oriented dan algoritma yang mampu mendukung konsep game 3 Dimensi. Pengembangan Algoritma Binary Space Partition Tree (BSP Tree) adalah salah satu algoritma yang mampu mendukung kosep untuk object 3 Dimensi. Binary Space Partitioning(BSP) Tree adalah model struktur data yang digunakan untuk mempresentasikan sebuah iterasi (pengulangan) dari susunan pembagian n- dimensi ruang dalam bentuk sub-sub ruang yang lain. BSP Tree mengkonstruksi sebagian proses dimana sebuah sub ruang dan partisi (sekatannya) dari sembarang bidang ruang adalah saling beririsan dengan sub ruang yang ada didalamnya. Hasilnya adalah dua sub ruang yang baru yang dapat dilakukan partisi kembali dengan metode pengulangan. Hasil yang diharapkan adalah menyederhanakan proses pembangkitan object 3D dan meningkatkan kecepatan dengan menghemat alokasi memori pada sumber daya komputer. Katakunci : Object 3D, BSP, Dimensi Ruang, Iterasi.

1. Pendahuluan Perkembangan teknologi permainan pada saat ini lebih banyak mengarah pada teknik pengem-bangan game berbasis objek oriented dan algoritma yang mampu mendukung konsep game Dimensi. Pengembangan Algoritma Binary Space Partition Tree (BSP Tree) adalah salah satu algoritma yang mampu mendukung kosep untuk object 3 Dimensi. Object oriented programming merupakan teknik pemrograman yang memisahkan fungsi atau prosedur dalam bentuk object class yang berbeda. Pembedaan object class ini memungkinkan untuk memanfaatkan class guna digunakan kembali sebagai obejct class yang reusable. Teknik reusable class memungkinkan pula untuk melakukan kemudahan dalam pengembangan modul program yang baru. Hal ini tentunya akan dapat meningkatkan produktifitas dalam penciptaan dan peningkatan kualitas game sehingga dapat mendorong kreatif industri. Perkembangan dunia kreatif industri menuntut adanya penciptaan inovasi dengan berbagai selera pasar yang bervariatif. Penumbuhan variatif game khususnya dalam teknologi game simulasi semakin menarik minat pencinta permainan digital. Permainan digital berbentuk simulasi khususnya yang memiliki genre Game Strategi memiliki peminat yang sangat besar. Warcraft dan Strarcraft adalah kedua jenis game bergenre

Strategi yang bersifat komersial dan memiliki tingkat penjualan mencapai lebih dari 10 juta copy. Hal ini mengindikasikan bahwa game dengan genre Strategi sangat diminati oleh para pencinta permainan digital. Permainan digital yang bergenre Strategi pada umumnya memiliki bentuk seperti simulasi. Simulasi yang sering digunakan adalah simulasi strategi perang, simulasi strategi pembangunan suatu kota dan masih banyk bentuk lainnya. Simulasi strategi perang paling mendominasi dalam bentuk game Strategi permainan. War Tank Strategy juga merupakan salah satu simulasi game strategi perang yang banyak dimainkan bahkan telah banyak pula dikembangkan dalam kompetesi pemrograman. Kompetisi pemrograman war Tank Strategy tersebut meliputi pengembangan AI dan Obejct Oriented Programmingnya(OOP). Pengembangan OOP dapat menggunakan berbagai bahasa pemrograman yang memungkinkan misalnya lingkungan pemrograman C++ termasuk Visual C++, lingkungan pemrograman JAVA dan sebagainya. Selain itu, juga dimungkinkan untuk pengembangan game dengan menggunakan Game Engine. Pemanfaatan game engine juga memberikan kemudahan dalam membangun suatu pengembangan game baru. Game engine ada yang bersifat open source seperti Boss Tank War Strategy, Open Real Time Strategy(ORTS), Ogre dan lain sebagainya. Dukungan Open Source memungkinkan untuk melakukan reusable dari modul OOP Class yang telah tersedia. Pada umumnya fasilitas yang tersedia Class dalam lingkup open source masih terbatas. Pengembangan Game dengan game engine komersial lebih memungkinakan untuk menemukan object class yang lebih banyak, namun demikian harus dibeli dengan harga tertentu. Pengembangan dengan menggunakan bahasa pemrograman yang mendukung OOP tentu akan lebih memberikan keleluasaan dalam membuat desain sendiri. Dalam penulisan hasil laporan ini, penulis mencoba untuk memanfaatkan fasilitas dalam lingkungan bahasa pemrograman C++ khususnya Visual C++ untuk mengembangan game berbasis OOP. OOP Game yang dikembangkan adalah mengenai simulasi perang game dengan nuansa peperangan tank Pengembangan yang dilakukan adalah mendesain Class Object Tank dan menyusun skenario serta algoritmanya dengan metode Algoritma BSP Tree, guna membangun suatu simulasi permainan digital yang bertemakan ”Game Strategi Perang Tank pada Visual C++”. 2. Tujuan Pengembangan desain pemrograman game ini tertujuan untuk : 1. menerapkan konsep algoritma BSP Tree dalam Game 3 Dimensi 2. menerapkan konsep FSM dalam simulasi perang tank 3. Maksud Pengembangan desain pemrograman game ini bermaksud untuk : 1. mengimplementasikan algoritma BSP Tree dalam Game 3 Dimensi dalam Visual C++ 2. membangun simulasi game strategi perang tank 4. Landasan Teori Konsep Algortima BSP Tree Binary Space Partitioin Trees(BSP Tree) pertama kali diperkenalkan oleh Fuchs, Kedem dan Naylor sekitar tahun 1980. Ketiganya mulai memperkenalkan BSP Tree dengan mempublikasikan dua paper mengenai BSP Tree ini yaitu “Predeterming Visibility Priority in 3-D Scenes” dan “ On VisibleSurface Generatoin by A Priori Tree

Structures” kedua paper ini membahas mengenai BSP Tree dan bagaimana menggunakannya. Binary Space Partitioning(BSP) Tree adalah model struktur data yang digunakan untuk mempresentasikan sebuah iterasi(pengulangan) dari susunan pembagian n- dimensi ruang dalam bentuk sub-sub ruang yang lain. BSP Tree mengkonstruksi sebagian proses dimana sebuah sub ruang dan partisi(sekatannya) dari sembarang bidang ruang adalah saling beririsan dengan sub ruang yang ada didalamnya. Hasilnya adalah dua sub ruang yang baru yang dapat dilakukan partisi kembali dengan metode pengulangan. Algoritma BSP Tree Proses untuk membangun BSP Tree adalah sebagai berikut : 1. Pertama pilih partisi dari permukaan bidang yang akan menjadi node(simpul root 2. partisi (sekatan) dari semua banyak garis yang merupakan inisialisasi dari banyak bidang disimpan dalam daftar kemungkinan garis yang ada dengan membedakan garis baian depan atau belakang 3. lakukan proses yang berulang(iterasi) untuk keseluruhan dari banyak garis yang ada dari posisi depan atau belakang , untuk membuat node(simpul) tree yang baru dan menambahkannya sebagai simpul child yang baru dari simpul parentnya. . Banyak bidang dalam n-ruang dimensi adalah suatu objek n-1 dari ruang dimensi yang dapat digunakan untk membagi ruang dalam dua ruang. Sebagai contoh jika dalam ruang 3 Dimensi banyak objek n-1 adalah bidang dan dalam ruang 2 dimensi objeknya adalah garis. Ilustrasinya adalah sebagai berikut : Dalam bangun ruang 3 Dimensi : Andaikan ada sebuah kubus dengan 6 bidang datar yang sama dan sebangun, maka ke-6 bidang datar tersebut akan membentuk sebuah ruang kubus yang besar misalkan disebut sebagai ruang A disebut sebagai simpul(root) parent. Jika ruang kubus A dilakukan partisi dengan membagi ruang kubus A sama besar bagiannya menjadi partisi (sekatan) ruang yang baru misalkan ruang itu adalah ruang B dan C, maka ruang B dan C adalah bagian dari simpul (node) child dari simpul (node) parent A. Perhatikan Ruang Sekatan B (simpul child B). Jika Ruang B dibagi dua ruang(partisi) yang baru dengan besar yang sama misalkan partisi D dan parisi E yang kemudian disebut sebagai simpul D dan E, maka ruang partisi B dengan simpul B akan menjadi simpul(node) parent dari simpul(node) B dan C dimana simpul B dan C disebut sebagai simpul child. Perhatikan gambar dibawah ini !

Gambar 1 Struktur Logika Algoritma BSP 3 Dimensi

Sehingga apabila diperhatikan maka dalam ruang 3 dimensi setiap sekatan dari ruang bidang akan menjadi permukaan bidang yang baru yang akan saling beririsan dengan bidang ruang yang lain dan kan saling berhadapan sebagai bidang depan atau bidang belakang dimana hasil dari pembedaan ruang sekatan bidang depan dan belakang akan disimpan sebagai daftar dari kumpulan simpul BSP Tree hasil dari iterasi (pengulangan) metoda pembagian ruang sekatan menjadi bidang-bidang sekatan yang baru. Dengan menggunakan konsep yang sama BSP Tree dapat diterapkan dalam bidang 2 dimensi. Perhatikan ilustrasi dibawah ini :

Gambar 2. Struktur Logik Algoritma BSP 2 Dimensi Sebuah bidang datar A mempunyai 4 empat sisi berupa garis yang membentuk suatu arena bidang datar segiempat. Bidang datar ini disebut sebagai simpul (node) parent A. Jika simpul A dibagi menjadi 2 bagian yang sama besar oelh suatu garis baru yang disebut simpul X maka akan terdapat 2 sekatan baru yaitu bidang datar B dan Bidang datar C dimana simpul B dan Simpul C merupakan simpul child dari simpul parent X (yang berupa garis). Jika bidang datar B dibagi menjadi 2 oleh garis Y yang disebut sebagai sub simpul parent yang baru maka akan terdapat dua sekatan bidang datar yang baru yaitu bidang datar D dan bidang E yang menjadi sub simpul child D dan sub simpul child E dari sub simpul parent Y. Proses ini dapat dilanjutkan dengan proses iterasi berikutnya. Secara konsep maka Algoritma mengenai BSP Tree dapat dituliskan dalam alur logika program sebagai berikut Pseudo Code : void

Enumerate (BSP_tree *tree) { Stack stack; while (tree) { if (tree->back) stack.Push (tree->back); if (tree->front) stack.Push (tree->front); tree = stack.Pop (); } }

5. Membuat deskripsi logik alur game dengan menggunakan FSM FSM di gambarkan sebagai jaringan semantic yang merepresentasikan maksud dan hubungan dengan menggunakan kata. Bulatan merepresentasikan state, sedangkan anak panah merepresentasikan transisi state. Pada semua sistem berbasis aturan (Rule Based System), jika kondisi syarat untuk aturan (rule) tertentu terpenuhi maka aturan itu

akan dilaksanakan. Tidak memungkinkan untuk terjadi beberapa aturan dilaksanakan sekaligus. FSM bekerja berdasarkan urut-urutan dengan keadaan ( state) tertentu dan hanya ada sebuah state transition aja yang terjadi antara state saat ini dengan state berikutnya. Cara termudah untuk mengimplementasikan finite state machine adalah dengan menggunakan pengatur yang berfungsi sebagai kotak saklar. Ketika eksekusi thread dijalankan pada FSM, maka akan ditujukan pada pengatur yang mengevaluasi atau menentukan state saat ini (current state). Biasanya menggunakan switch(case) statement atau if-then-else statement. Ketika suatu state telah ditentukan, maka kode program untuk state tersebut akan dieksekusi. Sebuah contoh; mayoritas entitas obyek game dipengaruhi oleh faktor terluka. luka dapat ditimbulkan dari banyak hal seperti proyektil roket misalnya. ketika trigger luka ditransmisikan ke entitas lain, pointer fungsi sakit entitas itu akan dipanggil, yang kemudian mentriger sebuah transisi state yang mempengaruhi entitas menjadi state mati atau state menyerang. Garis besar: luka yang timbul adalah sebuah input bagi FSM, yang mana bisa berfungsi sebagai triger untuk sebuah transisi state. Hanya ada sebuah transisi state dari state saat ini (current state) yang dilaksanakan, jadi strategi resolusi konflik yang persistant diperlukan untuk memilih salah satu dari transisi state yang dilaksanakan yang kemudian mengakibatkan perubahan state.

Finite State Machine (FSM) Perang Tank

Gambar 3. FSM Object 3D 6. Membuat desain UML OOP Game Tank Penentuan Object-object Game Tank ditentukan dengan melakukan analisis perancangan menggunakan konsep diagram UML. Konsep desain UML akan memudahkan rancangan dalam menentukan Class dalam object untuk diterjemahkan dalam penerapan pengkodingannya. Desain UML yang dirancang adalah sebagai berikut :

Gambar 4. UML Object 3D

7. Menentukan bahasa pemrograman dan engine library grafis game Persiapan untuk melakukan implementasi program simulasi game tank ini dilakukan dengan penentuan Framework yang akan digunakan untuk pengkodingan. Pertimbangan utama adalah dipilih bahasa pemrograman yang mampu untuk menerapkan Object Oriented Programming (OOP) Penentuan bahasa pemrograman yang dipilih adalah C++ dengan lingkungan IDE Visual C++ dengan memanfaatkan objek library grafis yaitu openGL dan DirectX 9.0 8. Mengimplementasikan dalam pengkodean Visual C++ a. Implementasi Desain Class Object Pada saat awal player mengaktifkan permainan maka posisi awal unti NPC telah tersedia di arena windwos permaianan. Arena windows permainan dibangun dengan menggunakan object Terrain dengan memanfaatkan engine Maping yang tersedia. Unit NPC yang ada dibangun dengan Class menunggu. Class menunggu pada awalnya akan dibangun dengan state yang lain yaitu bergerak dan mencari. Alur logik FSM state awal ini adalah sebagai berikut :

Gambar 5. FSM awal State menunggu

Class menunggu() menampilkan posisi awal dari setiap object dari unit NPC player. Tampilan dari posisi awal unit NPC adalah sebagai berikut:

Gambar 6. Object Rendering 3D b. Implementasi Desain Class Object Menyerang Pada saat awal player mengaktifkan penempatan NPC maka posisi awal unti NPC telah tersedia di arena windwos permainan. Arena windows permainan dibangun dengan menggunakan object Terrain dengan memanfaatkan engine Maping yang tersedia. Unit NPC menyerang yang ada dibangun dengan Class menyerang. Class menyerang pada awalnya akan dibangun dengan state yang lain yaitu menunggu dan mencari. Alur logik FSM state awal ini adalah sebagai berikut :

Gambar 7. FSM Sate mencari- menyerang

c. Implementasi Desain Class Object mati Pada saat awal player mengaktifkan penempatan NPC maka posisi NPC musuh telah tersedia di arena windwos permainan. Unit NPC musuh menyerang dibangun dengan Class menyerang. Class menyerang akan dibangun dengan state yang lain yaitu menunggu dan mati. Alur logik FSM state awal ini adalah sebagai berikut :

Gambar 8. FSM Sate menyerang-mati

9. Kesimpulan Abstraksi Object melalui UML dan FSM yang telah digambarkan secara umum dapat diterapkan disegala jenis game komputer. Abstraksi ini memudahkan kita untuk melakukan desain ulang(Reusable) pada kerangka kerja permasalahan pengembangan tingkatan game berikutnya. Penggunaan Modeling digunakan untuk analisis dan simulasi yang memungkinkan pada setiap tahapan pengembangan. Implementasi dari rancangan FSM dapat digunakan engine game atau bahasa pemrograman yang bersifat Object Oriented Modular yang dapat dikompilasi misalkan dengan C++. Jadi, ModelBased Design pada game tidak lagi harus dibuat dengan detail pengko-dean yang rumit pada tingkat bawah(low machine) tetapi dapat dirancang dengan menggunakan abstraksi tingkat tinggi higher-level.