Recursive Backtracker Maze գեներատոր

Ռեկուրսիվ backtracker ալգորիթմը իրականում ընդհանուր նպատակի խորության որոնում է: Երբ այն օգտագործվում է լաբիրինթոսային սերնդի համար, այն փոքր-ինչ ձեւափոխվում է պատահականորեն ընտրելու ուղին, մինչդեռ եթե օգտագործվում է իրական որոնման նպատակով, ապա մարդը սովորաբար պարզապես փնտրում է յուրաքանչյուր մակարդակը գծային կարգով։ Այն հակված է լաբիրինթոսներ արտադրելու, որոնք ունեն երկար, քամոտ միջանցքներ եւ շատ երկար, ոլորապտույտ լուծույթ։

Կատարյալ լաբիրինթոսն այն լաբիրինթոսն է, որտեղ լաբիրինթոսի ցանկացած կետից դեպի ցանկացած այլ կետ կա ուղիղ մեկ ճանապարհ: Դա նշանակում է, որ դուք չեք կարող ի վերջո շրջել շրջանակներով, բայց հաճախ կհանդիպեք փակուղիների՝ ստիպելով ձեզ շրջվել և հետ գնալ:

Այստեղ ստեղծված լաբիրինթոսային քարտեզները ներառում են լռելյայն տարբերակ՝ առանց որևէ մեկնարկի և ավարտի դիրքերի, այնպես որ դուք կարող եք որոշել դրանք ինքներդ. լուծում կլինի լաբիրինթոսի ցանկացած կետից մինչև ցանկացած այլ կետ: Եթե ​​ցանկանում եք ոգեշնչել, կարող եք միացնել առաջարկվող սկզբի և ավարտի դիրքը և նույնիսկ տեսնել լուծումը երկուսի միջև:

Ռեկուրսիվ backtracker ալգորիթմը կատարյալ լաբիրինթոսներ ստեղծելու խորացված առաջին որոնման մեթոդ է (լաբիրինթոսներ, որոնք չունեն պտույտներ եւ մեկ ճանապարհ ցանկացած երկու կետերի միջեւ)։ Այն պարզ է, արդյունավետ եւ առաջացնում է տեսողական գրավիչ լաբիրինթոսներ, որոնք ունեն երկար, քամոտ միջանցքներ։

Չնայած իր անվանմանը, պարտադիր չէ, որ այն կիրառվի կրկնության միջոցով: Այն հաճախ կիրառվում է իտերատիվ մոտեցմամբ՝ օգտագործելով LIFO հերթը (այսինքն՝ ստալակ): Շատ մեծ լաբիրինթոսների դեպքում կրկնվելու դեպքում ավելի հավանական է, որ զանգերի կուտակումը տեղի կունենա՝ կախված ծրագրավորման լեզվից եւ առկա հիշողությունից։ LIFO հերթը ավելի հեշտությամբ կարելի է հարմարեցնել մեծ քանակությամբ տվյալներ ձեռք բերելուն, նույնիսկ հերթը պահել սկավառակի կամ տվյալների բազայի վրա, եթե առկա հիշողությունը բավարար չէ:

Ինչպես է այն գործում

Ալգորիթմը գործում է ստակի վրա հիմնված խորության վրա հիմնված որոնման մոտեցման միջոցով: Ահա քայլ առ քայլ կոտրվածքը.

1. Ընտրեք սկսնակ բջիջը եւ նշեք այն որպես այցեքարտ:
2. Մինչ կան չզտված բջիջներ.
   • Նայեք հարեւան բջիջներին, որոնք դեռ չեն այցելել:
   • Եթե առնվազն մեկ չզվայել հարեւան գոյություն ունի.
     • Պատահականորեն ընտրեք չզվարված հարեւաններից մեկին:
     • Հեռացրեք պատը ներկա բջջի եւ ընտրված հարեւանի միջեւ:
     • Տեղափոխվեք ընտրված հարեւանի մոտ եւ նշեք այն որպես այցելություն:
     • Ներկա բջիջը հրեք կույտի վրա։
   • Եթե չկան չզգավորված հարեւաններ.
     • Backtrack- ը' վերջին բջիջը կճղակից դուրս գալով:
3. Շարունակեք այս գործընթացը, մինչեւ որ ստաքը դատարկվի:

Հետաքրքիր փաստ այս ալգորիթմի մասին այն է, որ այն աշխատում է ինչպես լաբիրինթոսային գեներատոր, այնպես էլ որպես լաբիրինթոս լուծող: Եթե այն աշխատեցնեք արդեն արտադրված լաբիրինթոսում եւ պարզապես կանգ առնեք, երբ հասնեք որոշված վերջնակետին, ապա կպարունակի լաբիրինթոսի լուծույթը։

Ես իրականում ունեմ այս ալգորիթմի երկու տարբերակները այս կայքում խաղալիս. LIFO հերթ, որը հիմնված է մեկը այս էջում լաբիրինթոսներ գեներացնելու համար, եւ մի կրկնություն, որը հիմնված է լաբիրինթոսների լուծման համար, նաեւ լաբիրինթոսներ, որոնք ստեղծվում են այլ ալգորիթմների կողմից (այդպես են ստեղծվում լուծումներով քարտեզները): Երկու տարբեր տարբերակներ ունենալը միայն սպորտի համար է, քանի որ ես մի nerd եմ, ով այն հետաքրքիր է համարում, երկուսն էլ կարող էին աշխատել երկուսի համար ;-)