Өсөн нэмэгдэж буй модны алгоритмын Maze генератор

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

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

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

Тархий модны алгоритмын тухай

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

Тархий модны алгоритм хэрхэн ажилладаг вэ

Алхам 1: Эхлүүлэлт

• Хэрэв зочилогдоогүй эсүүдтэй тороос эхлэнэ.
• Төрөл бүрийн эхлэх эсийг санамсаргүй сонгоно уу, дараа нь үүнийг жагсаалтад нэмнэ үү.

Алхам 2: Лабиринт үүсгэх давталт

• Жагсаалт хоосон биш бол:
• Жагсаалтаас эсийг тодорхой стратегийн дагуу сонгоно уу (доорх тайлбар).
• Сонгосон эсээс зочилогдоогүй хөрш рүү зам гаргана (санамсаргүйгээр сонгогдсон).
• Хөршийг жагсаалтад нэмнэ, учир нь энэ нь одоо лабиринт хэсэг боллоо.
• Сонгосон эсэд зочилогдоогүй хөрш байхгүй бол жагсаалтаас үүнийг хасна.

Алхам 3: Төгсгөл

• Алгоритм жагсаалтанд эсүүд үлдсэнгүй бол дуусна, энэ нь бүхэл лабиринт огтлогдсон гэсэн үг юм.

Эс сонгох стратегиуд (Алгоритмын уян хатан байдал)

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

Шинээр нэмэгдсэн эс (Остгоны төрлийн зан төлөв) – Эргүүлэн хуудаслах:

• Хамгийн сүүлд нэмэгдсэн эсийг үргэлж сонгоно.
• Урт, мушгирсан коридоруудыг олон хаагдсан төгсгөлийг үүсгэдэг (гүнзгий хайлтын лабиринт шиг).
• Лабиринт нь урт коридоруудаар дүүрэн бөгөөд амархан шийдэгдэнэ.

Санамсаргүй эс (Санамсаргүй Примийн алгоритм):

• Жагсаалтаас санамсаргүй эсийг сонгоно.
• Илүү тэгш тархсан лабиринтыг үүсгэдэг, нарийн, хялбар замуудтай.
• Урт коридорууд багасаж, илүү их салаа замууд бий болно.

Хамгийн эртний эс (Чиг үүргийн төрлийн зан төлөв):

• Хамгийн эртний эсийг үргэлж сонгоно.
• Ийм лабиринт нь илүү тэгш тархалттай бөгөөд өргөтгөсөн хамгийн түрүүнд хүрэхээс илүү нягт холбоосоор бүтээгдэнэ.
• Богино, өтгөн тунгалаг туннель, нягт холбоосуудтай.
• (Энэ бол энд хэрэгжүүлсэн хувилбар)

Хосолмол хандлагууд:

Олон төрлийн лабиринт шинж чанарыг хувиргахын тулд стратегиудыг хослуулан ашиглана. Жишээлбэл:

• 90% хамгийн шинэ, 10% санамсаргүй: Ихэнхдээ эргүүлэн хуудаслах лабиринт шиг харагддаг, гэхдээ урт коридоруудыг таслах үе үе салаануудтай.
• 50% хамгийн шинэ, 50% хамгийн эртний: Урт коридоруудаа салан хуваагдсан ургамалтай хослуулсан.