Apa cara terbaik untuk mewakili dan memecahkan labirin yang diberi gambar?
Diberikan gambar JPEG (seperti yang terlihat di atas), apa cara terbaik untuk membacanya, parsing ke dalam beberapa struktur data dan pecahkan maze? Insting pertama saya adalah membaca gambar dalam pixel demi pixel dan menyimpannya dalam daftar (array) nilai boolean: True
untuk pixel putih, dan False
untuk piksel non-putih (warna dapat dibuang). Masalah dengan metode ini, adalah bahwa gambar mungkin tidak "pixel perfect". Maksud saya, jika ada piksel putih di suatu tempat di dinding, itu mungkin membuat jalur yang tidak diinginkan.
Metode lain (yang datang kepada saya setelah sedikit berpikir) adalah untuk mengkonversi gambar ke file SVG - yang merupakan daftar jalur yang digambar di atas kanvas. Dengan cara ini, jalur dapat dibaca ke dalam daftar yang sama (nilai boolean) di mana True
menunjukkan jalur atau dinding,False
menunjukkan ruang yang dapat bepergian. Masalah dengan metode ini muncul jika konversi tidak 100% akurat, dan tidak sepenuhnya menghubungkan semua dinding, menciptakan celah.
Juga masalah dengan mengkonversi ke SVG adalah bahwa garis tidak lurus "sempurna". Ini menghasilkan lintasan menjadi kurva kubik bezier. Dengan daftar (larik) nilai boolean yang diindeks oleh bilangan bulat, kurva tidak akan mudah ditransfer, dan semua titik yang garis pada kurva harus dihitung, tetapi tidak akan sama persis dengan daftar indeks.
Saya berasumsi bahwa sementara salah satu metode ini dapat bekerja (meskipun mungkin tidak) bahwa mereka sangat tidak efisien diberi gambar sebesar itu, dan bahwa ada cara yang lebih baik. Bagaimana ini terbaik (paling efisien dan / atau dengan kompleksitas paling sedikit) dilakukan? Apakah ada cara terbaik?
Kemudian datang pemecahan labirin. Jika saya menggunakan salah satu dari dua metode pertama, saya pada dasarnya akan berakhir dengan sebuah matriks. Menurut jawaban ini , cara yang baik untuk mewakili labirin menggunakan pohon, dan cara yang baik untuk menyelesaikannya adalah menggunakan algoritma A * . Bagaimana cara membuat pohon dari gambar? Ada ide?
TL; DR
Cara terbaik untuk menguraikan? Ke dalam struktur data apa? Bagaimana mengatakan struktur membantu / menghambat penyelesaian?
PEMBARUAN
Saya sudah mencoba menerapkan @Mikhail dengan Python, menggunakan numpy
, seperti yang direkomendasikan oleh @Thomas. Saya merasa bahwa algoritme itu benar, tetapi tidak berfungsi seperti yang diharapkan. (Kode di bawah ini.) Perpustakaan PNG adalah PyPNG .
import png, numpy, Queue, operator, itertools
def is_white(coord, image):
""" Returns whether (x, y) is approx. a white pixel."""
a = True
for i in xrange(3):
if not a: break
a = image[coord[1]][coord[0] * 3 + i] > 240
return a
def bfs(s, e, i, visited):
""" Perform a breadth-first search. """
frontier = Queue.Queue()
while s != e:
for d in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
np = tuple(map(operator.add, s, d))
if is_white(np, i) and np not in visited:
frontier.put(np)
visited.append(s)
s = frontier.get()
return visited
def main():
r = png.Reader(filename = "thescope-134.png")
rows, cols, pixels, meta = r.asDirect()
assert meta['planes'] == 3 # ensure the file is RGB
image2d = numpy.vstack(itertools.imap(numpy.uint8, pixels))
start, end = (402, 985), (398, 27)
print bfs(start, end, image2d, [])
visited.append(s)
bawahfor.if
dan menggantinya denganvisited.append(np)
. Sebuah vertex dikunjungi setelah ditambahkan ke antrian. Bahkan, array ini harus dinamai "antri". Anda juga dapat menghentikan BFS setelah Anda mencapai finish.Jawaban:
Ini solusinya.
Berikut adalah kode MATLAB untuk BFS:
Ini benar-benar sangat sederhana dan standar, tidak boleh ada kesulitan dalam mengimplementasikan ini dengan Python atau apa pun.
Dan inilah jawabannya:
sumber
Solusi ini ditulis dalam Python. Terima kasih Mikhail untuk petunjuk tentang persiapan gambar.
Animasi Breadth-First Search:
Labirin Lengkap:
Catatan: Menandai abu-abu piksel yang dikunjungi putih. Ini menghilangkan kebutuhan untuk daftar yang dikunjungi, tetapi ini membutuhkan pemuatan kedua file gambar dari disk sebelum menggambar jalur (jika Anda tidak ingin gambar komposit dari jalur akhir dan SEMUA jalur diambil).
Versi kosong dari labirin yang saya gunakan.
sumber
Saya mencoba menerapkan pencarian A-Star untuk masalah ini. Diikuti dengan cermat implementasi oleh Joseph Kern untuk kerangka kerja dan algoritma pseudocode yang diberikan di sini :
Karena A-Star adalah algoritma pencarian heuristik, Anda perlu membuat fungsi yang memperkirakan biaya yang tersisa (di sini: jarak) hingga tujuan tercapai. Kecuali Anda merasa nyaman dengan solusi suboptimal itu tidak boleh melebih-lebihkan biayanya. Pilihan konservatif di sini adalah jarak manhattan (atau taksi) karena ini mewakili jarak garis lurus antara dua titik di grid untuk lingkungan Von Neumann yang digunakan. (Yang, dalam hal ini, tidak akan pernah melebih-lebihkan biayanya.)
Namun ini akan secara signifikan meremehkan biaya sebenarnya untuk labirin yang diberikan. Oleh karena itu saya telah menambahkan dua metrik jarak lain kuadrat jarak euclidean dan jarak manhattan dikalikan empat untuk perbandingan. Namun ini mungkin melebih-lebihkan biaya aktual, dan karenanya mungkin menghasilkan hasil yang kurang optimal.
Ini kodenya:
Berikut adalah beberapa gambar untuk visualisasi hasil (terinspirasi oleh yang diposting oleh Joseph Kern ). Animasi menunjukkan bingkai baru masing-masing setelah 10.000 iterasi dari while-loop utama.
Pencarian Breadth-First:
A-Star Manhattan Jarak:
A-Star Squared Euclidean Jarak:
A-Star Manhattan Distance dikalikan empat:
Hasil penelitian menunjukkan bahwa daerah yang dieksplorasi dari labirin sangat berbeda untuk heuristik yang digunakan. Dengan demikian, jarak euclide kuadrat bahkan menghasilkan jalur (suboptimal) yang berbeda dengan metrik lainnya.
Mengenai kinerja algoritma A-Star dalam hal runtime sampai penghentian, perhatikan bahwa banyak evaluasi jarak dan fungsi biaya bertambah dibandingkan dengan Breadth-First Search (BFS) yang hanya perlu mengevaluasi "tujuan" dari masing-masing posisi kandidat. Apakah biaya untuk evaluasi fungsi tambahan ini (A-Star) melebihi biaya untuk jumlah node yang lebih besar untuk diperiksa (BFS) dan terutama apakah kinerja merupakan masalah bagi aplikasi Anda atau tidak, itu adalah masalah persepsi individu dan tentu saja tidak bisa dijawab secara umum.
Suatu hal yang dapat dikatakan secara umum tentang apakah atau tidak algoritma pencarian informasi (seperti A-Star) bisa menjadi pilihan yang lebih baik dibandingkan dengan pencarian yang lengkap (misalnya, BFS) adalah sebagai berikut. Dengan jumlah dimensi labirin, yaitu, faktor percabangan dari pohon pencarian, kelemahan dari pencarian lengkap (untuk mencari secara mendalam) tumbuh secara eksponensial. Dengan semakin rumitnya, semakin tidak mungkin untuk melakukannya dan pada titik tertentu Anda cukup senang dengan jalur hasil apa pun , baik itu (kurang-lebih) optimal atau tidak.
sumber
Pencarian pohon terlalu banyak. Labirin secara inheren dapat dipisahkan di sepanjang jalur solusi.
(Terima kasih kepada rainman002 dari Reddit karena menunjukkan ini padaku.)
Karena itu, Anda dapat dengan cepat menggunakan komponen yang terhubung untuk mengidentifikasi bagian dinding labirin yang terhubung. Ini mengulangi piksel dua kali.
Jika Anda ingin mengubahnya menjadi diagram yang bagus dari jalur solusi, Anda kemudian dapat menggunakan operasi biner dengan elemen penataan untuk mengisi jalur "jalan buntu" untuk setiap wilayah yang terhubung.
Kode demo untuk MATLAB berikut. Itu bisa menggunakan tweaking untuk membersihkan hasilnya lebih baik, membuatnya lebih digeneralisasikan, dan membuatnya berjalan lebih cepat. (Kadang saat itu bukan jam 2:30 pagi.)
sumber
Menggunakan antrian untuk pengisian terus menerus ambang. Dorong pixel kiri dari pintu masuk ke antrian dan kemudian mulai loop. Jika piksel yang antri cukup gelap, warnanya abu-abu terang (di atas ambang batas), dan semua tetangga didorong ke antrean.
Solusi adalah koridor antara dinding abu-abu dan dinding berwarna. Perhatikan bahwa labirin ini memiliki banyak solusi. Juga, ini hanya berfungsi.
sumber
Ini dia: maze-solver-python (GitHub)
Saya bersenang-senang bermain-main dengan ini dan memperluas Joseph Kern jawaban . Tidak mengurangi darinya; Saya hanya membuat beberapa tambahan kecil untuk orang lain yang mungkin tertarik bermain-main dengan ini.
Ini adalah pemecah berbasis python yang menggunakan BFS untuk menemukan jalur terpendek. Tambahan utama saya, pada saat itu, adalah:
Seperti berdiri, titik awal / akhir adalah kode keras untuk labirin sampel ini, tapi saya berencana untuk memperluasnya sehingga Anda dapat memilih piksel yang sesuai.
sumber
Saya akan memilih opsi matrix-of-bools. Jika Anda menemukan bahwa daftar Python standar terlalu tidak efisien untuk ini, Anda bisa menggunakan a
numpy.bool
array. Penyimpanan untuk labirin 1000x1000 piksel kemudian hanya 1 MB.Jangan repot-repot membuat struktur data pohon atau grafik. Itu hanya cara berpikir tentang hal itu, tetapi belum tentu cara yang baik untuk merepresentasikannya dalam memori; matriks boolean lebih mudah dikodekan dan lebih efisien.
Kemudian gunakan algoritma A * untuk menyelesaikannya. Untuk jarak heuristik, gunakan jarak Manhattan (
distance_x + distance_y
).Mewakili node dengan tupel
(row, column)
koordinat. Setiap kali algoritme ( pseudocode Wikipedia ) memanggil "tetangga", ini adalah masalah sederhana untuk mengulangi empat tetangga yang mungkin (pikirkan ujung-ujung gambar!).Jika ternyata masih terlalu lambat, Anda dapat mencoba menurunkan skala gambar sebelum memuatnya. Berhati-hatilah agar tidak kehilangan jalur sempit dalam proses.
Mungkin mungkin untuk melakukan downscaling 1: 2 dengan Python juga, memeriksa bahwa Anda tidak benar-benar kehilangan jalur yang mungkin. Pilihan yang menarik, tetapi perlu sedikit lebih banyak pemikiran.
sumber
boolean
nilai, apakah penyimpanan masih akan dibandingkan? Matriksnya kemudian 2400 * 1200. Dan apakah A * lebih dari BFS akan berdampak signifikan pada waktu berjalan nyata?Berikut ini beberapa ide.
(1. Pemrosesan Gambar :)
1.1 Muat gambar sebagai peta piksel RGB . Dalam C # itu adalah penggunaan sepele
system.drawing.bitmap
. Dalam bahasa yang tidak memiliki dukungan sederhana untuk pencitraan, cukup konversikan gambar ke format pixmap portabel (PPM) (representasi teks Unix, menghasilkan file besar) atau beberapa format file biner sederhana yang dapat Anda baca dengan mudah, seperti BMP atau TGA . ImageMagick di Unix atau IrfanView di Windows.1.2 Anda dapat, seperti disebutkan sebelumnya, menyederhanakan data dengan mengambil (R + G + B) / 3 untuk setiap piksel sebagai indikator nada abu-abu dan kemudian memberikan nilai ambang batas untuk menghasilkan tabel hitam putih. Sesuatu yang mendekati 200 dengan asumsi 0 = hitam dan 255 = putih akan mengeluarkan artefak JPEG.
(2. Solusi :)
2.1 Pencarian Kedalaman-Pertama: Masukkan tumpukan kosong dengan lokasi awal, kumpulkan gerakan tindak lanjut yang tersedia, pilih satu secara acak dan dorong ke tumpukan, lanjutkan sampai akhir tercapai atau deadend. Pada backend deadend dengan memunculkan stack, Anda perlu melacak posisi mana yang dikunjungi di peta sehingga ketika Anda mengumpulkan gerakan yang tersedia, Anda tidak akan pernah mengambil jalur yang sama dua kali. Sangat menarik untuk menghidupkan.
2.2 Pencarian Breadth-First: Disebutkan sebelumnya, mirip seperti di atas tetapi hanya menggunakan antrian. Juga menarik untuk dianimasikan. Ini berfungsi seperti mengisi-banjir dalam perangkat lunak pengedit gambar. Saya pikir Anda mungkin dapat memecahkan labirin di Photoshop menggunakan trik ini.
2.3 Wall Follower: Secara geometris, labirin adalah tabung yang terlipat / berbelit-belit. Jika Anda meletakkan tangan di dinding, Anda pada akhirnya akan menemukan pintu keluar;) Ini tidak selalu berhasil. Ada asumsi tertentu tentang: labirin sempurna, dll., Misalnya, labirin tertentu mengandung pulau. Lihat itu; itu menarik.
(3. Komentar :)
Ini yang sulit. Mudah untuk memecahkan labirin jika direpresentasikan dalam beberapa formal array sederhana dengan setiap elemen menjadi tipe sel dengan dinding utara, timur, selatan dan barat dan bidang bendera yang dikunjungi. Namun mengingat bahwa Anda mencoba melakukan ini mengingat sketsa yang digambar tangan itu menjadi berantakan. Jujur saya berpikir bahwa mencoba merasionalisasi sketsa akan membuat Anda gila. Ini mirip dengan masalah penglihatan komputer yang cukup terlibat. Mungkin langsung ke peta gambar mungkin lebih mudah namun lebih boros.
sumber
Inilah solusi menggunakan R.
RGB ke skala abu-abu, lihat: https://stackoverflow.com/a/27491947/2371031
Voila!
Inilah yang terjadi jika Anda tidak mengisi beberapa piksel perbatasan (Ha!) ...
Pengungkapan penuh: Saya bertanya dan menjawab pertanyaan yang sangat mirip sendiri sebelum saya menemukan yang ini. Kemudian melalui keajaiban SO, ditemukan ini sebagai salah satu dari "Pertanyaan Terkait" teratas. Saya pikir saya akan menggunakan labirin ini sebagai test case tambahan ... Saya sangat senang menemukan bahwa jawaban saya di sana juga berfungsi untuk aplikasi ini dengan sedikit modifikasi.
sumber
solusi yang baik adalah bahwa alih-alih menemukan tetangga dengan pixel, itu akan dilakukan oleh sel, karena sebuah koridor dapat memiliki 15px sehingga dalam koridor yang sama dapat mengambil tindakan seperti kiri atau kanan, sementara jika itu dilakukan seolah-olah perpindahan adalah sebuah kubus itu akan menjadi tindakan sederhana seperti ATAS, BAWAH, KIRI ATAU KANAN
sumber