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

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

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

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

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

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

Ինչպես է այն աշխատում

Ալգորիթմը գործում է խորության վրա հիմնված որոնման մոտեցմամբ։ Ահա քայլ առ քայլ վերլուծությունը՝

1. Ընտրեք մեկնարկային բջիջ և նշեք այն որպես այցելված։
2. Քանի դեռ կան չայցելված բջիջներ՝ նայեք հարևան բջիջներին, որոնք դեռևս չեն այցելել։ Եթե գոյություն ունի առնվազն մեկ չայցելված հարևան՝ պատահականորեն ընտրեք չայցելված հարևաններից մեկը։ Հեռացրեք ներկայիս և ընտրված հարևանի միջև եղած պատը։ Տեղափոխվեք ընտրված հարևանի մոտ և նշեք այն որպես այցելված։ Տեղափոխեք ներկայիս բջիջը կույտի մեջ։ Եթե չայցելված հարևաններ չկան՝ վերադարձեք հետ՝ կույտից հանելով վերջին բջիջը։
3. Շարունակեք այս գործընթացը, մինչև կույտը դատարկվի։

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

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

Լրացուցիչ ընթերցանություն

Եթե ​​ձեզ դուր եկավ այս գրառումը, ձեզ կարող են նաև դուր գալ այս առաջարկները.

• Էլլերի ալգորիթմ Maze գեներատոր
• Վիլսոնի ալգորիթմի լաբիրինթոս գեներատոր
• Աճող ծառի ալգորիթմ Maze գեներատոր