Լաբիրինթոսի Գեներատոր Հորդարձ և Մահ

«Որսիր և սպանիր» ալգորիթմը իրականում Ռեկուրսիվ հետադարձման ալգորիթմի փոփոխված տարբերակն է։ Փոփոխությունը բաղկացած է նոր բջիջի համակարգված սկանավորումից (կամ «որսումից»)՝ այն պահից շարունակելու համար, երբ այն չի կարող առաջ գնալ, ի տարբերություն իրական ռեկուրսիվ որոնման, որը միշտ կվերադառնա կույտի նախորդ բջիջ։

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

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

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

«Որսիր և սպանիր» ալգորիթմի մասին

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

Ինչպես է «Որսիր և սպանիր» ալգորիթմը աշխատում լաբիրինթոսի ստեղծման համար

Քայլ 1։ Սկսեք պատահական բջիջից

• Գտեք ցանցում պատահական բջիջ և նշեք այն որպես այցելված։

Քայլ 2. Քայլելու փուլ (պատահական քայլք)

• Ընտրեք պատահական չայցելված հարևան։
• Տեղափոխվեք այդ հարևան բջջի մոտ, նշեք այն որպես այցելված և գծեք ուղի նախորդ և նոր բջջի միջև։
• Կրկնեք, մինչև չմնա ոչ մի չայցելված հարևան։

Քայլ 3. Որսորդության փուլ (հետընթաց սկանավորման միջոցով)

• Սկանավորեք ցանցը տող առ տող (կամ սյուն առ սյուն):
• Գտեք առաջին չայցելված բջիջը, որն ունի առնվազն մեկ այցելված հարևան։
• Միացրեք այդ բջիջը այցելած հարևանի հետ՝ քայլելու փուլը վերսկսելու համար։
• Կրկնել մինչև բոլոր բջիջները այցելվեն։

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

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

• Էլլերի ալգորիթմ Maze գեներատոր
• Կրուսկալի ալգորիթմի լաբիրինթոս գեներատոր
• Recursive Backtracker Maze գեներատոր