Perbandingan perbandingan Algortima Breadth First Search Pada Aplikasi Game Onet menggunakan Platform Android

Onet Fruit merupakan permainan yang bertujuan mencocokan gambar yang sama dengan syarat kedua gambar itu harus dihubungkan maksimal tiga garis maya tanpa terhalang gambar-gambar yang lain. Hal ini menjadi faktor kerumitan tersendiri dalam menyelesaikan permainan nya disebabkan karena setiap gambarnya hampir serupa tapi tak sama, dan dibatasi waktu untuk menyelesaikannya.

Permainan Onet Fruit memerlukan suatu algoritma pencarian yang digunakan untuk memecahkan solusi permainan. Dalam tugas akhir ini dijelaskan penerapan algoritma breadth-first search (BFS) dan depth-first search (DFS) dalam menyelesaikan permainan Onet Fruit pada platform Android.

Setelah itu dilakukan pengujian dengan cara pemain memilih titik awal dan titik akhir dalam papan Onet Fruit yang disediakan oleh sistem lalu sistem memberikan solusi pencarian jalan menggunakan algoritma Breadth First Search dan Depth First Search. Jika dalam papan tersebut sudah tidak ada lagi yang dapat dipasangkan, maka sistem akan mengacak secara otomatis.

Dari hasil uji akan terlihat performansi jumlah garis, sel, waktu dan node pencarian dari kedua algortima tersebut. Pencarian akan optimal menggunakan BFS jika posisi titik awal (x1, y1) dan titik akhir (x2, y2) berdekatan baik secara horizontal (y1=y2), vertikal (x1=x2) maupun diagonal (x2 � x1 <= 2 atau y2 � y1 <= 2 ataupun sebaliknya). Sedangkan pencarian menggunakan DFS akan optimal jika posisi antara titik awal dan titik akhir berjauhan atau posisi titik akhir berada di sebelah kiri atau atas titik awal, karena proses pencarian dilakukan mulai dari kiri, atas, kanan lalu bawah.

Onet Fruit is a game with simple objective where player tries to match two images based on some kind of rules. The rules are that the images must be of the same kind, and they can be reached within three lines, without obstruction from other images. These rules add some complexity on the game play, because player should try to match similar images, and s/he should do it wihtin time limit.

Onet Fruit needs some kind of algorithm to search for the solution. This final project will explain the implementation of breadth-first search (BFS) and depth-first search (DFS) algorithm on Android platform in solving problems found in Onet Fruit.

Some tests will be done where player choose a starting point and a destination point on Onet board, and then the system will try to solve the problem using breadth-first search and depth-first search algorithm. If the board is there no more that can be paired, then the system will automatically randomize.

The test result will be number of lines, cell, time, and visited nodes than can be used as a benchmark for both algorithms. The search for optimal use of BFS if the position of starting point (x1,y1) and destination point (x2, y2) adjacent either horizontal (y1=y2), vertical (x1=x2) or diagonal (x2 � x1 <= 2 atau y2 � y1 <= 2). And the search for optimal use of DFS if the position of starting point and destination point are far or destination point position is on the left or above the starting point, because seacrh begins from left, top, right, and then bottom.