Algoritma Back track Pada Game Maze
Maze (Labirin) merupakan
game yang template-nya berbentuk
persegi yang ukurannya dapat
diatur sesuai dengan
keinginan user. Di dalamnya
terdapat serangkaian jalur
berupa labirin yang bercabang.
Namun, tidak setiap
cabang mencapai tujuan yang diinginkan.
Algoritma backtrack pertama kali
diperkenalkan oleh D.H.
Lehmer pada tahun
1950. Penggunaan algoritma backtrack
ini terlihat pada proses
penelusuran tiap jalur untuk mencapai tujuan yang diinginkan.
Sejak komputer memulai permainan, komputerakan menentukan jalur menelusuri sembarang
jalur. Ketika komputer menemukan
jalan buntu, maka ia akan
melakukan proses backtrack
dengan cara kembali
padajalur sebelumnya sampai menemukan jalur baru yang belum pernah
dilewati. Ada dua solusi untuk
masalah ini, yaitu secara iteratif dan
rekursif. Dalam game ini menggunakan metode iteratif. Dalam
game ini, algoritma
akan membagilintasan menjadi sederetan langkah. Sebuahlangkahterdiri dari
pergerakan satu unit
sel pada arahtertentu. Arah yang mungkin:ke atas (up),
ke bawah(down), ke kiri (left), ke kanan (right).
Algoritma Minimax Pada Game Catur
Catur merupakan
permainan two player strategy board game yang masih popular hingga saat ini.
Catur adalah permainan mental dengan menggunakan pikiran yang dimainkan oleh
dua orang. Sebelum bermain, pecatur terlebih dahulu memilih bidak atau biji catur yang akan ia mainkan. Terdapat dua
warna untuk membedakan bidak catur, yaitu hitam dan putih. Pemegang bidak putih
akan jalan terlebih dahulu diikuti oleh pemegang bidak hitam secara bergantian
hingga permainan selesai[1].
Kecerdasan Buatan (AI) adalah kecerdasan mesin dan cabang
ilmu computer yang bertujuan untuk menciptakan komputer cerdas yang dapat
berfikir layaknya manusia. Buku AI mendefinisikan bidang ini sebagai “the study
and design of intelligent agent” dimana agent cerdas adalah system yang
merasakan lingkungannya dan mengambil tindakan untuk memaksimalkan peluang yang
sukses. John McCarthy menciptakan istilah ini pada tahun 1956 yang di
definisikan sebagai “ilmu dan teknik membuat mesin cerdas”[3]. AI sangat banyak
digunakan pada aplikasi computer terutama pada aplikasi permainan. Pada two
player board games strategy, AI digunakan untuk mengatur strategi dan
memutuskan langkah yang dapat mengimbangi permainan player sehingga player yang
memainkan aplikasi ini seakan – akan bermain dengan player lain.
Algoritma minimax merupakan salah satu algoritma yang
digunakan pada permainan dua player yang memiliki AI atau pada zero sum games
seperti catur[2]. Pada algoritma minimax, pengecekan akan dilakukan untuk
mencari semua kemungkinan yang ada. Pengecekan tersebut akan menghasilkan pohon
permainan yang berisi semua kemungkinan tadi. Akan dibutuhkan resource dengan
skala besar untuk menangani pencarian pohon solusi tersebut karena kombinasi
kemungkinan pada permainan catur sangat banyak.
Pada algoritma minimax, komputer akan menganalisa semua
pohon permainan sehingga komputer akan mengambil langkah yang dapat membuat
lawan mendapatkan keuntungan minimum dan keuntungan maksimum pada komputer itu
sendiri[2],[6]. Dalam penentuan keputusan tersebut dibutuhkan suatu nilai atau
bobot yang dapat merepresentasikan kerugian atau keuntungan yang akan diperoleh
pada setiap langkah, sehingga langkah yang memiliki nilai terbesar (keuntungan
terbesar dan kerugian terkecil) akan dipilih.
Algoritma Greedy Pada Game Tower
Defense
Tower Defense merupakan salah satu genre
game minimalis pada PC dengan sub-genre dari Real-Time Strategy. Gameplay
dari Tower Defense sangat sederhana, 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. Penempatan Posisi Tower adalah hal yang sangat penting dan perlu diperhatikan, karena
tower memiliki radius serangan
tertentu (AOE, Area Of Effect ).
Strategi penempatan tower adalah hal
yang perlu dilakukan untuk mendapatkan skor yang maksimal.
Algoritma greedy merupakan metode yang paling populer untuk
memecahkan persoalan optimisasi. Sesuai dengan nama dari algoritmanya,
Algoritma Greedy Bersifat Rakus dan Tamak. “take what you can get now!” adalah
prinsip utama dari algoritma greedy dengan cara membentuk solusi langkah per
langkah (step by 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.
Implementasi
Algoritma Greedy pada penempatan tower
Yang harus diperhatikan pada permainan Tower Defense 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.
Algoritma Brute Force Pada Game
Tetris
Tetris adalah permainan teka-teki yang disusun dan diprogram
oleh sepasang programmer berkebangsaan Rusia.Dalam permainan tetris,
balok-balok tetris berjatuhan ke area permainan dalam waktu konstan.Balok
tetris selalu terdiri dari 4 balok kecil yang membentuk 7 macam rupa.
Pemain dapat mengontrol balok tetris yang jatuh melalui 4
tombol arah panah untuk menggeser ke kanan atau ke kiri dan tombol arah panah
ke bawah untuk mempercepat jatuhnya balok tetris. Satu kendali yang lain adalah
untuk memutar bentuk balok tetris 90º’
Algoritma yang gunakan untuk mencari solusi dari permainan
tetris adalah algoritma yang menggunakan konsep-konsep yang ada dalam algoritma
Greedy dan Algoritma BruteForce. Algoritma Greedy merupakan metode yang paling
umum digunakan untuk memecahkan masalah optimasi. Algoritma ini sederhana dan
sesuai dengan tujuan yang ada.
Algoritma Greedy
memecahkan masalah langkah per langkah, pada setiap langkah:
1. mengambil pilihan yang terbaik yang dapat diperoleh pada
saat itu tanpa memperhatikan konsekuensi ke depan (prinsip “take what you can
get now!”)
2. berharap bahwa dengan memilih optimum local pada setiap
langkah akan berakhir dengan optimum global Brute force adalah sebuah
pendekatan yang sesuai (straightforward) untuk memecahkan suatu masalah,
biasanya didasarkan pada pernyataan masalah (problem statement) dan definisi
konsep yang dilibatkan.
Prioritas keuntungan yang tersusun terdiri dari:
1. Membentuk satu atau lebih baris paling penuh
2. Membentuk satu atau lebih baris paling mendekati penuh
3. Tidak membentuk ruang kosong pada susunan tumpukan balok
4. Balok dapat masuk ke dalam susunan tumpukan balok paling
dalam Algoritma yang kami kemukakan akan mencari penempatan balok yang jatuh ke
ruang yang paling tepat sesuai prioritas keuntungan di atas diantara susunan
tumpukan balok. Pencarian ini akan
dilakukan secara Brute Force. Balok yang jatuh akan dicoba untuk ditempatkan ke
ruang di antara susunan tumpukan balok dibawah.
Algoritma ini akan mencari penempatan yang sesuai dengan
prioritas di atas. Pencarian solusi diantara susunan tumpukan balok akan
dilakukan secara Brute Force. Algoritma ini akan mencari solusi paling
menguntungkan untuk setiap sisi balok yang sedang jatuh. Pencarian solusi untuk
setiap sisi dilakukan secar Brute Force. Apabila pada skala prioritas tertinggi
memiliki lebih dari satu solusi terbaik yang sama, maka diantara solusi
tersebut akan dibandingkan satu sama lain untuk mencari yang paling menguntungkan
dengan standard prioritas selanjutnya, dan begitu selanjutnya. Apabila pada
skala prioritas tertinggi tidak memiliki solusi, maka akan mencari solusi
paling menguntungkan dengan skala prioritas selnjutnya, dan begitu selanjutnya.
Apabila pada skala prioritas tertinggi hanya memiliki satu solusi paling menguntungkan, maka akan dibandingkan dengan
solusi dari hasil pencarian solusi untuk sisi balok yang lain. Diantara setiap
solusi sisi balok, dicari solusi yang paling menguntungkan sesuai skala
prioritas di atas. Dan balok akan ditempatkan pada ruang tersebut.
Apabila ada kasus seperti diatas, maka algoritma tersebut
akan mencari solusi yang paling menguntungkan untuk menempatkan balok tersebut
ke ruang di antara susunan tumpukan balok. Pencarian dicari secara brute force
dari kiri ke kanan untuk sisi yang pertama kali keluar.Dapat dilihat seperti
gambar berikut, bahwa lgoritma seakan-akan menempatkan balok tersebut dari kiri
ke kanan untuk balok dengan sisi tersebut.
Setelah algoritma ini mancari solusi sampai paling kanan,
maka algoritma ini akan menyimpan satu solusi terbaik yang ada. Apabila ada beberapa
solusi yang sama baiknya, maka akan diambil penempatan paling kiri, seperti
dilihat dibawah ini.
Setelah menyimpan solusi terbaik untuk sisi tersebut, maka
algoritma ini akan mulai mencari solusi optimum untuk sisi berikutnya. Tampak
di bawah, algoritma in seakan-akan memutar balok untuk memulai pencarian sisi
berikutnya.Sisi berikut yang kami maksud disini adalah sisi dimana balok yang
sedang jatuh diputar 900 searah jarum jam.
Setelah itu, algoritma ini akan menyimpan solusi dari setiap
sisi berikutnya, seperti terlihat pada tiga gambar berikut ini.
Diantara setiap solusi sisi balok, dicari solusi yang paling
menguntungkan sesuai skala prioritas di atas. Dan balok akan ditempatkan pada
ruang tersebut. Seperti terlihat pada gambar berikut, algoritma ini telah
menemukan solusi terbaik, dan menempatkan balok pada ruang tersebut.
Algoritma Collision Detection Pada
Game Dokkaebi Shooter
Collision model adalah algoritma collision detection. Sebuah
algoritma yang berfungsi untuk memeriksa apakah dua buah objek spasial saling
bertumbukan. Algoritma ini sangat diperlukan di bidang animasi dan pebuatan
game. Dengan menggunakan algoritma ini, sang pembuat dunia virtual (game
ataupun animasi) bisa membuat dunia virtualnya semakin mirip dengan dunia
nyata. Algoritma ini sangat esensial di setiap pembuatan animasi ataupun game
karena jika tidak ada algoritma ini, tidak akan terjadi interaksi antar elemen
di dalam sebuah game atau animasi.
Game “Dokkaebi shooter” adalah sebuah game tembak-menembak 2
dimensi secara vertikal yang bisa dijalankan di platform android. Tujuan dari
game ini adalah menghabisi Dokkaebi sebanyak-banyaknya dalam tenggat waktu yang
sudah diberikan. Dokkaebi sendiri adalah sebuah monster mitologi dalam cerita
rakyat bangsa korea. Dalam permainan ini, pemain dituntut ketangkasannya untuk
menembak dokkaebi secepatnya dan juga menghindari tembakkan dokkaebi dan
dokkaebi itu sendiri.
Dalam game ini algoritma collision detection sangat
dibutuhkan. Jika algoritma collision detection tidak diterapkan dalam game ini,
game akan tidak bisa dimainkan. Setiap objek yang saling bertumbukan hanya akan
saling bertumpuk dengan gambar lain dan melewatinya. Permainan pun juga tidak
akan punya tujuan karena tidak ada yang berubah dalam lingkungan game itu
sendiri.
http://nickotriputra.blogspot.co.id/
http://dokumen.tips/documents/analisis-penerapan-algoritma-backtrack-pada-game-maze-55a35b455473a.html
http://chachados.blogspot.co.id/2012/04/algoritma-pada-game-tetris.html
informatika.stei.itb.ac.id/.../Tugas%20Besar-I-IF3051-Strategi-Algoritma-Greedy.pdf
https://bamandhityo.wordpress.com/tag/algoritma-collision-detection/
Tidak ada komentar:
Posting Komentar