Minggu, 15 April 2012

Algoritma pada Game Tetris


           Pengertian 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.

Algoritma
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.

            Algoritma brute force memecahkan masalah dengan sangat sederhana, langsung dan dengan cara yang jelas (obvious way). Algoritma yang digunakan untuk mendapatkan susunan tumpukan balok yang paling baik dengan menempatkan balok ke tempat yang tepat.Algoritma ini menggunakan prinsip Greedy dalam mencari langkah sollusi yang paling menguntungkan. 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.

Apabila ada kasus seperti diatas, maka algoritma kami 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.



Penggunaan Matriks dalam pembuatan Tetris
Pada game tetris, terdapat blok-blok yang akan kita susun secara horizontal ataupun vertikal blok-blok tersebut dinamakan dengan grid. Jumlah tiap baris grid tergantung pada si pembuat tetris, kalo contoh yang kami gunakan berjumlah 15 grid.Grid tersebut pada pemrograman kita buat dengan menggunakan matriks berdimensi 2.Contoh :
___________________
o o o o
o o o o
o o o o
__________________
Sebagai contoh gambar diatas adalah matriks ukuran 4x3 (4 kolom, 3 baris).Begitu pula pada tetris juga memiliki ukuran kolom x baris (m x n). Pada kolom 1 baris 1, memiliki index[0,0]. Pada kolom 1 baris 2, memiliki indexnya[0,1]. Pada kolom 1 baris 3, memiliki index[0,2]. Pada kolom 2 baris 1, itu indexnya[1,0]. Pada kolom 2 baris 2, itu indexnya[1,1] dan s seterusnya. Di sini kami anggap susunannya  terlihat seperti pada matriks dibawah ini :
[0,0] [0,1] [0,2] [0,3]
[1,0] [1,1] [1,2] [1,3]
[2,0] [2,1] [2,2] [2,3]
Baris paling atas pada tetris  (baris 1) memiliki index [0,n] sampai [0,n+1]. Sehingga dapat kita anggap ukuran layar tetris [m,n]. Setiap ada blok yang turun atau berjatuhan kita definisikan sebagai, m+1 dan setiap bergeser kekanan n+1 dan setiap kekiri n-1
Pada permainan tetris ini apabila blok yang berjatuhan telah melampaui batas dari layar tetris [m,n] maka permainan akan berakhir (game over) sehingga apabila ada baris yang penuh (sesuai dengan syarat) maka baris tersebut akan dihapus.

2 komentar: