TKAP

DOKUMENTASI FINAL PROJECT

TOPIK KHUSUS ALGORITMA DAN PEMROGRAMAN

“LABYRINTH PUZZLE GAME”

DESAIN

Background

Square

Turtle Position

Bear

Fish

LOGIC

Algoritma Backtracking 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. Algoritma backtracking yang digunakan berbasis pada algoritma Depth First Search (DFS), maka pencarian solusi dilakukan dengan menelusuri suatu struktur berbentuk pohon berakar secara preorder.

Prinsip dasar algoritma backtracking adalah mencoba semua kemungkinan solusi yang ada. Perbedaan utamanya adalah pada konsep dasarnya, yaitu pada backtracking semua solusi dibuat dalam bentuk pohon solusi, dan kemudian pohon tersebut akan ditelusuri secara DFS sehingga ditemukan solusi terbaik yang diinginkan.

Seperti yang telah dijelaskan bahwa pencarian solusi dengan menggunakan algoritma backtracking ini berbasis pada DFS kita menggunakan pohon ruang status.

Langkah-langkah pencarian solusi dengan backtracking

adalah sebagai berikut :

1. Solusi dicari dengan membentuk lintasan akar ke daun. Simpul yang sudah dilahirkan dinamakan simpul hidup dan simpul hidup yang diperluas dinamakan simpul-E (Expand-node).

2. Jika lintasan yang diperoleh dari perluasan simpulE tidak mengarah ke solusi, maka simpul itu akan menjadi simpul mati dimana simpul itu tidak akan diperluas lagi.

3. Jika posisi terakhir ada di simpul mati, maka pencarian dilakukan dengan membangkitkan simpul anak yang lainnya dan jika tidak ada simpul anak, maka dilakukan backtracking ke simpul orang tua.

4. Pencarian dihentikan jika telah menemukan solusi atau tidak ada simpul hidup.

DOKUMENTASI

DESKRIPSI

Labyrinth Puzzle Game merupakan game yang divisualisasikan melalui scratch tentang seorang beruang yang mencari ikan. Beruang ini akan melewati jalan yang ada di dalam labirin untuk mencari ikannya. Algoritma yang digunakan adalah backtracking algorithm dalam pembuatan labyrinth dan random number dalam meletakkan posisi awal beruang dan ikan. Game ini dibuat untuk memenuhi Final Project matakuliah Topik Khusus Algoritma dan Pemrograman.

STORYBOARD

Membuat kotak-kotak yang nantinya akan jadi labirin

Kotak untuk labirin sudah sepenuhnya terbuat.

Turtle akan membentuk labirin dengan recursive backtracking algorithm..

Turtle selesai membentuk labirin.

Labirin sudah selesai dibuat dan permainan sudah siap dimainkan. Cara memainkannya adalah mengarahkan beruang untuk mendapatkan ikan. Tetapi sebelum mendapatkan ikan beruang harus melewati labirin yang ada dan tidak boleh menyentuh tembok labirin yang berwarna hitam.

PENJELASAN SOURCE CODE

Sprite Maze

Set nilai dari tiap variable yang nantinya akan digunakan.

Membentuk kotak dengan ukuran 11 x 15 ( height x width). Dimulai dari x = left edge dan y = bottom edge dan akan kembali lagi jika telah selesai.

Mengecek kemungkinan arah yang dapat dilewati (left, right, down, up)

Jika possible move nya lebih dari 1 maka dia akan memilih mana yang akan dia pilih secara random arah yang akan dia lewati (left, right, up, down)

Jika tidak ada kemungkinan untuk berpindah lagi makan akan berpindah ke titik yang sebelumnya hingga ditemukkan posisi/titik dimana nilai possible move nya != 0

Sprite Bear

Terdiri beberapa kondisi bergantung pada tombola apa yang akan ditekan. Dan setiap kondisi memiliki respon yang berbeda-beda. Intinya untuk mengarahkan sprite bear kemana dia akan pergi dan bear akan berhenti jalan saat bertemu dengan object berwarna hitam dan akan berakhir saat bertemu dengan sprite fish.