iko42360 robotika - · pdf fileiko42360 robotika - genap 2010/2011 laporan tugas pengganti uts...
TRANSCRIPT
IKO42360 ROBOTIKA - GENAP 2010/2011
LAPORAN TUGAS PENGGANTI UTS
Fukushi Fighter
Oleh:
Adrianto Santoso (1205000126)
Fahri Nurul Hidayat (0706271701)
Faris Al Afif (0706271733)
M Iqbal Tawakal (0706271954)
FAKULTAS ILMU KOMPUTER
UNIVERSITAS INDONESIA
2011
2
DAFTAR ISI
BAB I PENDAHULUAN ........................................................................................................................ 4
1.1. Latar Belakang ........................................................................................................................ 4
1.2. Rumusan Masalah ................................................................................................................... 4
BAB II STUDI LITERATUR .................................................................................................................... 6
2.1. Locomotion............................................................................................................................. 6
2.1.1. Wheel .............................................................................................................................. 6
2.1.1.1. Roda Standar ................................................................................................................. 6
2.1.1.2. Roda Castor ................................................................................................................... 7
2.2. Sensor..................................................................................................................................... 7
2.2.1. Sensor Ultrasonik ............................................................................................................. 8
2.2.2. Sensor Warna................................................................................................................... 8
2.2.3. Sensor Sentuh .................................................................................................................. 8
2.2.3. Sensor Suara .................................................................................................................... 9
BAB III METODE RISET ..................................................................................................................... 10
3.1. Spesifikasi Robot ................................................................................................................... 10
3.1.1. Robot Hayate ................................................................................................................. 10
3.1.1. Robot Kazetora .............................................................................................................. 10
3.2. Skenario ................................................................................................................................ 11
3.2.1. Skenario 1 (menggunakan Arena Pertama) ..................................................................... 11
3.2.2. Skenario 2 (menggunakan Arena Kedua) ........................................................................ 12
3.2.3. Skenario 3 (Penambahan Sensor Suara) ......................................................................... 13
BAB IV HASIL EKSPERIMEN .............................................................................................................. 14
4.1. Navigasi Robot ...................................................................................................................... 14
4.1.1. Gerakan Maju ................................................................................................................ 14
4.1.2. Fungsi-fungsi Pengecekan dalam Navigasi ...................................................................... 15
4.1.3. Pembacaan Garis dan Persimpangan .............................................................................. 16
4.1.4. Pendeteksian Posisi Tujuan ............................................................................................ 16
4.1.5. Mendeteksi Suara yang Cukup Keras .............................................................................. 17
4.2. Maze Mapping ...................................................................................................................... 18
4.3. Shortest Path ........................................................................................................................ 18
3
4.4. Communication .................................................................................................................... 18
4.4.1. Menemukan Device ....................................................................................................... 19
4.4.2. Inisiasi Sambungan Antar Device .................................................................................... 20
4.4.3. Menyiapkan Pertukaran Data Antar Device .................................................................... 20
4.4.4. Kazetora Menunggu Sambungan dari Hayate ................................................................. 21
4.4.4. Hayate Mengirimkan Data ke Kazetora ........................................................................... 21
4.4.5. Kazetora Menerima Sambungan dari Hayate .................................................................. 22
4.4.6. Kazetora Menerima Data dari Hayate ............................................................................. 22
4.5. Hasil Eksperimen................................................................................................................... 24
4.5.1. Hasil Eksperimen I .......................................................................................................... 24
4.5.2. Hasil Eksperimen II ......................................................................................................... 30
4.5.3. Hasil Eksperimen III ........................................................................................................ 36
BAB V KESIMPULAN ......................................................................................................................... 38
5.1. Kesimpulan ........................................................................................................................... 38
DAFTAR PUSTAKA ............................................................................................................................ 39
LAMPIRAN ....................................................................................................................................... 40
1. Ouput Hasil Running Program untuk Arena Pertama ................................................................ 40
2. Ouput Hasil Running Program Untuk Arena Kedua ................................................................... 50
4
BAB I
PENDAHULUAN
1.1. Latar Belakang
Jepang mengalami bencana hebat di kuarter awal tahun 2011 ini. Dimulai dari gempa besar
dengan skala 9.1 richter, gempa terbesar yang menimpa Jepang setelah The Great Kanto
Earthquake tahun 1930. Gempa ini mengakibatkan dua bencana susulan. Yang pertama
adalah Tsunami setinggi 10 meter yang menghempas sebelah timur Jepang, dan kemudian
kebocoran pembangkit nuklir Fukushima yang mengancam kesehatan pekerja dan
masyarakat yang tinggal di sekitarnya.
Untuk mengatasi permasalahan nuklir di Fukushima, maka akan diturunkan sebuah tim
robot bernama Fukushi Fighter yang terdiri dari 2 buah robot. Robot pertama, yaitu Robot
Hayate (疾風 ), berfungsi untuk menjelajahi beberapa kemungkinan jalur menuju tempat
kebocoran yang kemudian menentukan jalur terpendek dan kemudian menyampaikan
informasi ini ke robot kedua. Robot kedua, yaitu Robot Kazetora (風虎), berfungsi menerima
informasi penting dari robot pertama sehingga bisa menuju tempat kebocoran dengan tepat
dan cepat.
Penjelajahan jalur-jalur menuju tempat tujuan dilkakukan dengan menggunakan Algoritma
Maze Mapping dan pencarian jalur terpendek dilakukan dengan menggunakan Algoritma
Shortest Path. Kedua robot menggunakan komponen Lego Mindstorm NXTTM. Komunikasi
antara dua robot menggunakan protokol bluetooth yang tersedia di Lego Mindstorm NXT.
1.2. Rumusan Masalah
Beberapa hal yang dibahas dalam laporan ini adalah sebagai berikut.
1. Bagaimana penerapan Algoritma Maze Mapping dan Shortest Path serta komunikasi
antar robot menggunakan bluetooth pada Lego Mindstorm NXT?
5
2. Berapa lama waktu yang dibutuhkan oleh Hayate dan Kazetora ketika berkomunikasi
menggunakan bluetooth?
3. Berapa rata-rata waktu tempuh setiap jalur untuk Robot Hayate?
4. Berapa rata-rata waktu tempuh setiap jalur untuk Robot Kazetora?
5. Bagaimana perbandingan waktu tempuh untuk setiap jalur tanpa pengecekan
persimpangan dengan jika melakukan pengecekan persimpangan?
6
BAB II
STUDI LITERATUR
2.1. Locomotion
Sebuah mobile robot membutuhkan mekanisme locomotion untuk bergerak dan
menjelajahi lingkungannya. Ada dua mekanisme utama locomotion pada robot. Yang
pertama adalah legged (kaki) dan yang kedua menggunakan wheel (roda). Robot yang
menggunakan kaki memiliki degree of freedom yang lebih tinggi dibandingkan dengan yang
menggunakan roda. Namun implementasi robot yang mampu bergerak dengan kaki
memiliki tingkat kesulitan yang jauh lebih tinggi daripada roda. Oleh karena itu, roda
menjadi lebih populer dan menjadi pilihan untuk tugas kali ini.
2.1.1. Wheel
Locomotion dengan roda adalah mekanisme locomotion paling populer di bidang mobile
robots. Kelebihannya dibandingkan alternatif lain (kaki) adalah dengan roda kita tidak perlu
memusingkan masalah keseimbangan karena roda memang didesain agar terus menyentuh
tanah. Dengan roda bisa dicapai efisiensi dalam pergerakan dengan menggunakan
implementasi mekanikal yang sederhana.
2.1.1.1. Roda Standar
7
Roda standar memiliki 2 degree of freedom.
2.1.1.2. Roda Castor
Roda Castor juga memiliki 2 degree of freedom, namun terdapat gerakan tambahan berupa
rotasi pada sambungannya dengan badan utama robot.
2.2. Sensor
Salah satu hal kemampuan penting yang harus dimiliki Autonomous Mobile Robot adalah
kemampuan untuk mendeteksi lingkungannya. Hal ini bisa dilakukan dengan perangkat yang
bernama sensor. Sensor dapat digolongkan ke dalam 2 kelompok besar, yaitu
Proprioceptive/Exteroceptive dan Passive/Active Sensor.
Proprioceptive sensor adalah sensor yang mendeteksi atau mengukur keadaan internal dari
robot, seperti suhu prosesor, isi baterai, kecepatan motor, ataupun seperti sensor
gyroscope yang mengukur keseimbangan robot berdasarkan kemiringannya. Exteroceptive
sensor adalah sensor yang mendapatkan informasinya dari lingkungan sekitar robot, seperti
jarak, cahaya, ataupun suara.
Passive sensor adalah sensor yang mengukur energi yang masuk ke sensor dari lingkungan
sekitar. Contohnya seperti temperatur, kamera, atau bahkan nuklir. Active sensor adalah
sensor yang mengirimkan energi ke lingkungan dan kemudian mengukur reaksi dari
lingkungan terhadap energi yang diberikan. Karena bisa mempunyai interaksi lebih, sensor
8
tipe aktif memiliki kelebihan dibanding sensor yang sekedar pasif. Namun hal ini juga bisa
memberikan kerugian seperti apabila energi yang dikirimkan justru mengganggu apa yang
ingin dideteksi, atau jika menggunakan robot lebih dari satu, energi dari robot yang satu bisa
merusak hasil perhitungan robot yang satunya. Setiap sensor memiliki beberapa properti
masing-masing lainnya yang penting untuk diketahui.
2.2.1. Sensor Ultrasonik
Sensor ultrasonic adalah sensor yang bersifat exteroceptive dan aktif. Sensor ultrasonik
mengeluarkan gelombang ultrasonik yang memiliki frekuensi diantara 40 dan 80 kHz. Sensor
ultrasonik ini mampu mengukur jarak 0 sampai dengan 255 centimeter dengan ketelitian +/-
3 centimeter.
2.2.2. Sensor Warna
Sensor warna adalah sensor yang bersifat exteroceptive dan aktif. Sensor ini dapat
membaca intensitas cahaya di suatu ruangan dan mengukur intensitas cahaya dari
permukaan yang warnanya berbeda. Sensor ini memiliki peran yang penting dalam
mendeteksi garis yang diikuti dan mendeteksi persimpangan.
2.2.3. Sensor Sentuh
9
Sensor sentuh bersifat exteroceptive dan pasif. Sensor ini menerima rangsangan fisik berupa
sentuhan dari suatu objek. Ketika sensor ini menerima sentuhan/tekanan, maka tombol
yang berada di sensor ini akan tertekan, kemudian sensor ini akan mengirimkan impuls ke
dalam NXT Brick.
2.2.3. Sensor Suara
Sensor ini bersifat exteroceptive dan pasif. Sensor ini menangkap suara dari lingkungan.
Sensor suara mengukur tingkat volume pada skala 0 (tidak ada suara) hingga 100 (suara
sangat keras). Sensor suara memungkinkan dapat mengukur tingkat kebisingan dalam
satuan dB (desibel) dan dBA (frekuensi sekitar 3-6 kHz dimana telinga manusia berada pada
kondisi paling sensitif), serta mengenali pola suara dan mengidentifikasi perbedaan nada.
10
BAB III
METODE RISET
3.1. Spesifikasi Robot
3.1.1. Robot Hayate
Robot Hayate menggunakan 3 buah roda, yaitu terdiri dari 2 roda yang terhubung dengan
aktuator motor dan 1 roda bebas bertipe castor. Robot menggunakan 4 buah sensor, yaitu
sensor warna RGB, sensor sentuhan, sensor suara, dan sensor ultrasonik. Sensor warna RGB
digunakan untuk mengikuti garis dan mendeteksi persimpangan, sensor sentuhan
digunakan untuk aktivasi robot, dan sensor ultrasonik digunakan untuk mendeteksi posisi
akhir. Sensor suara digunakan pada salah satu skenario, yaitu untuk mendeteksi suara yang
akan membuat robot berhenti sejenak selama beberapa detik dan setelah itu robot kembali
melanjutkan perjalananannya. Berikut adalah gambar Robot Hayate.
3.1.1. Robot Kazetora
Robot Kazetora juga menggunakan 3 buah roda, yaitu terdiri dari 2 roda yang terhubung
dengan aktuator motor dan 1 roda bebas bertipe castor. Robot menggunakan 2 buah
sensor, yaitu sensor warna RGB dan sensor suara. Sensor warna RGB digunakan untuk
mengikuti garis dan mendeteksi persimpangan. Sensor suara digunakan pada salah satu
skenario, yaitu untuk mendeteksi suara yang akan membuat robot berhenti sejenak selama
11
beberapa detik dan setelah itu robot kembali melanjutkan perjalananannya. Berikut adalah
gambar Robot Kazetora.
3.2. Skenario
3.2.1. Skenario 1 (menggunakan Arena Pertama)
Tampilan dari arena pertama yang memiliki ukuran 7 x 5 satuan dapat dilihat pada gambar
berikut.
Cara menyimpan data suatu jalur adalah dengan merepresentasikan jalur sebagai tiga buah
titik yang berurutan, dalam hal ini 3 buah titik yang memiliki nilai yang sama. Misalnya
pemberian nilai 1 jika titik tersebut jalur dan nilai 0 jika tidak terdapat jalur. Sehingga urutan
12
angka 1 1 1 menandakan ada jalur dan 1 0 1 menandakan tidak ada jalur. Maka,
representasi dari arena tersebut setelah Robot menjelajahi semua titik akan seperti matriks
di bawah ini.
1 1 1 0 1 0 0 1 0 1 0 1 0 0 1 1 1 1 1 1 1 0 0 1 0 0 0 0 1 1 1 0 0 0 0
3.2.2. Skenario 2 (menggunakan Arena Kedua)
Tampilan dari arena kedua yang memiliki ukuran 9 x 7 satuan dapat dilihat pada gambar
berikut.
Sama seperti arena pertama, cara menyimpan data suatu jalur adalah dengan
merepresentasikan jalur sebagai tiga buah titik yang berurutan yang memiliki nilai yang
sama. Nilai 1 diberikan jika titik tersebut jalur dan nilai 0 diberikan jika tidak terdapat jalur.
Maka, representasi dari arena tersebut setelah Robot menjelajahi semua titik akan seperti
matriks di bawah ini.
1 0 1 1 1 0 1 1 1 1 0 1 0 0 0 1 0 1 1 1 1 1 1 1 1 0 1 0 0 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 0 1 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 0 0
13
3.2.3. Skenario 3 (Penambahan Sensor Suara)
Skenario 3 dapat menggunakan arena pertama maupun arena kedua, dan dapat dilakukan
pada Robot Hayate maupun Kazetora. Pada skenario ini menambahkan penggunaan sensor
suara. Ketika robot Hayate atau Kazetora sedang berjalan dan tiba-tiba mendeteksi tingkat
suara yang lebih tinggi dari yang ditentukan, robot akan berhenti selama beberapa detik,
dan setelah itu akan kembali meneruskan perjalanan. Skenario ini menggambarkan situasi
nyata ketika tim yang sedang melakukan perjalanan menuju tempat bencana lalu ada
gempa susulan (terdengar suara alarm) maka tim akan berhenti sejenak dan akan
melanjutkan perjalanan kembali setelah tidak ada lagi gempa susulan.
14
BAB IV
HASIL EKSPERIMEN
4.1. Navigasi Robot
4.1.1. Gerakan Maju
Potongan kode program untuk gerakan maju adalah sebagai berikut. public void robot_forward() { int error=0; boolean searchIntersection = true; while(searchIntersection) { while ( isLine() ) { LCD.drawString("isLine ", 0, 0); LCD.refresh(); pilot.forward(); } while ( isOutside() ) { LCD.drawString("isOutside ", 0, 0); LCD.refresh(); error = 5; pilot.rotate(error); if (isOutside()) { error = error * -2; pilot.rotate(error); } } while( isIntersection() ) { LCD.drawString("isIntersection", 0, 0); LCD.refresh(); searchIntersection = false; } } pilot.travel(5); }
15
Gerakan maju ini akan terhenti ketika robot sampai di suatu persimpangan, karena nilai
searchIntersection menjadi false dan program akan keluar dari loop while. Jika robot sedikit
keluar dari garis maka isOutside() akan menghasilkan nilai true yang membuat robot
melakukan koreksi posisi untuk kembali bisa berjalan mengikuti garis.
4.1.2. Fungsi-fungsi Pengecekan dalam Navigasi
Potongan kode program untuk pengecekan-pengecekan dalam navigasi robot adalah
sebagai berikut.
private boolean isOutside() { return readColor() == 6; } private boolean isLine() { int colorVal=0; colorVal = readColor(); return (colorVal!=6 && colorVal!=5) ; } private boolean isIntersection() { return readColor() == 5; } private boolean isFinish() { int i = 0, nearCounter = 0; boolean finish = false; for(i=0; i<4; i++) { if( isNear() ) { nearCounter++; } } if( nearCounter>=2 ) { finish = true; } return finish; }
16
Fungsi isOutside() akan mengembalikan nilai true ketika Robot berada di atas area yang
bukan garis dan bukan persimpangan, yaitu diwakili oleh area berwarna putih pada arena.
Fungsi isLine() akan mengembalikan nilai true jika Robot berada di atas garis yang berwarna
hitam, yang merupakan jalur utama yang dilewati robot. Fungsi isIntersection() akan
mengembalikan nilai true jika Robot berada di persimpangan, yaitu di atas tanda persegi
berwarna merah. Fungsi isFinish()mengembalikan nilai true jika Robot telah mencapai posisi
finish, yaitu posisi yang di atas areanya ditutupi oleh suatu objek sebagai atap sehingga
fungsi isNear() telah bernilai true.
4.1.3. Pembacaan Garis dan Persimpangan
Potongan kode program untuk pembacaan area di bawah robot adalah sebagai berikut.
public int readColor() { int colorVal=0; colorVal = cs.readValue();
return colorVal; // BLACK: 1, RED: 5, WHITE: 6 }
Fungsi readColor() mengembalikan nilai integer yang mengidentifikasi di atas area apa robot
berada. Nilai 1 menandakan robot berada di atas area berwarna hitam (garis), nilai 5
menandakan robot berada di atas area berwarna merah (persimpangan), dan nilai 6
menandakan robot berada di atas area berwarna putih (bukan di garis dan bukan di
persimpangan).
4.1.4. Pendeteksian Posisi Tujuan
Potongan kode program untuk pendeteksian posisi tujuan adalah sebagai berikut.
private boolean isNear() { int distance; distance = ultra.getDistance(); boolean near = false;
17
if(distance<30) { near = true; } return near; }
Fungsi ini bertujuan untuk mengetahui apakah Robot sudah berada pada posisi tujuan atau tidak.
Fungsi isNear() mengembalikan nilai true jika robot sudah mencapai posisi tujuan. Posisi
tujuan dikenali dengan cara area tersebut ditutupi oleh suatu objek sebagai atap sehingga
hasil pembacaan jarak yang dipancarkan ke arah atas akan menghasilkan nilai yang kecil
(jaraknya dekat).
4.1.5. Mendeteksi Suara yang Cukup Keras
Potongan kode program untuk mendeteksi suara yang cukup keras adalah sebagai berikut.
private boolean isLoud() { int loudness; loudness = sound.readValue(); boolean loud = false; LCD.drawInt(loudness, 0, 2); LCD.refresh(); if(loudness>65) { loud = true; } return loud; }
Fungsi isLoud() akan mengembalikan nilai true ketika kondisi di sekitar robot cukup bising,
dalam hal ini robot mendeteksi tingkat kebisingan di atas nilai 65%.
18
4.2. Maze Mapping
Penjelajahan jalur-jalur pada maze menggunakan Algoritma Maze Mapping. Cara yang
digunakan adalah dengan menentukan prinsip pemilihan jalur ke kanan. Algoritma ini
menyatakan dengan selalu belok ke kanan di setiap persimpangan, maka jika maze tersebut
terkoneksi seluruhnya dan memiliki solusi, maka suatu saat pasti akan sampai kepada solusi.
Data kondisi ketersediaan jalur di arah kanan, kiri dan depan akan disimpan oleh Robot.
Data yang tersimpan akan memberikan informasi jalur-jalur yang menghubungkan posisi
awal dengan posisi tujuan. Akan tetapi dengan menggunakan prinsip pemilihan jalur ke
kanan, belum mendapatkan informasi jalur terpendek dari maze. Untuk itu, Hayate
menerapkan sebuah algoritma depth first search dengan implementasinya menggunakan
stack.
4.3. Shortest Path
Algoritma Shortest Path yang diimplementasikan cukup sederhana, yaitu dengan
menyimpan semua kemungkinan jalur-jalur daru posisi awal ke posisi tujuan. Dari setiap
kemungkinan jalur tersebut, kemudian dihitung jumlah langkah total dari posisi awal ke
posisi tujuan. Pada akhirnya dilakukan pencarian nilai yang terkecil yang berarti jalur
tersebut merupakan jalur terpendek dari posisi awal ke posisi tujuan.
4.4. Communication
Komunikasi antara Hayate dengan Kazetora dilakukan melalui protokol Bluetooth. Bluetooth
beroperasi pada frekuensi 2.4 hingga 2.485 Gigahertz. Di banyak negara, frekuensi ini tidak
dilisensi dan memang dibuka secara luas untuk dipakai. Semua mekanisme untuk melakukan
sambungan bluetooth sudah disediakan oleh LejosTM, terutama dari package
lejos.nxt.comm. Kedua robot sebelumnya sudah pernah dipasangkan (pairing), sehingga di
dalam kode cukup dipanggil nama dari robot yang ingin dihubungkan tanpa perlu
mekanisme untuk perkenalan terlebih dahulu. Bagian selanjutnya akan menjelaskan tahap-
tahap komunikasi bluetooth antara dua robot.
19
4.4.1. Menemukan Device
Untuk mengetahui device apa saja yang sudah dikenal oleh suatu NXT Brick, bisa dilakukan
dengan menggunakan kode program di bawah ini.
Potongan kode tersebut berguna untuk mengeluarkan daftar dari semua device yang sudah
dikenal dan kemudian menampilkannya ke layar NXT. Apabila belum ada device yang
dikenal, maka diperlukan proses inquire untuk menemukan device bluetooth lainnya.
Method Bluetooth.inquire akan mencari device bluetooth yang tersedia pada jangkauan.
Device yang ditemukan kemudian akan dimasukkan ke dalam daftar.
Setelah ditemukan, untuk melakukan sambungan maka device tersebut perlu ditambahkan
ke dalam daftar device yang dikenal oleh NXT seperti tampak pada kode di atas.
20
4.4.2. Inisiasi Sambungan Antar Device
Setelah ada device yang ditemukan, tahap selanjutnya adalah melakukan sambungan.
Jika device sudah dikenal sebelumnya, cukup dilakukan dengan memanggil namanya.
Setelah objek berhasil didapat, maka koneksi bisa dimulai dengan menggunakan method
connect di kelas Bluetooth.
Jika device tersebut membutuhkan PIN untuk koneksi, maka pin harus disediakan terlebih
dahulu sebelum melakukan sambungan.
4.4.3. Menyiapkan Pertukaran Data Antar Device
Cara untuk melakukan pertukaran data antar device adalah dengan menggunakan
DataInputStream dan DataOutputStream seperti dicontohkan oleh kode di bawah.
DataInputStream dis = btc.openDataInputStream();
DataOutputStream dos = btc.openDataOutputStream();
21
DataInputStream berguna untuk menerima data yang dikirim dan DataOutputStream
berguna untuk mengirim data ke device lain.
4.4.4. Kazetora Menunggu Sambungan dari Hayate
Untuk menunggu koneksi bluetooth dari device lain dapat dilakukan dengan cara di bawah
ini.
NXT brick akan menunggu sampai mendapat sambungan dari device lain.
Kazetora adalah robot kedua dari pasangan Fukushi Fighter ini. Kazetora bertugas untuk
menerima sambungan koneksi dari Hayate melalui Bluetooth yang berisi rute jalur
terpendek dari maze yang akan ditelusuri. Berdasarkan pesan yang diterimanya, maka
Kazetora akan menjelajahi maze sesuai petunjuk yang diberikan.
Dari setelah dinyalakan, Kazetora akan menunggu koneksi Bluetooth dari Hayate melalui
kode pada baris ke 60 di atas. Selama menunggu, Kazetora tidak bergerak (idle).
4.4.4. Hayate Mengirimkan Data ke Kazetora
Berikut adalah tampilan potongan kode ketika Hayate mengirimkan data ke Kazetora: for (int i = 0; i < clue.size(); i++) {
int a = clue.get(i);
LCD.drawString("Sending: "+a, 0, 5);
dos.writeInt(a);
dos.flush();
}
dos.writeInt(8);
dos.flush();
dos.close();
22
4.4.5. Kazetora Menerima Sambungan dari Hayate
Begitu mendapatkan sambungan Bluetooth, maka Kazetora akan memanggil objek
DataInputStream yang merupakan objek yang mengatur pembacaan stream data yang
dikirim oleh Hayate. Kelas DataInputStream merupakan bagian dari package java.io.
4.4.6. Kazetora Menerima Data dari Hayate
Pesan yang dikirim oleh Hayate di encode menjadi potongan-potongan angka. Angka-angka
itu dibaca terus sampai sebuah karakter sentinel yang disepakati, di sini yang dipakai adalah
angka ‘8’. Diluar itu, angka yang dikirim adalah kode rute mana yang harus diambil Kazetora
ketika menemui persimpangan.
‘1’ untuk maju terus, ‘2’ untuk belok kanan, dan ‘3’ untuk belok kiri.
Begitu data sudah selesai didapat, Kazetora menutup koneksinya dan kemudian
menjalankan method untuk memulai penjelajahan maze dengan petunjuk yang sudah
diterima.
23
Method jalan adalah method untuk menelusuri maze dengan petunjuk yang diberikan pada
argumennya.
Method ini alur utamanya adalah melakukan iterasi sebanyak petunjuk arah yang diberikan,
yang berarti sebanyak persimpangan yang akan ditemukan sepanjang menelusuri maze dari
awal sampai akhir.
Sesuai kode, jika Kazetora menemukan persimpangan, dan petunjuk arah adalah angka ‘2’,
maka Kazetora akan belok ke kanan, sedangkan jika petunjuk arahnya adalah angka ‘3’,
maka dia akan belok kiri. Selain itu, dia akan berjalan lurus.
Ketika sedang tidak menemui simpangan, maka algoritma yang berjalan adalah algoritma
line following yang sama dengan yang dipakai oleh Hayate.
24
4.5. Hasil Eksperimen
4.5.1. Hasil Eksperimen I
Berikut adalah tampilan langkah-langkah pada arena pertama:
1. Kondisi awal robot dan arena
2. Pengecekan rutin ketersediaan jalur ke arah kanan oleh Hayate
3. Pengecekan rutin ketersediaan jalur ke arah depan oleh Hayate
25
4. Pengecekan rutin ketersediaan jalur ke arah kiri oleh Hayate
5. Hayate mencapai kondisi dead-end pertama dan kembali ke persimpangan terakhir yang dilalui (back-track)
6. Hayate mencapai kondisi dead-end kedua dan kembali ke persimpangan terakhir yang dilalui (back-track)
26
7. Hayate menemukan solusi pertama
8. Setelah menemukan solusi pertama Hayate kembali mencari alternatif jalur yang lain
9. Hayate menemukan solusi kedua dan sudah tidak ada lagi alternatif jalur yang lain
27
10. Hayate bergerak maju memberi ruang dan bersiap untuk mengirimkan data
11. Hayate mengirimkan data ke Kazetora
12. Kazetora menerima data
28
13. Kazetora mulai bergerak, pada persimpangan pertama langsung memilih arah ke kanan
14. Kazetora mulai bergerak, pada persimpangan kedua langsung memilih arah ke kanan
15. Kazetora berhasil mencapai tujuan akhir
29
Catatan-catatan waktu:
a. Waktu yang dibutuhkan oleh Hayate menemukan solusi pertama (baik solusi tersebut
jalur terpendek atau bukan): 2 menit 11 detik = 131 detik.
b. Waktu yang dibutuhkan oleh Hayate untuk menjelajahi semua kemungkinan jalur: 3
menit 14 detik = 194 detik. Total jalur yang ditempuh adalah 14 satuan jalur. Rata-rata
waktu tempuh untuk setiap jalur adalah: 194 detik/14 satuan jalur = 13.86 detik/satuan
jalur.
c. Waktu yang dibutuhkan oleh Hayate dan Kazetora untuk pengaktifkaan sambungan dan
pengiriman-penerimaan data: 8 detik.
d. Waktu yang dibutuhkan oleh Kazetora untuk mencapai daerah tujuan: 21 detik. Total
jalur yang ditempuh adalah 4 satuan jalur. Rata-rata waktu tempuh untuk setiap jalur
adalah: 21 detik/4 satuan jalur = 5.25 detik/satuan jalur.
e. Total waktu yang dibutuhkan: 3 menit 51 detik = 231 detik.
f. Perbedaan rata-rata waktu tempuh untuk setiap jalur adalah 13.86 (Hayate, ada
pengecekan persimpangan) – 5.25 (Kazetora, tanpa pengecekan persimpangan) = 8.61
detik. Perbandingan waktu 13.86 / 5.25 = 2.64 menggambarkan bahwa waktu tempuh untuk
setiap jalur tanpa pengecekan persimpangan 2.64 kali lebih cepat dibandingkan jika
melakukan pengecekan persimpangan.
30
4.5.2. Hasil Eksperimen II
Berikut adalah tampilan langkah-langkah pada arena kedua:
1. Kondisi awal robot dan arena
2. Pengecekan rutin ketersediaan jalur ke arah kanan oleh Hayate
3. Pengecekan rutin ketersediaan jalur ke arah depan oleh Hayate
31
4. Pengecekan rutin ketersediaan jalur ke arah kiri oleh Hayate
5. Hayate mencapai kondisi dead-end pertama dan kembali ke persimpangan terakhir yang dilalui (back-track)
6. Hayate menemukan solusi pertama
32
7. Setelah menemukan solusi pertama Hayate kembali mencari alternatif jalur yang lain
8. Hayate menemukan solusi kedua dan menganggap tidak mungkin ada lagi jalur yang lebih pendek
9. Hayate bergerak maju memberi ruang dan bersiap untuk mengirimkan data
33
10. Hayate mengirimkan data ke Kazetora
11. Kazetora menerima data
12. Kazetora mulai bergerak, pada persimpangan pertama langsung memilih arah ke depan
34
13. Kazetora mulai bergerak, pada persimpangan kedua langsung memilih arah ke kanan
14. Kazetora mulai bergerak, pada persimpangan ketiga langsung memilih arah ke kiri
15. Kazetora berhasil mencapai tujuan akhir
35
Catatan-catatan waktu:
a. Waktu yang dibutuhkan oleh Hayate menemukan solusi pertama (baik solusi tersebut
jalur terpendek atau bukan): 2 menit 2 detik = 122 detik.
b. Waktu yang dibutuhkan oleh Hayate untuk menjelajahi semua kemungkinan jalur: 3
menit 3 detik = 183 detik. Total jalur yang ditempuh adalah 18 satuan jalur. Rata-rata waktu
tempuh untuk setiap jalur adalah: 183 detik/18 satuan jalur = 10.16 detik/satuan jalur.
c. Waktu yang dibutuhkan oleh Hayate dan Kazetora untuk pengaktifkaan sambungan dan
pengiriman-penerimaan data: 8 detik.
d. Waktu yang dibutuhkan oleh Kazetora untuk mencapai daerah tujuan: 23 detik. Total
jalur yang ditempuh adalah 6 satuan jalur. Rata-rata waktu tempuh untuk setiap jalur
adalah: 23 detik/6 satuan jalur = 3.83 detik/satuan jalur.
e. Total waktu yang dibutuhkan: 3 menit 39 detik = 219 detik.
f. Perbedaan rata-rata waktu tempuh untuk setiap jalur adalah 10.16 (Hayate, ada
pengecekan persimpangan) – 3.83 (Kazetora, tanpa pengecekan persimpangan) = 6.33
detik. Perbandingan waktu 10.16 / 3.83 = 2.65 menggambarkan bahwa waktu tempuh untuk
setiap jalur tanpa pengecekan persimpangan 2.65 kali lebih cepat dibandingkan jika
melakukan pengecekan persimpangan.
36
4.5.3. Hasil Eksperimen III
Tampilan ketika Robot Hayate mendeteksi adanya suara yang lebih keras. Robot kemudian
berhenti sejenak selama beberapa detik.
Tampilan ketika Robot Hayate kembali melanjutkan perjalanan setelah berhenti.
Tampilan ketika Robot Kazetora mendeteksi adanya suara yang lebih keras. Robot kemudian
berhenti sejenak selama beberapa detik.
37
Tampilan ketika Robot Kazetora kembali melanjutkan perjalanan setelah berhenti.
38
BAB V
KESIMPULAN
5.1. Kesimpulan
Kesimpulan yang dapat diperoleh dari Hasil Eksperimen adalah:
a. Penerapan Algoritma Maze Mapping dan Shortest Path serta komunikasi antar robot
menggunakan bluetooth dapat diterapkan pada Lego Mindstorm NXT.
b. Waktu yang dibutuhkan oleh Hayate dan Kazetora untuk pengaktifkaan sambungan dan
pengiriman-penerimaan data adalah 8 detik baik pada arena pertama maupun kedua.
c. Rata-rata waktu tempuh setiap jalur untuk Hayate adalah 13.86 detik/satuan jalur pada
arena pertama dan 10.16 detik/satuan jalur pada arena kedua.
d. Rata-rata waktu tempuh setiap jalur untuk Kazetora adalah 5.25 detik/satuan jalur pada
arena pertama dan 3.83 detik/satuan jalur pada arena kedua.
f. Waktu tempuh untuk setiap jalur tanpa pengecekan persimpangan (Robot sudah
mengetahui mana jalur yang harus diambil) dibandingkan jika melakukan pengecekan
persimpangan (Robot belum mengetahui mana jalur yang harus diambil) adalah 2.64 kali
lebih cepat pada arena pertama dan 2.65 kali lebih cepat pada arena kedua.
39
DAFTAR PUSTAKA Lego Mindstorm NXT Product. Tersedia: http://mindstorms.lego.com/en-us/Products/default.aspx Lejos API. Tersedia: http://lejos.sourceforge.net/nxt/nxj/api/
Siegwart R., & Nourbakhsh, I.R. 2004. Introduction to Autonomous Mobile Robots. London:
MIT Press. Wisnu J, et al. 2009. Robot LEGO Mindstroms: Teori dan Praktek. Depok: Fakultas Ilmu
Komputer Universitas Indonesia.
40
LAMPIRAN
1. Ouput Hasil Running Program untuk Arena Pertama
----------------- 1 2 3 4 5 6 7 8 9 ----------------- 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ----------------- --- new state --- | current pos (Y, X): (0, 4) checking y= 0 and x= 3 | checking y= 1 and x= 4 | Data[1][4] is true A way found to forward. Maze was updated. checking y= 0 and x= 5 | Top Of Stack is: 1 ---stack values[0]: 12 0 4 8 nextMove is 12, from (0, 4) | move to direction 8, (moveForward) ----------------- 1 2 3 4 5 6 7 8 9 ----------------- 0 0 0 0 2 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ----------------- --- new state --- | current pos (Y, X): (1, 4) checking y= 1 and x= 3 | checking y= 2 and x= 4 | Data[2][4] is true A way found to forward. Maze was updated. checking y= 1 and x= 5 | Top Of Stack is: 1 ---stack values[0]: 12 1 4 8 nextMove is 12, from (1, 4) | move to direction 8, (moveForward) ----------------- 1 2 3 4 5 6 7 8 9 ----------------- 0 0 0 0 2 0 0
41
0 0 0 0 2 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ----------------- --- new state --- | current pos (Y, X): (2, 4) checking y= 2 and x= 3 | Data[2][3] is true A way found to the right. Maze was updated. checking y= 3 and x= 4 | checking y= 2 and x= 5 | Data[2][5] is true A way found to the left. Maze was updated. Top Of Stack is: 2 ---stack values[0]: 11 2 4 8 ---stack values[1]: 13 2 4 8 nextMove is 13, from (2, 4) | move to direction 2, (moveLeft) ----------------- 1 2 3 4 5 6 7 8 9 ----------------- 0 0 0 0 2 0 0 0 0 0 0 2 0 0 0 0 0 1 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ----------------- --- new state --- | current pos (Y, X): (2, 5) checking y= 3 and x= 5 | checking y= 2 and x= 6 | Data[2][6] is true A way found to forward. Maze was updated. checking y= 1 and x= 5 | Top Of Stack is: 2 ---stack values[0]: 11 2 4 8 ---stack values[1]: 12 2 5 2 nextMove is 12, from (2, 5) | move to direction 2, (moveForward) ----------------- 1 2 3 4 5 6 7 8 9 ----------------- 0 0 0 0 2 0 0 0 0 0 0 2 0 0 0 0 0 1 2 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ----------------- --- new state --- | current pos (Y, X): (2, 6)
42
checking y= 3 and x= 6 | checking y= 1 and x= 6 | Top Of Stack is: 1 ---stack values[0]: 11 2 4 8 Dead-end. nextMove is 12, from (2, 6). Dir: 4 | --- backtrack state --- | current pos (Y, X): (2, 6) move to direction 4, (moveForward) ----------------- 1 2 3 4 5 6 7 8 9 ----------------- 0 0 0 0 2 0 0 0 0 0 0 2 0 0 0 0 0 1 2 2 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ----------------- nextMove is 11, from (2, 5). Dir: 4 | --- backtrack state --- | current pos (Y, X): (2, 5) move to direction 1, (moveRight) ----------------- 1 2 3 4 5 6 7 8 9 ----------------- 0 0 0 0 2 0 0 0 0 0 0 2 0 0 0 0 0 1 2 3 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ----------------- nextMove is 11, from (2, 4). Dir: 8 | move to direction 4, (moveRight) ----------------- 1 2 3 4 5 6 7 8 9 ----------------- 0 0 0 0 2 0 0 0 0 0 0 2 0 0 0 0 0 1 2 3 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ----------------- --- new state --- | current pos (Y, X): (2, 3) checking y= 1 and x= 3 | checking y= 2 and x= 2 | Data[2][2] is true A way found to forward. Maze was updated. checking y= 3 and x= 3 | Top Of Stack is: 1 ---stack values[0]: 12 2 3 4 nextMove is 12, from (2, 3) | move to direction 4, (moveForward)
43
----------------- 1 2 3 4 5 6 7 8 9 ----------------- 0 0 0 0 2 0 0 0 0 0 0 2 0 0 0 0 1 2 2 3 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ----------------- --- new state --- | current pos (Y, X): (2, 2) checking y= 1 and x= 2 | Data[1][2] is true A way found to the right. Maze was updated. checking y= 2 and x= 1 | Data[2][1] is true A way found to forward. Maze was updated. checking y= 3 and x= 2 | Data[3][2] is true A way found to the left. Maze was updated. Top Of Stack is: 3 ---stack values[0]: 11 2 2 4 ---stack values[1]: 12 2 2 4 ---stack values[2]: 13 2 2 4 nextMove is 13, from (2, 2) | move to direction 8, (moveLeft) ----------------- 1 2 3 4 5 6 7 8 9 ----------------- 0 0 0 0 2 0 0 0 0 1 0 2 0 0 0 1 2 2 2 3 3 0 0 1 0 0 0 0 0 0 0 0 0 0 0 ----------------- --- new state --- | current pos (Y, X): (3, 2) checking y= 3 and x= 1 | checking y= 4 and x= 2 | Data[4][2] is true A way found to forward. Maze was updated. checking y= 3 and x= 3 | Top Of Stack is: 3 ---stack values[0]: 11 2 2 4 ---stack values[1]: 12 2 2 4 ---stack values[2]: 12 3 2 8 nextMove is 12, from (3, 2) | move to direction 8, (moveForward) ----------------- 1 2 3 4 5 6 7 8 9 -----------------
44
0 0 0 0 2 0 0 0 0 1 0 2 0 0 0 1 2 2 2 3 3 0 0 2 0 0 0 0 0 0 1 0 0 0 0 ----------------- --- new state --- | current pos (Y, X): (4, 2) checking y= 4 and x= 1 | Data[4][1] is true A way found to the right. Maze was updated. checking y= 4 and x= 3 | Top Of Stack is: 3 ---stack values[0]: 11 2 2 4 ---stack values[1]: 12 2 2 4 ---stack values[2]: 11 4 2 8 nextMove is 11, from (4, 2) | move to direction 4, (moveRight) ----------------- 1 2 3 4 5 6 7 8 9 ----------------- 0 0 0 0 2 0 0 0 0 1 0 2 0 0 0 1 2 2 2 3 3 0 0 2 0 0 0 0 0 1 2 0 0 0 0 ----------------- --- new state --- | current pos (Y, X): (4, 1) checking y= 3 and x= 1 | checking y= 4 and x= 0 | Data[4][0] is true A way found to forward. Maze was updated. Top Of Stack is: 3 ---stack values[0]: 11 2 2 4 ---stack values[1]: 12 2 2 4 ---stack values[2]: 12 4 1 4 nextMove is 12, from (4, 1) | move to direction 4, (moveForward) ----------------- 1 2 3 4 5 6 7 8 9 ----------------- 0 0 0 0 2 0 0 0 0 1 0 2 0 0 0 1 2 2 2 3 3 0 0 2 0 0 0 0 1 2 2 0 0 0 0 -----------------
45
--- new state --- | current pos (Y, X): (4, 0) checking y= 3 and x= 0 | Top Of Stack is: 2 ---stack values[0]: 11 2 2 4 ---stack values[1]: 12 2 2 4 Dead-end. nextMove is 12, from (4, 0). Dir: 2 | --- backtrack state --- | current pos (Y, X): (4, 0) move to direction 2, (moveForward) ----------------- 1 2 3 4 5 6 7 8 9 ----------------- 0 0 0 0 2 0 0 0 0 1 0 2 0 0 0 1 2 2 2 3 3 0 0 2 0 0 0 0 3 2 2 0 0 0 0 ----------------- nextMove is 13, from (4, 1). Dir: 2 | --- backtrack state --- | current pos (Y, X): (4, 1) move to direction 1, (moveLeft) ----------------- 1 2 3 4 5 6 7 8 9 ----------------- 0 0 0 0 2 0 0 0 0 1 0 2 0 0 0 1 2 2 2 3 3 0 0 2 0 0 0 0 3 3 2 0 0 0 0 ----------------- nextMove is 12, from (4, 2). Dir: 1 | --- backtrack state --- | current pos (Y, X): (4, 2) move to direction 1, (moveForward) ----------------- 1 2 3 4 5 6 7 8 9 ----------------- 0 0 0 0 2 0 0 0 0 1 0 2 0 0 0 1 2 2 2 3 3 0 0 2 0 0 0 0 3 3 3 0 0 0 0 ----------------- nextMove is 11, from (3, 2). Dir: 1 | --- backtrack state --- | current pos (Y, X): (3, 2) move to direction 2, (moveRight) ----------------- 1 2 3 4 5 6 7 8 9
46
----------------- 0 0 0 0 2 0 0 0 0 1 0 2 0 0 0 1 2 2 2 3 3 0 0 3 0 0 0 0 3 3 3 0 0 0 0 ----------------- nextMove is 12, from (2, 2). Dir: 4 | move to direction 4, (moveForward) ----------------- 1 2 3 4 5 6 7 8 9 ----------------- 0 0 0 0 2 0 0 0 0 1 0 2 0 0 0 1 2 2 2 3 3 0 0 3 0 0 0 0 3 3 3 0 0 0 0 ----------------- --- new state --- | current pos (Y, X): (2, 1) checking y= 1 and x= 1 | checking y= 2 and x= 0 | Data[2][0] is true A way found to forward. Maze was updated. checking y= 3 and x= 1 | Top Of Stack is: 2 ---stack values[0]: 11 2 2 4 ---stack values[1]: 12 2 1 4 nextMove is 12, from (2, 1) | move to direction 4, (moveForward) ----------------- 1 2 3 4 5 6 7 8 9 ----------------- 0 0 0 0 2 0 0 0 0 1 0 2 0 0 1 2 2 2 2 3 3 0 0 3 0 0 0 0 3 3 3 0 0 0 0 ----------------- --- new state --- | current pos (Y, X): (2, 0) checking y= 1 and x= 0 | Data[1][0] is true A way found to the right. Maze was updated. checking y= 3 and x= 0 | Top Of Stack is: 2 ---stack values[0]: 11 2 2 4 ---stack values[1]: 11 2 0 4 nextMove is 11, from (2, 0) | move to direction 1, (moveRight) -----------------
47
1 2 3 4 5 6 7 8 9 ----------------- 0 0 0 0 2 0 0 1 0 1 0 2 0 0 2 2 2 2 2 3 3 0 0 3 0 0 0 0 3 3 3 0 0 0 0 ----------------- --- new state --- | current pos (Y, X): (1, 0) checking y= 1 and x= 1 | checking y= 0 and x= 0 | Top Of Stack is: 1 ---stack values[0]: 11 2 2 4 Solution Found. nextMove is 13, from (1, 0). Dir: 8 | --- backtrack state --- | current pos (Y, X): (1, 0) move to direction 2, (moveLeft) ----------------- 1 2 3 4 5 6 7 8 9 ----------------- 0 0 0 0 2 0 0 3 0 1 0 2 0 0 2 2 2 2 2 3 3 0 0 3 0 0 0 0 3 3 3 0 0 0 0 ----------------- nextMove is 12, from (2, 0). Dir: 2 | --- backtrack state --- | current pos (Y, X): (2, 0) move to direction 2, (moveForward) ----------------- 1 2 3 4 5 6 7 8 9 ----------------- 0 0 0 0 2 0 0 3 0 1 0 2 0 0 3 2 2 2 2 3 3 0 0 3 0 0 0 0 3 3 3 0 0 0 0 ----------------- nextMove is 11, from (2, 2). Dir: 4 | move to direction 1, (moveRight) ----------------- 1 2 3 4 5 6 7 8 9 ----------------- 0 0 0 0 2 0 0 3 0 1 0 2 0 0 3 2 2 2 2 3 3 0 0 3 0 0 0 0 3 3 3 0 0 0 0
48
----------------- --- new state --- | current pos (Y, X): (1, 2) checking y= 1 and x= 3 | checking y= 0 and x= 2 | Data[0][2] is true A way found to forward. Maze was updated. checking y= 1 and x= 1 | Top Of Stack is: 1 ---stack values[0]: 12 1 2 1 nextMove is 12, from (1, 2) | move to direction 1, (moveForward) ----------------- 1 2 3 4 5 6 7 8 9 ----------------- 0 0 1 0 2 0 0 3 0 2 0 2 0 0 3 2 2 2 2 3 3 0 0 3 0 0 0 0 3 3 3 0 0 0 0 ----------------- --- new state --- | current pos (Y, X): (0, 2) checking y= 0 and x= 3 | checking y= 0 and x= 1 | Data[0][1] is true A way found to the left. Maze was updated. Top Of Stack is: 1 ---stack values[0]: 13 0 2 1 nextMove is 13, from (0, 2) | move to direction 4, (moveLeft) ----------------- 1 2 3 4 5 6 7 8 9 ----------------- 0 1 2 0 2 0 0 3 0 2 0 2 0 0 3 2 2 2 2 3 3 0 0 3 0 0 0 0 3 3 3 0 0 0 0 ----------------- --- new state --- | current pos (Y, X): (0, 1) checking y= 0 and x= 0 | checking y= 1 and x= 1 | Top Of Stack is: 0 Solution Found. All area is explored succesfully. Maze 0 1 2 0 2 0 0
49
3 0 2 0 2 0 0 3 2 2 2 2 3 3 0 0 3 0 0 0 0 3 3 3 0 0 0 0 Finding shortest path.. Position of source(x: 0 ,y: 4) Position of Destination(x: 0 ,y: 0) (0, 4) -> (1, 4) -> (2, 4) -> (2, 3) -> (2, 2) -> (1, 2) -> (0, 2) -> (0, 1) -> (0, 0)
50
2. Ouput Hasil Running Program Untuk Arena Kedua
----------------- 1 2 3 4 5 6 7 8 9 ----------------- 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ----------------- --- new state --- | current pos (Y, X): (0, 0) checking y= 1 and x= 0 | Data[1][0] is true A way found to forward. Maze was updated. checking y= 0 and x= 1 | Top Of Stack is: 1 ---stack values[0]: 12 0 0 8 nextMove is 12, from (0, 0) | move to direction 8, (moveForward) ----------------- 1 2 3 4 5 6 7 8 9 ----------------- 2 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ----------------- --- new state --- | current pos (Y, X): (1, 0) checking y= 2 and x= 0 | Data[2][0] is true A way found to forward. Maze was updated. checking y= 1 and x= 1 | Top Of Stack is: 1 ---stack values[0]: 12 1 0 8 nextMove is 12, from (1, 0) | move to direction 8, (moveForward) ----------------- 1 2 3 4 5 6 7 8 9 ----------------- 2 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0
51
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ----------------- --- new state --- | current pos (Y, X): (2, 0) checking y= 3 and x= 0 | checking y= 2 and x= 1 | Data[2][1] is true A way found to the left. Maze was updated. Top Of Stack is: 1 ---stack values[0]: 13 2 0 8 nextMove is 13, from (2, 0) | move to direction 2, (moveLeft) ----------------- 1 2 3 4 5 6 7 8 9 ----------------- 2 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ----------------- --- new state --- | current pos (Y, X): (2, 1) checking y= 3 and x= 1 | checking y= 2 and x= 2 | Data[2][2] is true A way found to forward. Maze was updated. checking y= 1 and x= 1 | Top Of Stack is: 1 ---stack values[0]: 12 2 1 2 nextMove is 12, from (2, 1) | move to direction 2, (moveForward) ----------------- 1 2 3 4 5 6 7 8 9 ----------------- 2 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 2 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -----------------
52
--- new state --- | current pos (Y, X): (2, 2) checking y= 3 and x= 2 | Data[3][2] is true A way found to the right. Maze was updated. checking y= 2 and x= 3 | Data[2][3] is true A way found to forward. Maze was updated. checking y= 1 and x= 2 | Data[1][2] is true A way found to the left. Maze was updated. Top Of Stack is: 3 ---stack values[0]: 11 2 2 2 ---stack values[1]: 12 2 2 2 ---stack values[2]: 13 2 2 2 nextMove is 13, from (2, 2) | move to direction 1, (moveLeft) ----------------- 1 2 3 4 5 6 7 8 9 ----------------- 2 0 0 0 0 0 0 0 0 2 0 1 0 0 0 0 0 0 2 2 2 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ----------------- --- new state --- | current pos (Y, X): (1, 2) checking y= 1 and x= 3 | checking y= 0 and x= 2 | Data[0][2] is true A way found to forward. Maze was updated. checking y= 1 and x= 1 | Top Of Stack is: 3 ---stack values[0]: 11 2 2 2 ---stack values[1]: 12 2 2 2 ---stack values[2]: 12 1 2 1 nextMove is 12, from (1, 2) | move to direction 1, (moveForward) ----------------- 1 2 3 4 5 6 7 8 9 ----------------- 2 0 1 0 0 0 0 0 0 2 0 2 0 0 0 0 0 0 2 2 2 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -----------------
53
--- new state --- | current pos (Y, X): (0, 2) checking y= 0 and x= 3 | Data[0][3] is true A way found to the right. Maze was updated. checking y= 0 and x= 1 | Top Of Stack is: 3 ---stack values[0]: 11 2 2 2 ---stack values[1]: 12 2 2 2 ---stack values[2]: 11 0 2 1 nextMove is 11, from (0, 2) | move to direction 2, (moveRight) ----------------- 1 2 3 4 5 6 7 8 9 ----------------- 2 0 2 1 0 0 0 0 0 2 0 2 0 0 0 0 0 0 2 2 2 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ----------------- --- new state --- | current pos (Y, X): (0, 3) checking y= 1 and x= 3 | checking y= 0 and x= 4 | Data[0][4] is true A way found to forward. Maze was updated. Top Of Stack is: 3 ---stack values[0]: 11 2 2 2 ---stack values[1]: 12 2 2 2 ---stack values[2]: 12 0 3 2 nextMove is 12, from (0, 3) | move to direction 2, (moveForward) ----------------- 1 2 3 4 5 6 7 8 9 ----------------- 2 0 2 2 1 0 0 0 0 2 0 2 0 0 0 0 0 0 2 2 2 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ----------------- --- new state --- | current pos (Y, X): (0, 4) checking y= 1 and x= 4 | checking y= 0 and x= 5 |
54
Top Of Stack is: 2 ---stack values[0]: 11 2 2 2 ---stack values[1]: 12 2 2 2 Dead-end. nextMove is 12, from (0, 4). Dir: 4 | --- backtrack state --- | current pos (Y, X): (0, 4) move to direction 4, (moveForward) ----------------- 1 2 3 4 5 6 7 8 9 ----------------- 2 0 2 2 3 0 0 0 0 2 0 2 0 0 0 0 0 0 2 2 2 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ----------------- nextMove is 13, from (0, 3). Dir: 4 | --- backtrack state --- | current pos (Y, X): (0, 3) move to direction 8, (moveLeft) ----------------- 1 2 3 4 5 6 7 8 9 ----------------- 2 0 2 3 3 0 0 0 0 2 0 2 0 0 0 0 0 0 2 2 2 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ----------------- nextMove is 12, from (0, 2). Dir: 8 | --- backtrack state --- | current pos (Y, X): (0, 2) move to direction 8, (moveForward) ----------------- 1 2 3 4 5 6 7 8 9 ----------------- 2 0 3 3 3 0 0 0 0 2 0 2 0 0 0 0 0 0 2 2 2 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ----------------- nextMove is 11, from (1, 2). Dir: 8 |
55
--- backtrack state --- | current pos (Y, X): (1, 2) move to direction 4, (moveRight) ----------------- 1 2 3 4 5 6 7 8 9 ----------------- 2 0 3 3 3 0 0 0 0 2 0 3 0 0 0 0 0 0 2 2 2 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ----------------- nextMove is 12, from (2, 2). Dir: 2 | move to direction 2, (moveForward) ----------------- 1 2 3 4 5 6 7 8 9 ----------------- 2 0 3 3 3 0 0 0 0 2 0 3 0 0 0 0 0 0 2 2 2 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ----------------- --- new state --- | current pos (Y, X): (2, 3) checking y= 3 and x= 3 | checking y= 2 and x= 4 | Data[2][4] is true A way found to forward. Maze was updated. checking y= 1 and x= 3 | Top Of Stack is: 2 ---stack values[0]: 11 2 2 2 ---stack values[1]: 12 2 3 2 nextMove is 12, from (2, 3) | move to direction 2, (moveForward) ----------------- 1 2 3 4 5 6 7 8 9 ----------------- 2 0 3 3 3 0 0 0 0 2 0 3 0 0 0 0 0 0 2 2 2 2 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -----------------
56
--- new state --- | current pos (Y, X): (2, 4) checking y= 3 and x= 4 | checking y= 2 and x= 5 | Data[2][5] is true A way found to forward. Maze was updated. checking y= 1 and x= 4 | Top Of Stack is: 2 ---stack values[0]: 11 2 2 2 ---stack values[1]: 12 2 4 2 nextMove is 12, from (2, 4) | move to direction 2, (moveForward) ----------------- 1 2 3 4 5 6 7 8 9 ----------------- 2 0 3 3 3 0 0 0 0 2 0 3 0 0 0 0 0 0 2 2 2 2 2 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ----------------- --- new state --- | current pos (Y, X): (2, 5) checking y= 3 and x= 5 | checking y= 2 and x= 6 | Data[2][6] is true A way found to forward. Maze was updated. checking y= 1 and x= 5 | Top Of Stack is: 2 ---stack values[0]: 11 2 2 2 ---stack values[1]: 12 2 5 2 nextMove is 12, from (2, 5) | move to direction 2, (moveForward) ----------------- 1 2 3 4 5 6 7 8 9 ----------------- 2 0 3 3 3 0 0 0 0 2 0 3 0 0 0 0 0 0 2 2 2 2 2 2 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ----------------- --- new state --- | current pos (Y, X): (2, 6) checking y= 3 and x= 6 | Data[3][6] is true A way found to the right. Maze was updated. checking y= 2 and x= 7 | checking y= 1 and x= 6 | Data[1][6] is true A way found to the left. Maze was updated.
57
Top Of Stack is: 3 ---stack values[0]: 11 2 2 2 ---stack values[1]: 11 2 6 2 ---stack values[2]: 13 2 6 2 nextMove is 13, from (2, 6) | move to direction 1, (moveLeft) ----------------- 1 2 3 4 5 6 7 8 9 ----------------- 2 0 3 3 3 0 0 0 0 2 0 3 0 0 0 1 0 0 2 2 2 2 2 2 2 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ----------------- --- new state --- | current pos (Y, X): (1, 6) checking y= 1 and x= 7 | checking y= 0 and x= 6 | Data[0][6] is true A way found to forward. Maze was updated. checking y= 1 and x= 5 | Top Of Stack is: 3 ---stack values[0]: 11 2 2 2 ---stack values[1]: 11 2 6 2 ---stack values[2]: 12 1 6 1 nextMove is 12, from (1, 6) | move to direction 1, (moveForward) ----------------- 1 2 3 4 5 6 7 8 9 ----------------- 2 0 3 3 3 0 1 0 0 2 0 3 0 0 0 2 0 0 2 2 2 2 2 2 2 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ----------------- --- new state --- | current pos (Y, X): (0, 6) checking y= 0 and x= 7 | Data[0][7] is true A way found to the right. Maze was updated. checking y= 0 and x= 5 | Top Of Stack is: 3 ---stack values[0]: 11 2 2 2
58
---stack values[1]: 11 2 6 2 ---stack values[2]: 11 0 6 1 nextMove is 11, from (0, 6) | move to direction 2, (moveRight) ----------------- 1 2 3 4 5 6 7 8 9 ----------------- 2 0 3 3 3 0 2 1 0 2 0 3 0 0 0 2 0 0 2 2 2 2 2 2 2 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ----------------- --- new state --- | current pos (Y, X): (0, 7) checking y= 1 and x= 7 | checking y= 0 and x= 8 | Data[0][8] is true A way found to forward. Maze was updated. Top Of Stack is: 3 ---stack values[0]: 11 2 2 2 ---stack values[1]: 11 2 6 2 ---stack values[2]: 12 0 7 2 nextMove is 12, from (0, 7) | move to direction 2, (moveForward) ----------------- 1 2 3 4 5 6 7 8 9 ----------------- 2 0 3 3 3 0 2 2 1 2 0 3 0 0 0 2 0 0 2 2 2 2 2 2 2 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ----------------- --- new state --- | current pos (Y, X): (0, 8) checking y= 1 and x= 8 | Data[1][8] is true A way found to the right. Maze was updated. Top Of Stack is: 3 ---stack values[0]: 11 2 2 2 ---stack values[1]: 11 2 6 2 ---stack values[2]: 11 0 8 2 nextMove is 11, from (0, 8) |
59
move to direction 8, (moveRight) ----------------- 1 2 3 4 5 6 7 8 9 ----------------- 2 0 3 3 3 0 2 2 2 2 0 3 0 0 0 2 0 1 2 2 2 2 2 2 2 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ----------------- --- new state --- | current pos (Y, X): (1, 8) checking y= 1 and x= 7 | checking y= 2 and x= 8 | Data[2][8] is true A way found to forward. Maze was updated. Top Of Stack is: 3 ---stack values[0]: 11 2 2 2 ---stack values[1]: 11 2 6 2 ---stack values[2]: 12 1 8 8 nextMove is 12, from (1, 8) | move to direction 8, (moveForward) ----------------- 1 2 3 4 5 6 7 8 9 ----------------- 2 0 3 3 3 0 2 2 2 2 0 3 0 0 0 2 0 2 2 2 2 2 2 2 2 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ----------------- --- new state --- | current pos (Y, X): (2, 8) checking y= 2 and x= 7 | checking y= 3 and x= 8 | Data[3][8] is true A way found to forward. Maze was updated. Top Of Stack is: 3 ---stack values[0]: 11 2 2 2 ---stack values[1]: 11 2 6 2 ---stack values[2]: 12 2 8 8 nextMove is 12, from (2, 8) | move to direction 8, (moveForward) ----------------- 1 2 3 4 5 6 7 8 9
60
----------------- 2 0 3 3 3 0 2 2 2 2 0 3 0 0 0 2 0 2 2 2 2 2 2 2 2 0 2 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ----------------- --- new state --- | current pos (Y, X): (3, 8) checking y= 3 and x= 7 | checking y= 4 and x= 8 | Top Of Stack is: 2 ---stack values[0]: 11 2 2 2 ---stack values[1]: 11 2 6 2 Solution Found. nextMove is 12, from (3, 8). Dir: 1 | --- backtrack state --- | current pos (Y, X): (3, 8) move to direction 1, (moveForward) ----------------- 1 2 3 4 5 6 7 8 9 ----------------- 2 0 3 3 3 0 2 2 2 2 0 3 0 0 0 2 0 2 2 2 2 2 2 2 2 0 2 0 0 1 0 0 0 1 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ----------------- nextMove is 12, from (2, 8). Dir: 1 | --- backtrack state --- | current pos (Y, X): (2, 8) move to direction 1, (moveForward) ----------------- 1 2 3 4 5 6 7 8 9 ----------------- 2 0 3 3 3 0 2 2 2 2 0 3 0 0 0 2 0 2 2 2 2 2 2 2 2 0 3 0 0 1 0 0 0 1 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ----------------- nextMove is 13, from (1, 8). Dir: 1 | --- backtrack state --- | current pos (Y, X): (1, 8) move to direction 4, (moveLeft)
61
----------------- 1 2 3 4 5 6 7 8 9 ----------------- 2 0 3 3 3 0 2 2 2 2 0 3 0 0 0 2 0 3 2 2 2 2 2 2 2 0 3 0 0 1 0 0 0 1 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ----------------- nextMove is 12, from (0, 8). Dir: 4 | --- backtrack state --- | current pos (Y, X): (0, 8) move to direction 4, (moveForward) ----------------- 1 2 3 4 5 6 7 8 9 ----------------- 2 0 3 3 3 0 2 2 3 2 0 3 0 0 0 2 0 3 2 2 2 2 2 2 2 0 3 0 0 1 0 0 0 1 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ----------------- nextMove is 13, from (0, 7). Dir: 4 | --- backtrack state --- | current pos (Y, X): (0, 7) move to direction 8, (moveLeft) ----------------- 1 2 3 4 5 6 7 8 9 ----------------- 2 0 3 3 3 0 2 3 3 2 0 3 0 0 0 2 0 3 2 2 2 2 2 2 2 0 3 0 0 1 0 0 0 1 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ----------------- nextMove is 12, from (0, 6). Dir: 8 | --- backtrack state --- | current pos (Y, X): (0, 6) move to direction 8, (moveForward) ----------------- 1 2 3 4 5 6 7 8 9 ----------------- 2 0 3 3 3 0 3 3 3 2 0 3 0 0 0 2 0 3
62
2 2 2 2 2 2 2 0 3 0 0 1 0 0 0 1 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ----------------- nextMove is 11, from (1, 6). Dir: 8 | --- backtrack state --- | current pos (Y, X): (1, 6) move to direction 4, (moveRight) ----------------- 1 2 3 4 5 6 7 8 9 ----------------- 2 0 3 3 3 0 3 3 3 2 0 3 0 0 0 3 0 3 2 2 2 2 2 2 2 0 3 0 0 1 0 0 0 1 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ----------------- nextMove is 11, from (2, 6). Dir: 2 | move to direction 8, (moveRight) ----------------- 1 2 3 4 5 6 7 8 9 ----------------- 2 0 3 3 3 0 3 3 3 2 0 3 0 0 0 3 0 3 2 2 2 2 2 2 2 0 3 0 0 1 0 0 0 1 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ----------------- --- new state --- | current pos (Y, X): (3, 6) checking y= 3 and x= 5 | checking y= 4 and x= 6 | Data[4][6] is true A way found to forward. Maze was updated. checking y= 3 and x= 7 | Top Of Stack is: 2 ---stack values[0]: 11 2 2 2 ---stack values[1]: 12 3 6 8 nextMove is 12, from (3, 6) | move to direction 8, (moveForward) ----------------- 1 2 3 4 5 6 7 8 9 ----------------- 2 0 3 3 3 0 3 3 3 2 0 3 0 0 0 3 0 3
63
2 2 2 2 2 2 2 0 3 0 0 1 0 0 0 2 0 3 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ----------------- --- new state --- | current pos (Y, X): (4, 6) checking y= 4 and x= 5 | Data[4][5] is true A way found to the right. Maze was updated. checking y= 5 and x= 6 | Data[5][6] is true A way found to forward. Maze was updated. checking y= 4 and x= 7 | Data[4][7] is true A way found to the left. Maze was updated. Top Of Stack is: 4 ---stack values[0]: 11 2 2 2 ---stack values[1]: 11 4 6 8 ---stack values[2]: 12 4 6 8 ---stack values[3]: 13 4 6 8 nextMove is 13, from (4, 6) | move to direction 2, (moveLeft) ----------------- 1 2 3 4 5 6 7 8 9 ----------------- 2 0 3 3 3 0 3 3 3 2 0 3 0 0 0 3 0 3 2 2 2 2 2 2 2 0 3 0 0 1 0 0 0 2 0 3 0 0 0 0 0 1 2 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 ----------------- --- new state --- | current pos (Y, X): (4, 7) checking y= 5 and x= 7 | checking y= 4 and x= 8 | checking y= 3 and x= 7 | Top Of Stack is: 3 ---stack values[0]: 11 2 2 2 ---stack values[1]: 11 4 6 8 ---stack values[2]: 12 4 6 8 Solution Found. nextMove is 11, from (4, 7). Dir: 4 | --- backtrack state --- | current pos (Y, X): (4, 7) move to direction 1, (moveRight) ----------------- 1 2 3 4 5 6 7 8 9 -----------------
64
2 0 3 3 3 0 3 3 3 2 0 3 0 0 0 3 0 3 2 2 2 2 2 2 2 0 3 0 0 1 0 0 0 2 0 3 0 0 0 0 0 1 2 3 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 ----------------- nextMove is 12, from (4, 6). Dir: 8 | move to direction 8, (moveForward) ----------------- 1 2 3 4 5 6 7 8 9 ----------------- 2 0 3 3 3 0 3 3 3 2 0 3 0 0 0 3 0 3 2 2 2 2 2 2 2 0 3 0 0 1 0 0 0 2 0 3 0 0 0 0 0 1 2 3 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 ----------------- --- new state --- | current pos (Y, X): (5, 6) checking y= 5 and x= 5 | checking y= 6 and x= 6 | Data[6][6] is true A way found to forward. Maze was updated. checking y= 5 and x= 7 | Top Of Stack is: 3 ---stack values[0]: 11 2 2 2 ---stack values[1]: 11 4 6 8 ---stack values[2]: 12 5 6 8 nextMove is 12, from (5, 6) | move to direction 8, (moveForward) ----------------- 1 2 3 4 5 6 7 8 9 ----------------- 2 0 3 3 3 0 3 3 3 2 0 3 0 0 0 3 0 3 2 2 2 2 2 2 2 0 3 0 0 1 0 0 0 2 0 3 0 0 0 0 0 1 2 3 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 1 0 0 ----------------- --- new state --- | current pos (Y, X): (6, 6) checking y= 6 and x= 5 | Data[6][5] is true A way found to the right. Maze was updated. checking y= 6 and x= 7 |
65
Top Of Stack is: 3 ---stack values[0]: 11 2 2 2 ---stack values[1]: 11 4 6 8 ---stack values[2]: 11 6 6 8 nextMove is 11, from (6, 6) | move to direction 4, (moveRight) ----------------- 1 2 3 4 5 6 7 8 9 ----------------- 2 0 3 3 3 0 3 3 3 2 0 3 0 0 0 3 0 3 2 2 2 2 2 2 2 0 3 0 0 1 0 0 0 2 0 3 0 0 0 0 0 1 2 3 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 1 2 0 0 ----------------- --- new state --- | current pos (Y, X): (6, 5) checking y= 5 and x= 5 | checking y= 6 and x= 4 | Data[6][4] is true A way found to forward. Maze was updated. Top Of Stack is: 3 ---stack values[0]: 11 2 2 2 ---stack values[1]: 11 4 6 8 ---stack values[2]: 12 6 5 4 nextMove is 12, from (6, 5) | move to direction 4, (moveForward) ----------------- 1 2 3 4 5 6 7 8 9 ----------------- 2 0 3 3 3 0 3 3 3 2 0 3 0 0 0 3 0 3 2 2 2 2 2 2 2 0 3 0 0 1 0 0 0 2 0 3 0 0 0 0 0 1 2 3 0 0 0 0 0 0 0 2 0 0 0 0 0 0 1 2 2 0 0 ----------------- --- new state --- | current pos (Y, X): (6, 4) checking y= 5 and x= 4 | checking y= 6 and x= 3 | Top Of Stack is: 2 ---stack values[0]: 11 2 2 2 ---stack values[1]: 11 4 6 8 Dead-end. nextMove is 12, from (6, 4). Dir: 2 |
66
--- backtrack state --- | current pos (Y, X): (6, 4) move to direction 2, (moveForward) ----------------- 1 2 3 4 5 6 7 8 9 ----------------- 2 0 3 3 3 0 3 3 3 2 0 3 0 0 0 3 0 3 2 2 2 2 2 2 2 0 3 0 0 1 0 0 0 2 0 3 0 0 0 0 0 1 2 3 0 0 0 0 0 0 0 2 0 0 0 0 0 0 3 2 2 0 0 ----------------- nextMove is 13, from (6, 5). Dir: 2 | --- backtrack state --- | current pos (Y, X): (6, 5) move to direction 1, (moveLeft) ----------------- 1 2 3 4 5 6 7 8 9 ----------------- 2 0 3 3 3 0 3 3 3 2 0 3 0 0 0 3 0 3 2 2 2 2 2 2 2 0 3 0 0 1 0 0 0 2 0 3 0 0 0 0 0 1 2 3 0 0 0 0 0 0 0 2 0 0 0 0 0 0 3 3 2 0 0 ----------------- nextMove is 12, from (6, 6). Dir: 1 | --- backtrack state --- | current pos (Y, X): (6, 6) move to direction 1, (moveForward) ----------------- 1 2 3 4 5 6 7 8 9 ----------------- 2 0 3 3 3 0 3 3 3 2 0 3 0 0 0 3 0 3 2 2 2 2 2 2 2 0 3 0 0 1 0 0 0 2 0 3 0 0 0 0 0 1 2 3 0 0 0 0 0 0 0 2 0 0 0 0 0 0 3 3 3 0 0 ----------------- nextMove is 11, from (4, 6). Dir: 8 | move to direction 4, (moveRight) ----------------- 1 2 3 4 5 6 7 8 9 ----------------- 2 0 3 3 3 0 3 3 3 2 0 3 0 0 0 3 0 3
67
2 2 2 2 2 2 2 0 3 0 0 1 0 0 0 2 0 3 0 0 0 0 0 1 2 3 0 0 0 0 0 0 0 2 0 0 0 0 0 0 3 3 3 0 0 ----------------- --- new state --- | current pos (Y, X): (4, 5) checking y= 3 and x= 5 | checking y= 4 and x= 4 | Data[4][4] is true A way found to forward. Maze was updated. checking y= 5 and x= 5 | Top Of Stack is: 2 ---stack values[0]: 11 2 2 2 ---stack values[1]: 12 4 5 4 nextMove is 12, from (4, 5) | move to direction 4, (moveForward) ----------------- 1 2 3 4 5 6 7 8 9 ----------------- 2 0 3 3 3 0 3 3 3 2 0 3 0 0 0 3 0 3 2 2 2 2 2 2 2 0 3 0 0 1 0 0 0 2 0 3 0 0 0 0 1 2 2 3 0 0 0 0 0 0 0 2 0 0 0 0 0 0 3 3 3 0 0 ----------------- --- new state --- | current pos (Y, X): (4, 4) checking y= 3 and x= 4 | checking y= 4 and x= 3 | checking y= 5 and x= 4 | Top Of Stack is: 1 ---stack values[0]: 11 2 2 2 Dead-end. nextMove is 12, from (4, 4). Dir: 2 | --- backtrack state --- | current pos (Y, X): (4, 4) move to direction 2, (moveForward) ----------------- 1 2 3 4 5 6 7 8 9 ----------------- 2 0 3 3 3 0 3 3 3 2 0 3 0 0 0 3 0 3 2 2 2 2 2 2 2 0 3 0 0 1 0 0 0 2 0 3 0 0 0 0 3 2 2 3 0 0 0 0 0 0 0 2 0 0 0 0 0 0 3 3 3 0 0 -----------------
68
nextMove is 12, from (4, 6). Dir: 1 | --- backtrack state --- | current pos (Y, X): (4, 6) move to direction 1, (moveForward) ----------------- 1 2 3 4 5 6 7 8 9 ----------------- 2 0 3 3 3 0 3 3 3 2 0 3 0 0 0 3 0 3 2 2 2 2 2 2 2 0 3 0 0 1 0 0 0 2 0 3 0 0 0 0 3 2 3 3 0 0 0 0 0 0 0 2 0 0 0 0 0 0 3 3 3 0 0 ----------------- nextMove is 12, from (2, 6). Dir: 4 | --- backtrack state --- | current pos (Y, X): (2, 6) move to direction 4, (moveForward) ----------------- 1 2 3 4 5 6 7 8 9 ----------------- 2 0 3 3 3 0 3 3 3 2 0 3 0 0 0 3 0 3 2 2 2 2 2 2 3 0 3 0 0 1 0 0 0 2 0 3 0 0 0 0 3 2 3 3 0 0 0 0 0 0 0 2 0 0 0 0 0 0 3 3 3 0 0 ----------------- nextMove is 12, from (2, 5). Dir: 4 | --- backtrack state --- | current pos (Y, X): (2, 5) move to direction 4, (moveForward) ----------------- 1 2 3 4 5 6 7 8 9 ----------------- 2 0 3 3 3 0 3 3 3 2 0 3 0 0 0 3 0 3 2 2 2 2 2 3 3 0 3 0 0 1 0 0 0 2 0 3 0 0 0 0 3 2 3 3 0 0 0 0 0 0 0 2 0 0 0 0 0 0 3 3 3 0 0 ----------------- nextMove is 12, from (2, 4). Dir: 4 | --- backtrack state --- | current pos (Y, X): (2, 4) move to direction 4, (moveForward) ----------------- 1 2 3 4 5 6 7 8 9
69
----------------- 2 0 3 3 3 0 3 3 3 2 0 3 0 0 0 3 0 3 2 2 2 2 3 3 3 0 3 0 0 1 0 0 0 2 0 3 0 0 0 0 3 2 3 3 0 0 0 0 0 0 0 2 0 0 0 0 0 0 3 3 3 0 0 ----------------- nextMove is 11, from (2, 2). Dir: 2 | move to direction 8, (moveRight) ----------------- 1 2 3 4 5 6 7 8 9 ----------------- 2 0 3 3 3 0 3 3 3 2 0 3 0 0 0 3 0 3 2 2 2 2 3 3 3 0 3 0 0 1 0 0 0 2 0 3 0 0 0 0 3 2 3 3 0 0 0 0 0 0 0 2 0 0 0 0 0 0 3 3 3 0 0 ----------------- --- new state --- | current pos (Y, X): (3, 2) checking y= 3 and x= 1 | checking y= 4 and x= 2 | Data[4][2] is true A way found to forward. Maze was updated. checking y= 3 and x= 3 | Top Of Stack is: 1 ---stack values[0]: 12 3 2 8 nextMove is 12, from (3, 2) | move to direction 8, (moveForward) ----------------- 1 2 3 4 5 6 7 8 9 ----------------- 2 0 3 3 3 0 3 3 3 2 0 3 0 0 0 3 0 3 2 2 2 2 3 3 3 0 3 0 0 2 0 0 0 2 0 3 0 0 1 0 3 2 3 3 0 0 0 0 0 0 0 2 0 0 0 0 0 0 3 3 3 0 0 ----------------- --- new state --- | current pos (Y, X): (4, 2) checking y= 4 and x= 1 | Data[4][1] is true A way found to the right. Maze was updated. checking y= 5 and x= 2 | checking y= 4 and x= 3 | Top Of Stack is: 1
70
---stack values[0]: 11 4 2 8 nextMove is 11, from (4, 2) | move to direction 4, (moveRight) ----------------- 1 2 3 4 5 6 7 8 9 ----------------- 2 0 3 3 3 0 3 3 3 2 0 3 0 0 0 3 0 3 2 2 2 2 3 3 3 0 3 0 0 2 0 0 0 2 0 3 0 1 2 0 3 2 3 3 0 0 0 0 0 0 0 2 0 0 0 0 0 0 3 3 3 0 0 ----------------- --- new state --- | current pos (Y, X): (4, 1) checking y= 3 and x= 1 | checking y= 4 and x= 0 | Data[4][0] is true A way found to forward. Maze was updated. checking y= 5 and x= 1 | Top Of Stack is: 1 ---stack values[0]: 12 4 1 4 nextMove is 12, from (4, 1) | move to direction 4, (moveForward) ----------------- 1 2 3 4 5 6 7 8 9 ----------------- 2 0 3 3 3 0 3 3 3 2 0 3 0 0 0 3 0 3 2 2 2 2 3 3 3 0 3 0 0 2 0 0 0 2 0 3 1 2 2 0 3 2 3 3 0 0 0 0 0 0 0 2 0 0 0 0 0 0 3 3 3 0 0 ----------------- --- new state --- | current pos (Y, X): (4, 0) checking y= 3 and x= 0 | checking y= 5 and x= 0 | Data[5][0] is true A way found to the left. Maze was updated. Top Of Stack is: 1 ---stack values[0]: 13 4 0 4 nextMove is 13, from (4, 0) | move to direction 8, (moveLeft) ----------------- 1 2 3 4 5 6 7 8 9 ----------------- 2 0 3 3 3 0 3 3 3
71
2 0 3 0 0 0 3 0 3 2 2 2 2 3 3 3 0 3 0 0 2 0 0 0 2 0 3 2 2 2 0 3 2 3 3 0 1 0 0 0 0 0 2 0 0 0 0 0 0 3 3 3 0 0 ----------------- --- new state --- | current pos (Y, X): (5, 0) checking y= 6 and x= 0 | Data[6][0] is true A way found to forward. Maze was updated. checking y= 5 and x= 1 | Top Of Stack is: 1 ---stack values[0]: 12 5 0 8 nextMove is 12, from (5, 0) | move to direction 8, (moveForward) ----------------- 1 2 3 4 5 6 7 8 9 ----------------- 2 0 3 3 3 0 3 3 3 2 0 3 0 0 0 3 0 3 2 2 2 2 3 3 3 0 3 0 0 2 0 0 0 2 0 3 2 2 2 0 3 2 3 3 0 2 0 0 0 0 0 2 0 0 1 0 0 0 3 3 3 0 0 ----------------- --- new state --- | current pos (Y, X): (6, 0) checking y= 6 and x= 1 | Top Of Stack is: 0 All area is explored succesfully. Maze 2 0 3 3 3 0 3 3 3 2 0 3 0 0 0 3 0 3 2 2 2 2 3 3 3 0 3 0 0 2 0 0 0 2 0 3 2 2 2 0 3 2 3 3 0 2 0 0 0 0 0 2 0 0 1 0 0 0 3 3 3 0 0 Finding shortest path.. Position of source(x: 0 ,y: 0) Position of Destination(x: 4 ,y: 8)
72
(0, 0) -> (1, 0) -> (2, 0) -> (2, 1) -> (2, 2) -> (2, 3) -> (2, 4) -> (2, 5) -> (2, 6) -> (3, 6) -> (4, 6) -> (4, 7) -> (4, 8)