Tower
Defense adalah jenis permainan yang dibuat untuk mengasah kemampuan logika.
Dalam permainan ini pemilihan penyimpanan tower dianggap krusial dan sangat
penting untuk diperhatikan, karena
tower memiliki radius serangan
tertentu (AOE, Area Of Effect ).
Strategi penempatan tower adalah hal
yang perlu dilakukan untuk mendapatkan skor yang maksimal.
Cara
bermain dari game ini yakni pemain mencoba menghentikan musuh yang melintasi
suatu jalan tertentu dengan tower/bangunan yang dapat menyerang. Tower dapat
menyerang musuh dengan kemampuan beragam dan biaya yang berbeda. Ketika tower mengalahkan salah satu musuh dari wave, akan mendapatkan gold/uang
dan skor. Gold atau uang pada Tower defense dapat digunakan untuk membeli tower baru, upgrade tower,
atau membeli hal lain sesuai fitur dari Tower
defense yang dimainkan.
Contoh game tower defense
Algoritma yang diterapkan pada permainan ini adalah
Algoritma greedy. Algoritma greedy merupakan metode yang paling popular untuk
memecahkan persoalan optimisasi. Prinsip utama dari algoritma greedy adalah “ take what you can get now! ” dengan
cara membentuk solusi langkah perlangkah (step ny step). pada setiap
langkahnya, algoritma greedy
mengambil keputusan berdasarkan nilai terbaik (minimasi dan maksimasi) tanpa
mengambil konsekuensi langkah dan pilihan di depan (langkah selanjutnya).
Elemen-elemen algoritma greedy:
1.
Himpunan kandidat.
2.
Himpunan solusi.
3.
Fungsi seleksi (selection function).
4. Fungsi
kelayakan (feasible).
5.
Fungsi obyektif.
Dan yang harus diperhatikan pada permainan Tower Defense ini
adalah kita harus mampu mengeliminasi atau membunuh musuh yang melintas
semaksimal mungkin dengan membangun tower di tempat yang strategis dan memiliki
jangkauan serangan yang besar terhadap jalur musuh. Dengan persoalan harus membunuh sebanyak mungkin
musuh, maka diperlukan penempatan tower
yang strategis karena total tower
yang bisa disimpan terbatas dengan persediaan gold/uang yang ada. Dalam persoalan ini Algoritma Greedy dapat digunakan untuk
penyelesaian masalah.
Algoritma
Greedy dapat menempatkan tower pada lokasi optimum dengan radius
yang efektif untuk membunuh musuh dengan tujuan memperoleh skor maksimal.
Elemen
Algoritma Greedy pada simulasi tower defense ini :
o
Himpunan
kandidat, himpunan titik-titik pada Battleground
atau pada peta tower defense
o
Fungsi
Seleksi, memilih titik yang sesuai pada Battleground.
Titik yang dipilih adalah titik yang memiliki AOE (area yang memungkinkan bisa dilakukan
serangan) paling besar.
o
Fungsi
Kelayakan, untuk mengecek apakah suatu titik dapat dibangun tower atau tidak. Titik dapat dibangun tower jika tidak terdapat tower lain dan tidak berada pada wave path
dan limit tower yang bisa dibangun
(sesuai dengan jumlah gold/uang yang
dimiliki).
o
Fungsi
Objektif, untuk memaksimalkan skor dengan memperoleh AOE sebesar mungkin untuk
memungkinkan tower dapat menyerang
musuh.
o
Himpunan
Solusi , himpunan titik yang merupakan tempat strategis tower dapat dibangun.
|
Algoritma untuk mendapatkan titik
himpunan solusi :
o
Mengambil
titik-titik pada peta yang memenuhi fungsi kelayakan (dapat dibangun tower) dengan fungsi generateArea dan
memberikan nilai representasi tiap titik.
0, representasi dari wilayah yang dapat dibangun tower
9, representasi dari wave path dan tidak dapat dibangun tower
1, representasi dari bangunan tower yang sudah dibuat dan tidak bisa
dibangun tower kembali
Dapat diambil
himpunan titik layak bangun dengan fungsi makeEnable yaitu fungsi untuk
mengambil area manakah yang bias dibangun tower atau area manakah yang memiliki
nilai ‘0’ pada list atau array battleground.
T={{1,A},{1,H},{1,I},{1,J},{2,A},{2,C},{2,D},{2,E},{2,F},{2,H},{2,I},{2,J},{3,A},{3,C},{3,D},{3,H},{4,A},{4,C},{4,D},{4,F},{4,G},{4,H},{4,J},{5,A},{5,C},{5,D},{5,J},{6,A},{6,D},{6,E},{6,F},{6,G},{6,H},{6,I},{6,J},{7,A},{7,B},{7,E},{7,F},{7,G},{7,H},{7,I},{7,J},{8,A},{8,B},{8,C},{8,F},{8,G},{9,A},{9,B},{9,C},{9,D},{9,I},{9,J},{10,A},{10,B},{10,C},{10,D},{10,E},{10,F},{10,G},{10,H},{10,I},{10,J}}
o
Pada
array T[10][10] atau himpunan titik T dapat dicari radius tower paling besar dengan fungsi findMaxAoe, dan return/feedback dari fungsi findMaxAoe
adalah titik yang memiliki radius AOE paling besar sesuai dengan algoritma greedy yang bersifat take what you can get now!.
Proses pencarian titik dengan AOE
terbesar adalah mencari titik dengan nilai ‘9’ yang merepresentasikan jalur
musuh paling banyak.
Pada langkah ini didapatkan titik
layak bangun pertama adalah (2,F) dengan area terbesar 7 titik. Dan tower dibangun pada titik yang telah
ditemukan dengan procedure
buildTower.
o
Proses
pembangunan tower dapat dilakukan
dengan cara mengubah nilai representasi pada titik yang akan dibangun dengan
nilai ‘1’ yang merepresentasikan bahwa di titik tersebut terdapat tower dan tidak dapat dibangun tower kembali. Dan nilai ‘2’ pada AOE
titik tower tersebut untuk
mengantisipasi adanya tower yang
dibangun di sekitarnya padahal daerah tersebut sudah di handle oleh tower yang
sudah dibangun (Karena Tower dibangun
dengan melihat nilai ‘9’ pada battleground).
Sumber :
|
