Menyelesaikan Maze Secara Otomatis Menggunakan Algoritma Dijkstra

Ini adalah tulisan anak ke 1 usia 16 tahun yang sedang mempelajari Algoritma Komputer.

Algoritma Dijkstra adalah algoritma untuk mencari jalur tersingkat dari satu titik ke satu titik lainnya. Algoritma ini dapat digunakan untuk menyelesaikan sebuah maze.

Ini adalah salah satu gambar "maze sederhana" yang sudah diselesaikan oleh program yang menggunakan algoritma dijkstra:

Gambar asli berukuran 10px x 20px

Pada waktu itu, teknik yang digunakan adalah teknik rekursi dari sini, Memang berhasil, tetapi, ketika dicoba dengan maze yang lebih besar, program tewas dan tak mampu menyelesaikan maze.

Teknik lainpun dicoba, kali ini yang digunakan adalah teknik loop dari buku Competitive Programmers Handbook. Teknik ini mudah ditulis, singkat, dan mudah dimengerti, tidak seperti kebanyakan algoritma dijkstra yang lain. Kebanyakan algoritma pada umumnya susah dimengerti dan menggunakan banyak baris code, walaupun sama sama menggunakan teknik looping.

Teknik ini berhasil menyelesaikan maze yang lebih besar. Ini adalah hasilnya:

Kemudian dicoba lagi dengan maze yang lebih besar:

Pada maze ini, program memilih untuk tidak melewati maze, tetapi ia "memotong jalan" (lewat sebelah kiri):

Setelah jalur untuk memotong jalan tersebut ditutup:

Akhirnya jalur maze diberi warna:

Kemudian program dibuat supaya bisa bergerak secara diagonal:

Mulai mencoba maze yang lebih rumit:

Maze yang jauh lebih rumit:

Maze diatas diselesaikan dalam waktu kurang dari 2 menit.

Maze ini diselesaikan dalam waktu kurang dari 17 detik:

Kilas Balik Menyelesaikan Maze. 

Pada tahun 2009 ketika berumur 7 tahun saya menyelesaikan maze secara manual dan 8 tahun kemudian menyelesaikan maze yang sama dengan Algoritma Dijkstra. Cerita di tahun 2009 dapat dilihat di sini.

Source code ada di github (mungkin akan dikembangkan kemudian) .

Kredit maze: krazydad.com, fun-stuff-to-do.com dan littlebadwolf.com .