Menganalisis Penggunaan Algoritma Backtracking dan Algoritma Greedy pada Penerapan Game Tower Defense

Pada materi sebelumnya saya sudah membahas apa itu permainan Tower Defense begitupun dengan bagaimana rules permainanya. Dan kita tahu bahwa 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).

Jenis permainan seperti Tower Defense ini tidak cocok apabila dibuat menggunakan algoritma backtracking, karna Algoritma backtracking (runut balik) merupakan salah satu metode pemecahan masalah yang termasuk dalam strategi yang berbasis pencarian pada ruang status. Algoritma backtracking bekerja secara rekursif dan melakukan pencarian solusi persoalan secara sistematis pada semua kemungkinan solusi yang ada. Oleh karena algoritma ini berbasis pada algoritma Depth-First Search (DFS), maka pencarian solusi dilakukan dengan menelusuri suatu struktur berbentuk pohon berakar secara preorder. Proses ini dicirikan dengan ekspansi simpul terdalam lebih dahulu sampai tidak ditemukan lagi suksesor dari suatu simpul.

Algoritma backtracking biasanya digunakan pada jenis game seperti Crossword Puzzle. Hasil analisis kemampuan algoritma backtracking dalam menyelesaikan persoalan pengisian crossword puzzle menunjukkan bahwa algoritma ini cukup efektif untuk mendapatkan solusi persoalan tersebut. Sistem kerja algoritma backtracking yang sistematis dan ciri khasnya yang hanya memeriksa kemungkinan solusi yang memang dapat dipertimbangkan untuk menjadi solusi akhir, diperkirakan dapat menjadi solusi yang efektif dan efisien untuk persoalan ini. 

Sedangkan pada game Tower Defense di perlukan kemampuan untuk 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.