Rabu, 29 April 2015

Artificial Intelligence pada Game

Game AI adalah aplikasi untuk memodelkan karakter yang terlibat dalam permainan baik sebagai lawan, ataupun karakter pendukung yang merupakan bagian dari permainan tetapi tidak ikut bermain (NPC = Non Playable Character). Peranan kecerdasan buatan dalam hal interaksi pemain dengan permainan adalah pada penggunaan interaksi yang bersifat alami yaitu yang biasa digunakan menusia untuk berinteraksi dengan sesama manusia. Contoh media interaksi ialah:

  • Penglihatan (vision)
  • Suara (voice), ucapan (speech)
  • Gerakan anggota badan ( gesture)


Untuk pembentukan Artificial Intelligence pada game ternyata digunakan pula algoritma, yaitu jenis pohon n-ary untuk suatu struktur. Implementasi pohon (tree) ini biasa disebut game tree. Berdasarkan game tree inilah sebuah game disusun algoritma kecerdasan buatannya. Artificial intellegence yang disematkan dalam sebuah game yang membentuk analisis game tree biasanya merepresentasikan kondisi atau posisi permainan dari game sebagai suatu node, dan merepresentasikan langkah yang mungkin dilakukan sebagai sisi berarah yang menghubungkan node kondisi tersebut ke anak (child) sebagaimana representasi suatu pohon (tree).

Namun, biasanya representasi langsung tersebut mempunyai kelemahan, yaitu representasi data pohon akan menjadi sangat lebar dan banyak. Mungkin bagi sebuah mesin komputer mampu melakukan kalkulasi sebanyak apapun masalah, namun game tree yang lebar dan besar memberikan beberapa masalah, antara lain konsumsi proses memori, kapasitas penyimpanan yang cukup besar dan kinerja yang kurang pada konsol game berspesifikasi rendah. Karena itu dibentuklah beberapa algoritma dan penyederhanaan bagi sebuah game tree.

Pada salah satu contoh game klasik, yaitu tic tac toe, penyederhanaan dapat dilakukan dengan berbagai metode. Salah satu diantaranya adalah minimax. Metode ini berhasil diterapkan dan memberikan nilai reduksi yang cukup signifikan. Dan tidak hanya bisa digunakan secara monoton, minimax juga bisa digunakan untuk game-game yang lebih rumit seperti catur, tentunya dengan algoritma dan representasi berbeda.

Minimax yang merupakan salah satu metode penerapan (implementasi) pohon n-ary pada suatu game, menandakan bahwa implementasi struktur (pohon khusunya) sangatlah diperlukan pada pembuatan dan penerapan Artificial Intelligence, dan tidak menutup kemungkinan ilmu dan metode baru yang lebih canggih akan ditemukan di masa depan.

Mengetahui bagaimana untuk mendapatkan dari titik A ke titik B adalah sesuatu yang banyak game membutuhkan. Apakah Anda sedang merancang sebuah turn-based dalam taktik strategi RPG atau permainan puzzle sederhana, navigasi dunia permainan Anda sering membutuhkan kecerdasan lebih dari karakter permainan Anda dari sekedar menunjuk ke arah tujuan dan bergerak dalam garis lurus.
Anda tidak ingin unit dalam permainan Anda berjalan melalui dinding. Pemain juga akan mengizinkan unit untuk bertemu dinding dan terjebak ketika jalan di sekitar hambatan terlihat jelas. Tidak ada yang lebih frustrasi daripada unit waktu nyata strategi permainan tidak mampu untuk membuat jalan mereka ke lokasi target.

Di sinilah algoritma pathfinding datang. Perintis adalah blok bangunan dasar dari sebagian besar permainan AI (kecerdasan buatan), dan dengan sedikit bantuan dari kode yang tepat permainan Anda akan jauh lebih pintar untuk itu.

Untuk sampai ke tujuan mereka, entitas permainan Anda mungkin harus berjalan sekitar hambatan, menemukan jalan mereka meskipun labirin penjara atau berkeliling jalan-jalan kota. Hal ini tidak cukup untuk akhirnya tiba di tempat tujuan melalui beberapa jalur putus asa memutar - rute yang mereka ambil harus mungkin rute terpendek.
Memecahkan masalah ini bukan tugas sepele, tapi itu adalah layak usaha. Musuh yang memilih dengan bijak sering dapat muncul hampir cerdas. Pemain Anda akan menghargai bahwa hal "hanya bekerja" dan akan dapat fokus pada strategi dan taktik bukannya mencemaskan memiliki mengasuh rusak AI.

Metode standar yang mayoritas game digunakan untuk merintis jalan disebut A *, yang diucapkan "bintang".

Asal Usul Perintis AI: Algoritma Dijkstra

Pada tahun lima puluhan, seorang ahli matematika bernama Edsger Dijkstra bekerja metode untuk menghitung rute yang efisien yang dapat diterapkan untuk setiap situasi hypethetical membutuhkan pilihan otomatis antara banyak langkah mungkin.

Hal ini sering digunakan dalam contoh truk pergi dari stop untuk menghentikan jarak jauh, ketika pengiriman harus dijemput dari berbagai lokasi di sepanjang jalan. Memilih rute yang paling efisien akan menghemat uang.


Animasi di atas adalah contoh khas dalam tindakan. Perhatikan bahwa setiap node tidak diatur pada grid permainan seperti tapi bisa jika kita ingin. Ini adalah contoh sempurna dari apa yang ingin kita lakukan: kita menambahkan "biaya" dari setiap rute dan memilih salah satu yang biaya sedikit. Biaya, dalam hal permainan merintis jalan, adalah jarak yang ditempuh.

Jika Anda menonton animasi di atas, Anda akan melihat bahwa setiap kali kita sampai pada node baru di sepanjang jalan, kami menambahkan biaya setiap kemungkinan rute dari sana dan melanjutkan ke salah satu yang biaya sedikit.

Masalah Dengan Algoritma Dijkstra

Algoritma Dijkstra karya besar, tetapi memiliki kelemahan yang naif dilaksanakan - itu tidak menggunakan heuristik khusus untuk memilih calon yang paling mungkin pertama, sehingga solusinya hanya diketahui setelah setiap lokasi yang mungkin diuji.


Dalam animasi di atas, Anda dapat melihat bahwa setiap "sel" atau "node" dalam grafik sedang diuji. Tiba di hasil yang tepat, tetapi programmer komputer di Anda mungkin berpikir, "perlu dioptimalkan!"

A-Bintang merintis jalan untuk menyelamatkan!

Sebuah bintang adalah versi lebih cepat dan lebih efisien dari algoritma Dijkstra. WikiPedia mendefinisikan A-bintang sebagai "best-pertama, grafik algoritma pencarian yang menemukan jalur penerbangan setidaknya dari node awal yang diberikan ke satu node tujuan".

Dengan kata lain, A-bintang melintasi grafik simpul (koleksi poin dalam ruang yang terhubung) dan menemukan jalan yang biaya sedikit (adalah terpendek) tanpa harus mengunjungi setiap node tunggal di seluruh grafik. Dalam kasus videogame, ini "simpul grafik" adalah dunia permainan; peta unit kami bergerak di sekitar.


Dalam animasi di atas, Anda dapat melihat bahwa dunia game yang sama disajikan seperti yang terlihat pada contoh Dijkstra sebelumnya, tapi kali ini lebih sedikit node diperiksa. Hasil ini heuristik mengoptimalkan adalah bahwa fungsi akan berjalan lebih cepat. Dalam game, ini selalu preferrable.

Gamedevs Cinta Optimization

Dengan beberapa optimasi yang lebih, kita bisa berbuat lebih banyak lagi menebak dan karena itu melakukan perhitungan lebih sedikit. Dengan menetapkan bobot untuk node yang dikunjungi sepanjang jalan, kita bisa memprediksi arah kita harus mencoba berikutnya.
Apa yang kita maksud dengan ini, adalah bahwa dengan menggunakan beberapa heuristik yang lebih agresif, kita dapat memprediksi apa arah yang paling mungkin terbaik untuk memindahkan adalah dan mencobanya pertama.


Dalam animasi di atas kita melihat contoh yang sangat efisien algoritma Bintang-yang mencoba untuk menebak rute terbaik sepanjang jalan bukannya mulai dari awal setiap kali rute tersebut akan diblokir.Lebih geometri yang kompleks akan membuat ini kurang jelas, tapi secara keseluruhan Anda dapat melihat bahwa ini adalah cara yang baik untuk melanjutkan.

Ini adalah apa yang paling dibutuhkan game untuk musuh mereka AI. Kemampuan untuk menemukan rute terpendek dari titik A ke titik B, dan mesin permainan yang bisa menghitung ini cukup cepat untuk berjalan lancar.




sumber :
https://setiyanugroho.wordpress.com/2011/04/12/kecerdasan-buatan-dalam-game/
http://ori50persen.blogspot.com/2010/10/artificial-intelligence-pada-games.html
http://buildnewgames.com/astar/