JOKODOK: GAME PUZZLE NUMBER

Latar Belakang

Program permainan (game) merupakan salah satu implementasi dari bidang ilmu komputer. Perkembangan permainan pada masa kini sudah sangat pesat dan telah menjadi mode tersendiri di dunia karena mayoritas pengguna komputer menghabiskan sebagian besar waktu mereka di depan komputer dalam program permainan. Salah satu algoritma yang digunakan untuk mengembangkan program permainan adalah algoritma berbasis pohon ruang pencarian (searching algorithm). Salah satu game yang menggunakan algoritma berbasis pohon ruang pencarian dalam menyelesaikan permainannya yaitu N-puzzle.

N-puzzle merupakan permainan menyusun angka-angka dengan aturan sebuah potongan hanya dapat dipindahkan dengan menggesernya ke ruang kosong(blank tile). Puzzle ini merupakan jenis puzzle yang memiliki tingkat kesulitan sangat tinggi dalam menyelesaikan masalahnya dibandingkan jenis puzzle lain. Umumnya orang yang memainkan puzzle ini butuh waktu lama dalam menyelesaikan permainannya. Hal ini disebabkan karena pada N-puzzle tidak ada informasi tambahan yang dimiliki untuk membantu melakukan pencarian solusi, sehingga saat proses penyusunan potongan-potongan puzzle terjadi susunan puzzle semula. Untuk menyelesaikan persoalan pada permainan ini dibutuhkan suatu algoritma pencarian efektif yang dapat diterapkan.

Dilihat dari karakteristik persoalan N- puzzle, puzzle ini membentuk ruang solusi yang diorganisasikan ke dalam struktur pohon dinamis. Struktur pohon dinamis sendiri dibangun dengan 2 metode traversal yaitu Breadth First Search (BFS) danDepth First Search (DFS). Untuk itu penulis menerapkan algoritma Breadth First Search dan Depth First Search dalam menyelesaikan permainan N-puzzle.

Batasan Masalah

Penulis membatasi masalah pada penulisan ini sebagai berikut :

1. N-Puzzle dibuat dengan menggunakan tampilan Graphical User Interface(GUI).

2. Bahasa Pemrograman yang dipakai dalam pembuatan puzzle ini adalah Visual Prolog 7.1

3. Puzzle berukuran 4 x 4 dengan berisi 15 papan yang terisi dengan angka 1 – 15 dan satu papan kosong (blank). Setiap memulai game, susunan puzzle akan diacak secara random oleh komputer

Tujuan

Tujuan dari penulisan ini adalah mengimplementasikan penerapan algoritma Breadth First Search (BFS) dan Depth First Search (DFS) sehingga dapat digunakan untuk mengoptimalkan waktu dalam menyelesaikan permainan N-puzzle. Permainan ini juga dapat dijadikan salah satu media alternatif untuk mengisi waktu senggang. Selain itu, permainan puzzle juga termasuk salah satu jenis permainan edukasi yang dapat digunakan untuk melatih kemampuan nalar dan logika.

Metode Penulisan

Metode yang digunakan pada penulisan ini adalah :

1. Perancangan Aplikasi

Tahap perancangan aplikasi dilakukan dengan perancangan tatap muka (interface) game, perancangan alur program, dan penyiapan softwarebahasa pemrograman Visual Prolog 7.1.

2. Pembuatan Aplikasi

Tahapan dalam pembuatan aplikasi meliputi desain yang telah dibuat pada tahap perancangan diterapkan ke dalam kode program dengan berpedoman pada teori-teori dan algoritma yang mendukung pembuatan game N-puzzle tersebut.

3. Pengujian Aplikasi

Tahapan pengujian aplikasi dilakukan dengan menguji (debuging) terhadap kode sumber (source code) untuk memastikan bahwa fungsi-fungsi pada kode berjalan sesuai tujuan.

Konsep AI

Puzzle Number adalah permainan tradisional yang direpresentasikan dalam papan n x n, dimana setiap blok papan di beri angka dari 1 sampai (n² - 1) dan satu buah papan kosong (blank), yang terurut dari sisi kiri atas papan sampai kanan bawah. Satu papan kosong (disisi paling kanan) digunakan untuk memindahkan papan-papan disekelilingnya. Pemindahan bisa dilakukan dengan memindahkan papan kosong tersebut ke atas, ke bawah, ke kanan, atau ke kiri. Papan yang kosong harus terus dipindah-pindahkan agar solusi akhir didapat. Solusi akhir dari permainan ini adalah papan-papan tersebut terurut dari nilai yang paling kecil hingga yang paling besar seperti pada gambar dibawah ini

1	2	3	4
5	6	7	8
9	10	11	12
13	14	15

Aturan-Aturan

Aturan ke-	Kondisi	Pergerakan Papan Kosong
1	Jika Papan Kosong berada di tengah.	Atas, Bawah, Kiri,Kanan
2	Jika Papan Kosong Berada di paling kanan	Atas, Bawah, Kiri
3	Jika Papan Kosong Berada di paling kiri	Atas, Bawah, Kanan
4	Jika Papan Kosong Berada di paling atas	Kiri, Kanan, Bawah
5	Jika Papan Kosong Berada di paling bawah	Kiri, Kanan, Atas
6	Jika Papan Kosong Berada di sudut Kanan Atas	Kiri, Bawah
7	Jika Papan Kosong Berada di sudut Kiri Atas	Kanan, Bawah
8	Jika Papan Kosong Berada di sudut Kanan Bawah	Kiri, Atas
9	Jika Papan Kosong Berada di sudut Kiri Bawah	Kanan, Atas