Эллерийн алгоритм Maze генератор
Нийтэлсэн: 2025 оны гуравдугаар сарын 19 20:43:17 (UTC)
Төгс төөрдөг байшин үүсгэхийн тулд Eller-ийн алгоритмыг ашиглан Maze генератор. Энэ алгоритм нь зөвхөн одоогийн мөрийг (бүхэл төөрдөг байшинг биш) санах ойд хадгалахыг шаарддаг тул сонирхолтой бөгөөд үүнийг маш хязгаарлагдмал систем дээр ч гэсэн маш том, маш том лабиринт үүсгэхэд ашиглаж болно.Eller's Algorithm Maze Generator
Эллерийн алгоритм нь эгнээ эгнээний аргыг ашиглан төгс төөрдөг байшинг (ямар ч гогцоогүй, дурын хоёр цэгийн хоорондох ганц зам) үр дүнтэй гаргадаг төөрдөг байшин үүсгэх алгоритм юм. Энэ нь Kruskal-ийн алгоритмтай төстэй төөрдөг байшинг үйлдвэрлэдэг боловч энэ нь төөрдөг байшинг бүхэлд нь санах ойд хадгалах шаардлагагүйгээр нэг удаад зөвхөн нэг эгнээ үүсгэдэг. Энэ нь маш хязгаарлагдмал системүүд дээр маш том лабиринт үүсгэх, процедурын агуулга үүсгэхэд ашигтай болгодог.
Төгс төөрдөг байшин гэдэг нь төөрдөг шорооны аль ч цэгээс өөр цэг хүртэл яг нэг зам байдаг төөрдөг байшин юм. Энэ нь та эргэн тойронд эргэлдэж чадахгүй гэсэн үг, гэхдээ та ихэнхдээ гарцгүй гарцтай тулгарах бөгөөд таныг эргэж, буцаж явахад хүргэдэг.
Энд үүсгэсэн төөрдөг шорооны газрын зураг нь ямар ч эхлэл, төгсгөлийн байрлалгүй анхдагч хувилбарыг агуулдаг тул та эдгээрийг өөрөө шийдэх боломжтой: төөрдөг газрын аль ч цэгээс өөр цэг хүртэл шийдэл байх болно. Хэрэв та урам зориг авахыг хүсч байвал санал болгож буй эхлэх, дуусгах байрлалыг идэвхжүүлж, тэр ч байтугай хоёрын хоорондох шийдлийг харж болно.
Эллерийн алгоритмын тухай
Эллерийн алгоритмыг Дэвид Эллер танилцуулсан.
Алгоритм нь тагт бүрээр ээлжлэн хөдөлж, хэрэм үүсгэхэд үр ашигтай бөгөөд энэ нь хязгааргүй хэрэм эсвэл бодит цагийн хэрэм үүсгэхэд тохиромжтой. Энэ нь процедурын агуулга үүсгэх болон хэрэм үүсгэх зохиолуудад түгээмэл дурдагддаг боловч анхны хэвлэлийн эх үүсвэрийг олоход би амжилтгүй болсон.
Эллерийн алгоритм хэрэм үүсгэхэд хэрхэн ажилладаг вэ
Эллерийн алгоритм нь нэг тагт бүрийг ээлжлэн боловсруулж, холбогдсон эсийн багцуудыг хадгалахын зэрэгцээ засварладаг. Энэ нь утга бүхий холболтыг баталгаажуулж, давхцал үүсгэхээс зайлсхийж, хэрмийг үр дүнтэйгээр доошоо сунгадаг.
Теоретик хувьд хязгааргүй хэрэм үүсгэхэд ашиглаж болно, гэвч үүсгэсэн хэрэм үнэхээр шийдэгдэх боломжтой байхыг баталгаажуулахын тулд зарим нэг үед "сүүлийн тагт" логикийг шилжүүлэх шаардлагатай.
Алхам 1: Эхний Тагтыг Тохируул
- Тагт бүрийн эсэд онцгой багцын ID өгнө.
Алхам 2: Зарим Хойд Хавхлагуудыг Горизонталь Холбох
- Хэд хэдэн хойд хавхлагуудыг санамсаргүйгээр нэг багцын ID-тай болгож нэгтгэнэ. Энэ нь горизонталь гарцыг баталгаажуулна.
Алхам 3: Дараагийн Тагтад Босоо Холболт Үүсгэх
- Тагтад гарах бүрийн багцаас хамгийн багадаа нэг эс доошоо холбогдох ёстой (холболтыг баталгаажуулахын тулд).
- Багц бүрээс нэг буюу хэд хэдэн эсийг санамсаргүй сонгож, дараагийн тагт руу холбоно.
Алхам 4: Дараагийн Тагтад Шилжих
- Босоо холболтуудыг үргэлжлүүлэн хийж, доорхи холбогдох эсүүдэд ижил багцын ID өгнө.
- Хэрэглэгдээгүй эсүүдэд шинэ багцын ID өгнө.
Алхам 5: Алхам 2–4-ийг Сүүлийн Тагт Хүртэл Давт
- Тагтыг нэг бүрчлэн боловсруулсаар бай.
Алхам 6: Сүүлийн Тагтыг Боловсруулах
- Сүүлийн тагт дахь бүх эсүүд нэг багцад хамаарахыг баталгаажуулахын тулд үлдсэн тусдаа багцуудыг нэгтгэнэ.