Electronic Theses and Dissertation

Maze non-perfect merupakan maze yang memiliki cycle. penelitian ini ditujukan untuk merancang algoritma yang dapat membentuk maze non-perfect dengan ukuran m×n yang memiliki dua buah bias. bias pertama merupakan komposisi dari sekat horizontal dan sekat vertikal dan bias kedua merupakan komposisi dari cycle. algoritma yang dibuat pada penelitian ini dihasilkan dengan melakukan modifikasi pada algoritma prim serta penggunaan algoritma fisher yates yang juga digunakan dalam membantu perancangan algoritma. algoritma maze non-perfect dimulai dengan menghitung nilai paramater dan dilanjutkan dengan membentuk maze perfect dan diakhiri dengan membentuk maze non-perfect. algoritma yang sudah dirancang dapat membentuk sebuah maze dengan bias dengan waktu terburuk dari algoritma ini bekerja adalah sebesar |e|^2, di mana e merupakan himpunan edge dari sebuah grid graph m×n. pengembangan aplikasi dengan berbasis flash juga dilakukan agar dapat memvisualkan algoritma. algoritma yang divisualkan akan ditampilkan dalam bentuk dua dimensi berupa gambar dari maze yang dibuat beserta graf padanannya. aplikasi yang dikembangkan memiliki 4 buah menu utama, dimana setiap menunya akan mengarahkan ke halaman lain yang bersesuaian dengan nama menunya. aplikasi tersebut mampu mencari hingga 20 solusi pertama dari maze berbias yang akan ditampilkan.

A non-perfect maze is a maze that contain cycle. The aim for this study is to construct an algorithm that can generate a m×n non-perfect maze with two biases. The first biases is the composition of horizontal and vertical walls and for the second biases is the composition of cylce. The algorithm designed in this study is the result from modifying Prim algorithm as well as the application from Fisher Yates algoritm is using to help in this study. The maze non-perfect algorithm starts by calculating parameter value and continues by forming a perfect maze and end by forming a non-perfect maze. The algorithm is able to generate a biases maze with the worst time this algorithm work is |E|^2, where E is the set of edge from m×n grid graph. A Flash-based software is developed to visualize the algorithm. The visualized algorithm will be displayed in two dimensional object from the created maze and its corresponding graph. This software has 4 main menu, where each menu will direct to another page that correspond to the name of the menu. This software is able to find the first 20 solution of biased mazes to display.