Selasa, 02 November 2010

ALGORITMA AI SEDERHANA: MEMBUAT MUSUH YANG BISA MENGEJAR PEMAIN bagian 1

Salah satu elemen yang membuat game menarik adalah tantangan. Tantangan bisa berupa goal, halangan atau musuh.

Dalam game Pacman misalnya, kita diberi tantangan berupa musuh yang bisa mengejar. Dalam game catur kita bisa bermain melawan komputer dan makin banyak saja game-game yang melibatkan komputer sebagai pemain bahkan dalam skala yang besar seperti pada game RTS dan game online.

Untuk menciptakan musuh yang bisa mengejar pemain seperti pada game pacman, dibutuhkan yang namanya AI atau Artificial Intelligence atau dalam bahasa Inggris disebut Kecerdasan Buatan, dalam bahasa Jawa AI bisa juga disebut dengan pinter gawean.

AI secara sederhana adalah kemampuan komputer untuk membuat pertimbangan dan mengambil keputusan. Dalam game pacman misalnya, kita bisa melihat bahwa para hantu memiliki kemampuan untuk membuat pertimbangan dan mengambil keputusan tentang langkah mana yang harus diambil agar tidak hanya bisa mengejar pacman tapi juga membuatnya terkepung. Walaupun kelihatan sederhana namun proses pembuatannya tidaklah sesederhana yang pernah anda bayangkan.

AI bukanlah hal mudah yang bisa dipelajari dalam waktu sehari atau semalam, atau bahkan sehari semalam bila digabungkanpun belum tentu cukup.

Satu hal yang perlu diingat dalam pemrograman AI adalah semakin tinggi kepandaian yang dimiliki oleh musuh/komputer, maka algoritma yang digunakan akan semakin sulit pula. Biasanya programmer pemula akan mengalami kegagalan dikarenakan mereka tidak mengetahui betapa rumitnya membuat sebuah AI bahkan yang paling sederhana sekalipun seperti pada game catur misalnya.

Disini saya berusaha menjelaskan tentang algoritma yang saya pakai pada game saya Pacmaze dan Battle City 3D (promosi mode on).

Algoritma ini hanya berlaku pada daerah yang sempit dimana satu jalur hanya bisa dilalui satu karakter saja, seperti pada game-game bertipe maze seperti pacman dan battle city. Untuk permainan dengan area yang lebar seperti pada game-game RTS maka kita akan butuh algoritma path find seperti A* Path Find atau yang lebih rumit lagi.

Pembahasan kali ini akan saya mulai dari yang paling sederhana hingga ke yang lebih rumit, dan tulisan ini juga akan saya bagi menjadi beberapa bagian seperti biasa supaya postingannya banyak dan saya bisa kejar target bulan ini :)

Algoritma I:
Algoritma ini mirip dengan algoritma yang dipakai dalam game Chips Challenge. Pada game Chips Challenge, Creature yang berbentuk kodok akan berusaha mengejar pemain. Namun kodok ini tidak terlalu pintar karena dia hanya berpikir untuk berjalan lurus saja, dan saat ada halangan dia tidak bisa apa-apa dan akhirnya dia hanya diam dan menunggu.











Pada gambar diatas, si creature tidak bisa mengejar pemain, walaupun sebenarnya dia bisa mengambil alternatif untuk bergerak ke kanan/kekiri agar bisa mengejar pemain.

Apa yang dipikirkan oleh sang kodok diatas dapat digambarkan dengan alur sebagai berikut:




Diagram diatas adalah diagaram yang paling sederhana untuk menentukan langkah musuh (kodok) untuk mengejar user. Gambar alurnya memang agak keluar dari aturan pembuatan algoritma, tapi hal ini dibuat semata-mata hanya untuk kemudahan saja.

Penjelasan alurnya sebagai berikut:
Pertama musuh akan mencari posisi pemain. Bila pemain ada di kanan maka musuh akan bergerak ke kanan. Sebelum bergerak kekanan, musuh akan mengecek dulu apakah dia bisa bergerak ke kanan atau tidak. Bila ada benda yang menghalangi misalnya tembok maka musuh tidak akan bisa bergerak kekanan dan memilih untuk diam.
[ai.png]
Bila pemain ada di sebelah kanan, musuh akan bergerak kekanan


Bila ada penghalang maka musuh tidak bisa bergerak.

Salah satu kelemahan dari algoritma ini adalah tidak ada inisiatif bagi musuh untuk mencari jalan alternatif bila ada halangan. Karena bila ada halangan maka langkah yang diambil adalah kembali lagi ke awal dan mencari posisi target. Langkah ini akan selalu diulangi sampai target berada pada posisi dimana musuh bisa mengejar.


Seharusnya musuh bisa memiliki alternatif jalan untuk mengejar pemain.

Untuk memperbaiki algoritma ini, kita butuh algoritma yang lebih rumit lagi yang mengikutkan beberapa pertimbangan tambahan.


Algoritma II (perbaikan dari algoritma 1)




































Pada algoritma diatas, alur pikiran dari musuh dibuat lebih rumit dengan memperbaiki struktur otaknya dan memberikan dua upgrade kemampuan sbb:

Pertama musuh akan diberi memori sehingga dia bisa mengingat langkah terakhir yang dia ambil. Kita bisa menentukan berapa banyak memori yang dimiliki oleh musuh. Apakah dia hanya bisa mengingat tempat terakhir yang dia lalui, ataukah dia bisa mengingat hingga lima posisi.

Sebenarnya satu posisi saja sudah cukup. Tujuan dari memori ini adalah untuk menghindari musuh bergerak ke tempat yang sama berkali-kali sehingga menimbulkan kesan musuh hanya berputar-putar saja. Musuh dilarang untuk berjalan ke tempat yang sudah dia lewati sebelumnya. Informasi tentang tempat yang sudah dia lewati disimpan dalam memorinya yang terbatas.

Kedua musuh akan diberi tambahan inisiatif untuk berjalan ke arah tertentu bila dia tidak bisa mengejar pemain. Setiap musuh memiliki prioritas arah sendiri-sendiri. Pada alur diatas, musuh memiliki prioritas untuk bergerak ke arah kanan terlebih dahulu, baru bergerak ke arah kiri, ke atas dan ke bawah.

Dengan adanya pilihan untuk bergerak ke arah tertentu bila dia tidak bisa mengejar pemain, maka musuh akan terlihat lebih pintar.

Contoh Kasus

 
Pada posisi pertama musuh tidak bisa mengejar pemain karena dihalangi oleh tembok. Musuh akan memilih bergerak kekanan sesuai dengan prioritas yang dimiliki.

Saat berada pada posisi kedua, musuh akan bergerak keatas karena posisi pemain berada di atas.Walaupun sebenarnya pada saat ini dia bisa memilih bergerak kekiri karena posisi pemain juga berada di sebelah kiri tapi dia tidak bisa melakukannya karena dia tidak bisa melewati tempat yang sama dua kali.

Pada posisi tiga, musuh memiliki pilihan untuk bergerak ke atas karena posisi pemain berada diatasnya, tapi dia juga bisa bergerak kekiri karena posisi pemain berada dikiri. Pada situasi ini, musuh akan bergerak kekiri karena dia memiliki prioritas lebih tinggi untuk berjalan kekiri dari pada berjalan ke atas.

Pada posisi empat, musuh akan langsung bergerak ke atas karena pemain berada di atas dan semua kondisi memungkinkan dia untuk bergerak keatas, dan akhirnya dia bisa mengejar pemain.

Algoritma ini menurut saya lebih baik dari yang pertama, dan bisa dikembangkan lagi ke algoritma untuk pergerakan group yang akan saya tulis pada artikel selanjutnya.

0 komentar:

:a: :b: :c: :d: :e: :f: :g:
:h: :i: :j: :k: :l: :m: :n: :o: :p: :q: :r: :s: :t: :u: :v: :w: :x: :y: :z:

Posting Komentar

OKe

no hal

Search