Finding Sortest Path in Maze

A. Deskripsi
Finding sortest path in maze merupakan sebuah game yang dibuat dari sebuah visualisasi dengan menggunakan scratch. Pada game ini terdapat 3 objek yang penting pada maze tersebut, yaitu dinding maze, start path dan finish path. User diberi kebebasan untuk menggambar dinding pada area yang diberikan dan bebas meletakkan start dan finish, kemudian sistem akan menghitung jarak optimal dari kemungkinan yang ada. Game ini menggunakan algoritma pencarian A* untuk mencari rute yang optimal dengan menghitung nilai heuristiknya.

B. Algoritma
Game ini menggunakan algoritma A*.
Dimana algoritma A* ini adalah salah satu algoritma pencarian yang menganalisa input, mengevaluasi sejumlah jalur yang mungkin dilewati dan menghasilkan solusi. Algoritma A* adalah algoritma komputer yang digunakan secara luas dalam graph traversal dan penemuan jalur serta proses perencanaan jalur yang bisa dilewati secara efisien di sekitar titik-titik yang disebut node (Reddy, 2013).

Algoritma A* menggunakan path dengan cost paling rendah ke node yang membuatnya sebagai algoritma pencarian nilai pertama yang terbaik atau best first search. Menggunakan rumus :

f(x) = g(x)+h(x)

g(x) = adalah jarak total dari posisi asal ke lokasi sekarang.
h(x) = adalah fungsi heuristik yang digunakan untuk memperkirakan jarak dari lokasi sekarang ke lokasi tujuan

C. StoryBoard

1.      Tampilan awal game ini adalah tombol tombol menu. Diantarnya adalah :

-          Start          : Menu untuk memulai game

-          Tutorial      : Menu yang akan menjelaskan fungsi dari objek objek yang ada pada game tersebut dan cara penggunaannya dalam game tersebut.

-          Options     : Menu pilihan untuk pengguna menyalakan musik atau mematikan musik yang ada pada saat lembar menu dibuka.

-          Back          : Untuk kembali

2.      Setelah menekan tombol start, akan terdapat beberapa tombol di bawah, diantaranya :

-          Back          : Untuk kembali.

-    Empty       : Untuk menghapus kotak yang sudah letakkan di papan permainan.

-         Wall           : Kotak yang akan berfungsi sebagai dinding, kotak yang diberi wall tidak dapat dilewati.

-         Start          : Sebagai kotak yang menandai start path

-         Finish        : Sebagai kotak yang menandai finish path

-         Begin         : Untuk memulai pencarian rute

-         Clear          : Untuk menghapus seluruh kotak yang ada pada papan game

3.      Papan game ini berbentuk kotak kotak, pengguna harus meletakkan kotak start, finish, dan wall pada kotak yang telah disediakan. Kotak start dan finish hanya ada 1, sedangkan untuk dinding bisa lebih dari satu sesuai dengan papan kotak yang tersedia.

Permainan tidak bisa dimulai apabila tidak terdapat kotak start dan finish.

4.     Setelah meletakkan kotak start, finish dan dinding, kemudian menekan tombol begin untuk memulai pencarian rutenya. Di sekitar kotak start akan terdapat kotak berwarna hijau yang akan mencari rute yang bisa dilalui sampai ketemu kotak finish.

5.      Setelah pencarian selesai, sistem akan menggambar rute yang paling optimal sesuai dengan perhitungan nilai heuristiknya.

D. Link Download Apk

DOWNLOAD

E. Link Download Dokumentasi

DOWNLOAD DOKUMENTASI