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/
