Recursive Backtracker Maze Generator

Рекурсив буцаах алгоритм нь үнэхээр ерөнхий зориулалтын гүнээс эхлээд хайлт юм. Төөрдөг байшин үүсгэхэд ашиглахдаа замаа санамсаргүй байдлаар сонгохын тулд бага зэрэг өөрчлөгддөг бол бодит хайлтын зорилгоор ашиглавал түвшин бүрийг шугаман дарааллаар хайх болно. Энэ нь урт, ороомог коридор, маш урт, мушгирсан шийдэл бүхий төөрдөг байшинг бүтээх хандлагатай байдаг.

Төгс төөрдөг байшин гэдэг нь төөрдөг шорооны аль ч цэгээс өөр цэг хүртэл яг нэг зам байдаг төөрдөг байшин юм. Энэ нь та эргэн тойронд эргэлдэж чадахгүй гэсэн үг, гэхдээ та ихэнхдээ гарцгүй гарцтай тулгарах бөгөөд таныг эргэж, буцаж явахад хүргэдэг.

Энд үүсгэсэн төөрдөг шорооны газрын зураг нь ямар ч эхлэл, төгсгөлийн байрлалгүй анхдагч хувилбарыг агуулдаг тул та эдгээрийг өөрөө шийдэх боломжтой: төөрдөг газрын аль ч цэгээс өөр цэг хүртэл шийдэл байх болно. Хэрэв та урам зориг авахыг хүсч байвал санал болгож буй эхлэх, дуусгах байрлалыг идэвхжүүлж, тэр ч байтугай хоёрын хоорондох шийдлийг харж болно.

Рекурсив арын зам хайгч алгоритм нь төгс лабиринт үүсгэх (давхцалгүй, хоёр цэгийн хооронд нэг л замтай лабиринт) гүндэх-эхэлсэн хайлт арга юм. Энэ нь энгийн, үр ашигтай бөгөөд урт, мушгиа орон зайтай харагдахуйц лабиринтуудыг бий болгодог.

Нэр нь ямар ч байсан, үүнийг заавал рекурсаар хэрэгжүүлэх шаардлагагүй. Ихэвчлэн LIFO дараалал (өөрөөр хэлбэл стек) ашиглан давталттай хэрэгжүүлэгддэг. Маш том лабиринтуудын хувьд, рекурс ашигласнаар програмчлалын хэл болон байгаа санах ойгоос хамааран дуудлага дахь стэк хэт их ачаалал үүсэх магадлалтай. LIFO дараалал нь том хэмжээний өгөгдлийг удирдахад илүү хялбар бөгөөд санах ой хэтэрсэн тохиолдолд дарааллыг диск дээр эсвэл мэдээллийн сан дээр хадгалах боломжтой.

Яаж ажилладаг вэ

Алгоритм нь стек ашиглан гүндэх-эхэлсэн хайлт аргыг ашиглан ажилладаг. Алхам алхмаар дэлгэрэнгүй:

1. Эхлэх гарчигыг сонгоод, үүнийг зорьсон гэж тэмдэглэ.
2. Зорьсонгүй эсвэл хайлтын эхлэлийг олгоогүй гарчигууд байвал:
   • Үнэхээр зорьсонгүй байсан хөршийн гарчигийг үзнэ үү.
   • Хэрэв нэг ч зорьсонгүй хөрш байвал:
     • Зорьсонгүй хөршөөс нэгийг санамсаргүйгээр сонгоно.
     • Одоогийн гарчиг ба сонгосон хөршийн хоорондох ханаа устгана.
     • Сонгосон хөршид шилжиж, үүнийг зорьсон гэж тэмдэглэнэ.
     • Одоогийн гарчгийг стек рүү түлхэнэ.
   • Хэрэв зорьсонгүй хөрш байвал:
     • Стектээс хамгийн сүүлд нэмэгдсэн гарчгийг гаргаж авахад арын замыг хайдаг.
3. Энэхүү үйл явцыг стэк хоосронг магадлах хүртэл үргэлжлүүлнэ.

Энэхүү алгоритмын сонирхолтой баримт нь энэ нь лабиринт үүсгэгч болон лабиринт шийдэгч хоёрын хоёуланг нь хийх чадвартай юм. Хэрэв та үүнийг аль хэдийн үүсгэсэн лабиринтад ажиллуулж, шийдсэн эцсийн цэгт хүрэхэд зогсвол, стэк нь лабиринтын шийдлийг агуулсан байх болно.

Би энэ сайтын хоёр хувилбарыг ашигладаг: нэг нь лабиринт үүсгэх LIFO дараалал ашигладаг хувилбар бөгөөд нөгөө нь лабиринтуудыг шийдэж буй рекурсын хувилбар (энэ нь бусад алгоритмуудын үүсгэсэн лабиринт дээр шийдлийг олохтой холбоотой). Хоёр өөр хувилбар ашиглах нь зөвхөн спортын зорилгоор, учир нь би сонирхолтой гэж боддог шүү дээ, аль аль нь хоёуланд нь тохирч болно ;-)