Pertemuan 4 -Teknologi Game | Visibilitas

Nama    : Kareem Abdul Jabbar

NPM     : 53418591

Kelas    : 3IA15

Visibilitas

Algoritma Portal Sel

Identifikasi portal yang bisa dilihat. Portal menghubungkan dua sel yang terputus. User akan mengidentifikasi bagaimana caranya agar bisa menggunakan portal untuk visibilitas yang efisien. 

Potentially Visible Cells

Generating :

Untuk dua sel mana saja, cari tahu apakah objek terlihat dan Oculuders

Tradeoffs :

• Penyimpanan
• Komputasi
• Agresif atau Konservatif

Algortihms for Combining Occluders

- Oklusi Horizons berfungsi untuk adegan 2.5.

Bagus untuk kota dan sejenisnya dan ada ekstensi untuk pemandangan 3D yang relatif sederhana seperti jembatan

- Green’s Hierarchical Z-Buffer membangun okluder dan menguji oklusi diruang layar

Membutuhkan perangkat keras khusus atau perender perangkat lunak

Zhang et.al.

Peta Oklusi Hierarki merender okluder menjadi peta tekstur kemudian membandingkan objek kepeta.

• Menggunakan perangkat keras yang ada tetapi membayar untuk operasi pembuatan tekstur disetiap bingkai.
• Memungkinkan perkiraan visibilitas jika diinginkan (Terkadang tidak menggambar hal-hal yang seharusnya)

Schaufler et.al.

Occluder Fusion membangun struktur data spasial dari wilayah yang tersumbat

Problems

Metode ini sebagian besar berfungsi untuk didalam ruangan dan terdapat pemandangan alam, yaitu lahan dan hutan (Tidak dapat menemukan okluders yang bagus)

Slight Digression

Level of Detail (LOD)

Memiliki beberapa representasi dari objek yang sama dan menggambar dari yang paling sederhana yang bisa user lakukan

Terrain

Hal yang terpenting untuk banyak game dan sebagai model, ukurannya sangat besar. Membuat setiap titik secara eksplisit dengan tangan terdapat tidak memungkinkan sehingga metode pembuatan medan otomatis adalah umum. Saat rendering, beberapa medan mendekat dan bagian lain menjauh yang mengarah ke algoritma LOD medan

Representing Terrain

Representasi dasar untuk medan biasanya berupa bidang ketinggian

•     z = f (x, y) untuk (x, y) dalam batas spasi
•     Menghindari hal-hal seperti goa dan overhang yang harus dirawat secara khusus

Ada dua cara umum untuk merepresentasikan fungsi f(x, y) :

Simpan secara eksplisit nilai f(x, y) untuk grid diskrit lokasi (x, y)

•          Umumnya interpolasi (Bilinear) atau triangulasi untuk mendapatkan poin yang tidak ada digrid
•         Mudah untuk mengetahui berapa ketinggian medan pada suatu nilai (x, y)
•         Mahal untuk menyimpan seluruh medan.

Penggabungan

Diamond merupakan calon gabungan jika anak anggotanya masuk dalam triangulasi. Salah satu cara penggabungan diamond adalah cari orang tua dari simpul daun saudara yang merupakan tetangga dasar atau tidak memiliki tetangga dasar. Kemudian mengurangi jumlah segitiga.

Algoritma Penyempitan LOD

Dimulai dengan jaringan dasar. Pisahkan segitiga berulang kali sampai selesai. Berhenti ketika hitungan segitiga tertentu tercapai atau berhenti ketika kesalahan kurang dari jumlah tertentu. Untuk memandu urutan pemisahan, tetapkan prioritas untuk setiap pemisahan dan selalu lakukan yang memiliki prioritas tertinggi. Setelah tahap pemisahan, perbarui prioritas segitiga yang terpengaruh.

Prioritas sampel : Prioritas tinggi pada pemisahan yang akan mengurangi kesalahan besar.

User akan memeriksa apakah algoritma sudah dinyatakan kompleks. Algoritme serupa bekerja dengan menyederhanakan mesh melalui operasi penggabungan.

Catatan Perbaikan

Jika prioritasnya monoton, maka medan yang dihasilkan optimal.

Monotonik : Prioritas anak-anak tidak lebih besar dari prioritas orang tua mereka.

Prioritas dapat berasal dari banyak sumber :

Didalam atau diluar pandangan, siluet, kesalahan yang diproyeksikan, dibawah kendaraan dan garis pandang.

Tidak memanfaatkan koherensi :

Saat tampilan bergerak diatas medan, triangulasi cenderung tidak banyak berubah.

User harus bisa memulai dengan triangulasi yang ada dan memodifikasinya untuk menghasilkan triangulasi baru yang optimal.

Kesalahan Metriks yang Diproyeksikan

Idenya adalah untuk mengetahui seberapa jauh urutan penggabungan memindahkan medan dari lokasi aslinya yang benar. Diukur dalam ruang layar, yang dilihat oleh penonton.

Mulailah dengan batas-batas diruang dunia, kemudian proyeksikan batas-batas tersebut pada saat run-time. Batas ruang dunia terlihat independen dan batas ruang layar yang diproyeksikan bergantung pada tampilan.

Performance Bottlenecks

•  Menyimpan dan mengelola prioritas untuk segitiga yang tidak terlihat hanya membuang-buang waktu. Lakukan pemusnahan frustum standar untuk mengidentifikasi mereka. 
• Mengirim segitiga individu itu boros. Sebaiknya buat strip saat segitiga dipisahkan dan digabungkan.
• Secara naif disetiap frame, pernikahan harus diproyeksikan, prioritas baru dihitung dan antrian diurutkan ulang. Gunakan kecepatan pemirsa untuk mengikat jumlah bingkai sebelum sebuah prioritas bisa mencapai puncak tumpukan dan tunda penghitungan ulang sampai saat itu.
• Antrian prioritas : Prioritas bin untuk mengurangi biaya penyortiran
• Pada prioritas rendah, urutan didalam keranjang tidak menjadi masalah.

Peningkatan Tambahan

•             Hentikan pemrosesan setelah jangka waktu tertentu. Mudah untuk dilakukan, cukup hentikapemrosesan pemisahan atau penggabungan berikutnya. Hasilnya tidak lagi optimal, tapi mungkin tidak begitu buruk juga.
•            Biaya algoritma antrian ganda tergantung pada jumlah langkah yang diperlukan untuk mengubah satu mesh kemesh lainnya. Periksa sebelumnya berapa banyak langkah yang mungkin diperlukan dan jika mungkin, buat kembali mesh dari awal menggunakan algoritma perbaikan.
•            Dapat memperoleh ketinggian garis pandang atau dibawah kendaraan yang akurat dengan memanipulasi prioritas untuk memaksa pemisahan tertentu

Pertemuan 3 - Teknologi Game | Simulasi Berbasis Fisik

Nama       : Kareem Abdul Jabbar

NPM        : 53418591

Kelas       : 3IA15

Simulasi Berbasis Fisik

Suatu massa yang dihubungkan dengan pegas dan dapat digunakan untuk memodelkan :

·         Benda yang bisa berubah bentuk

·         Kain

·         Rambut

·         Tubuh yang kaku

Contoh konkrit :

·         Keadaan (Posisi dan Kecepatan)

·         Kekuatan (Gravitasi dan Pegas)

·         Integrasi

Collision/Tabrakan

Mendeteksi sebuah tabrakan :

Broad Phase :

·         Mencari tau kotak pembatas yang berpotongan

·         Meluas dan memendekkan

 

Narrow Phase :

·         Mencari tau apakah tabrakan sebenarnya ada

·         Pengujian titik potong dengan metode vertex / face, edge / face

Respon Tabrakan

·         Pegas tidak terlalu bagus untuk benda kaku

·         Abstrak sebagai jerat yang tidak berubah bentuk dengan menggunakan derajat kebebasan

Pertemuan 2 | Teknologi Game - Artificial Intelligence

Nama    : Kareem Abdul Jabbar

NPM    : 53418591

Kelas    : 3IA15 

    Artificial Intelligence (AI) adalah kontrol dari setiap entitas non-manusia dalam sebuah game. Contoh dari AI adalah mobil-mobilan dalam permainan mobil, musuh dan monster dalam game tembak-tembakan, unit pasukan user, unit musuh user dan musuh Anda dalam game RTS (Real Time Strategy). RTS adalah pengembangan dari game dengan genre strategi. Game dapat didefinisikan sebagai game RTS kalau memenuhi beberapa riteria seperti dapat memilih serta mengendalikan banyak unit dengan cara dragging and clicking, dapat menggerakkan unit untuk menguasai area penting sebagai contoh resource, dapat menyerang serta menghancurkan unit musuh. AI Biasanya tidak mengacu pada hal-hal pasif yang hanya bereaksi kepada pemain dan tidak pernah memulai tindakan, tetapi berdasarkan logika fisik atau permainan. Misalnya, balok di Tetris bukanlah AI dan bola juga tidak ada di dalam permainan yang user lakukan, juga tidak ada bendera yang tertiup angin. Ini merupakan perbedaan yang agak sewenang-wenang. 

    AI Berbasis peristiwa, digerakkan oleh peristiwa yang melakukan segalanya untuk menanggapi peristiwa didunia. Peristiwa dikirim melalui pesan (Pada dasarnya, sebuah fungsi dipanggil saat pesan tiba, seperti antarmuka pengguna). Contoh pesannya adalah jangka waktu tertentu telah berlalu jadi perbarui diri anda, anda telah mendengar suara dan seseorang telah memasuki bidang pandang anda. Pesan dapat sepenuhnya menggantikan penginderaan, tetapi biasanya tidak. Sistem nyata adalah campuran, sesuatu yang bisa berubah-ubah. Jadi user perlu melakukan beberapa penginderaan.

Tujuan Game Artificial Intelligence

• Didorong oleh tujuan. Artificial Intelligence sudah memutuskan apa yang harus dilakukannya dan  mencari cara untuk melakukannya.
• Reaktif. AI Segera merespons perubahan didunia.
• Karakteristik. Mewujudkan karakter yang konsisten dan dapat dipercaya.
• Pengembangan cepat dan mudah.

AI dalam game loop

    Artificial Intelligence didalam Game Loop diperbarui sebagai bagian dari Game Loop, setelah input pengguna dan sebelum rendering. Yang ditinjau dalam Game Loop adalah AI mana yang lebih didahulukan, apakah AI berjalan disetiap frame atau disinkronkan. 

 

AI dan Animasi

    Hubungannya antara AI dan animasi, AI menentukan apa yang harus dilakukan dan animasi yang melakukannya. AI Mendorong animasi, memutuskan tindakan apa yang harus dianimasikan oleh sistem animasi. AI Mengeluarkan perintah seperti perpindahan dari titik A ke B dan sistem akan melakukan animasi untuk melakukan sisa kerjanya. Skenario yang terbaik bergantung pada sifat AI sistem dan sifat sistem animasi. Apakah sistem animasi berdasarkan pohon bergerak (Motion capture) atau physics atau apakah AI menjaga penghindaran tabrakan dan apakah itu rinci perencanaan.

 

AI menurut Polling

• AI dipanggil dengan jangka yang ditentukan.
• “Sensing” : AI mencari apa yang berubah di dunianya. Singkatnya :
• Mendata apa yang bisa dilihat
• Memeriksa apakah animasinya sudah selesai berjalan
• Kemudian beraksi berdasarkan data yang didapat.

Kompleksitas Spesifikasi

• Seberapa sulit untuk menulis kode
• Menentukan biaya pengembangan dan risiko
• Semakin banyak pengetahuan yang ditambahkan, berapa banyak lagi kode yang perlu ditambahkan

Dua Ukuran Kompleksitas

• Menentukan biaya run-time AI
• Seberapa cepat program berjalan karena lebih banyak pengetahuan ditambahkan
• Berapa banyak memori yang dibutuhkan karena lebih banyak pengetahuan ditambahkan

Kelebihan FSM

• Sangat cepat, akses satu array.
• Cukup ekspresif untuk perilaku sederhana atau karakter yang dimaksudkan “bodoh”
• Bisa di-commpile menjadi struktur data yang compact.
• Memory dinamis : keadaan sekarang
• Memory statis : diagram keadaan, implementasi array
• Bisa membuat tools, sehingga non-programmer bisa membangun perilaku/behaviour.
• Non-deterministic FSM bisa membuat perilaku yang tidak terprediksi

Kelemahan FSM

• Jumlah keadaan bisa bertumbuh begitu cepat.
• Secara eksponensial dengan jumlah kejadian s=2e
• Jumlah cabang bisa tumbuh bahkan lebih cepat : a=s2
• Representasi proporsional
• Sulit untuk menaruh perintah “Ambil power-up yang lebih baik”, atau “serang musuh yang paling dekat”
• Berat untuk menghitung : Tunggu hingga kali ketiga melihat musuh, baru serang
• Memerlukan event tambahan : Kali pertama melihat, kali kedua, dst, dan keadaan tambahan untuk mengurus penghitungannya.

    Masalah dasar teknik AI dalam game, mengingat keadaan dunia, apa yang harus user bisa lakukan. Berbagai macam solusi dalam game antara lain mesin keadaan hingga, pohon keputusan, sistem berbasis aturan, jaringan saraf, logika fuzzy. Solusi yang lebih beragam di dunia akademis adalah sistem perencanaan yang kompleks, pemrograman logika, algoritma genetika, Bayes-nets. Biasanya terlalu lambat untuk game. Bayes Network adalah suatu metode pemodelan data berbasis probabilitas yang merepresentasikan suatu himpuan variabel dan conditional interdependenciesnya melalui suatu DAG (Directed Acyclic Graph).