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

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

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

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

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

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

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

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

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

Քայլ 1: Սկզբնայնացնել

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

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

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

Քայլ 3. Պատահական քայլք loop-Erasing-ով

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

Քայլ 4. Կրկնել մինչեւ բոլոր բջիջների այցելությունը.

• Շարունակեք ընտրել չզտված բջիջներ եւ կատարել պատահական քայլեր, մինչեւ որ յուրաքանչյուր բջիջ մաս կազմի լաբիրինթոսին: