Selasa, 22 Mei 2012

Game Algorithms - Tetris Algorithms



Algoritma Game Tetris

Algoritma yang digunakan dalam permainan tetris dan akan kami bahas dalam makalah ini adalah algoritma yang menggunakan konsep-konsep algoritma greedy dan algoritma brute force. Algoritma greedy banyak digunakan dalam memecahkan masalah optimasi, algoritma ini juga cukup 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 pada tetris untuk mendapatkan susunan balok dengan posisi akhir yang paling baik, yaitu membentuk suatu baris penuh sehingga baris dapat terhapus. Algoritma ini menggunakan prinsip mencari langkah solusi yang paling manguntungkan yaitu algoritma greedy. 
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 jelaskan akan mencari penempatan balok yang turun pada posisi yang paling tepat dan sesuai dengan keuntungan diatas diantara susunan tumpukan balok. Pencarian solusi akan dilakukan dengan pendekatan algoritma 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 masalah seperti diatas, maka algoritma akan mencari solusi yang paling tepat, yaitu yang paling menguntungkan untuk penempatan balok yang turun diantara susunan balok yang sudah turun sebelumnya. Pencarian dicari dari kiri ke kanan untuk sisi yang pertama kali keluar yaitu secara algoritma brute force.
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, lalu algoritma ini akan mencari solusi optimum untuk sisi berikutnya. Seperti yang tampak pada gambar di bawah, algoritma ini seakan-akan memutar balok untuk memulai pencarian sisi berikutnya. Sisi berikut yang kami maksud disini adalah sisi dimana balok yang sedang jatuh diputar 90o 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.