Վիլսոնի ալգորիթմի լաբիրինթոս գեներատոր

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

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

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

Վիլսոնի ալգորիթմի մասին

Վիլսոնի ալգորիթմը՝ ցիկլով ջնջված պատահական պատի միջոցով միատարր տարածվող ծառեր ստեղծելու համար, ստեղծվել է Դեյվիդ Բրյուս Վիլսոնի կողմից։

Վիլսոնն այս ալգորիթմը սկզբնապես ներկայացրել է 1996 թվականին՝ հավանականության տեսության մեջ պատահականորեն տարածված ծառերի և Մարկովի շղթաների ուսումնասիրության ժամանակ։ Չնայած նրա աշխատանքը հիմնականում վերաբերում էր մաթեմատիկային և վիճակագրական ֆիզիկային, այդ ժամանակվանից ի վեր ալգորիթմը լայնորեն կիրառվել է լաբիրինթոսներ ստեղծելու համար՝ կատարյալ միատարր լաբիրինթոսներ ստեղծելու իր ունակության շնորհիվ։

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

Վիլսոնի ալգորիթմը ապահովում է, որ վերջնական լաբիրինթոսը լիովին միացված լինի առանց որևէ օղակի՝ չայցելված բջիջներից պատահական քայլքների միջոցով իտերատիվ կերպով ուղիներ փորագրելով։

Քայլ 1. Նախաձեռնել

• Սկսեք պատերով լցված ցանցից։
• Սահմանեք բոլոր հնարավոր անցուղի բջիջների ցանկը։

Քայլ 2. Ընտրեք պատահական սկզբնական բջիջ

• Ընտրեք ցանկացած պատահական բջիջ և նշեք այն որպես այցելված։ Սա ծառայում է որպես լաբիրինթոսի մեկնարկային կետ ստեղծման ընթացքում։

Քայլ 3. Պատահական քայլք՝ ցիկլի ջնջմամբ

• Ընտրեք չայցելված բջիջ և սկսեք պատահական քայլք (շարժվելով պատահական ուղղություններով):
• Եթե քայլարշավը հասնում է արդեն այցելված բջիջի, ջնջեք ուղու վրա եղած բոլոր օղակները։
• Երբ զբոսանքը միանա այցելված տարածաշրջանին, նշեք արահետի բոլոր բջիջները որպես այցելված։

Քայլ 4. Կրկնել մինչև բոլոր բջիջները այցելվեն։

• Շարունակեք ընտրել չայցելված բջիջները և կատարել պատահական քայլարշավներ, մինչև յուրաքանչյուր բջիջ դառնա լաբիրինթոսի մաս։

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

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

• Էլլերի ալգորիթմ Maze գեներատոր
• Recursive Backtracker Maze գեներատոր
• Լաբիրինթոսի Գեներատոր Հորդարձ և Մահ