Էլլերի ալգորիթմ Maze գեներատոր

Էլլերի ալգորիթմը լաբիրինթոս առաջացման ալգորիթմ է, որն արդյունավետորեն արտադրում է կատարյալ լաբիրինթոսներ (առանց օղակների և մեկ ուղի ցանկացած երկու կետերի միջև)՝ օգտագործելով տող առ տող մոտեցումը: Այն արտադրում է Կրուսկալի ալգորիթմի նման լաբիրինթոսներ, բայց դա անում է միանգամից մեկ տող ստեղծելով, առանց ամբողջ լաբիրինթոսը հիշողության մեջ պահելու անհրաժեշտության: Դա օգտակար է դարձնում շատ սահմանափակ համակարգերում շատ մեծ լաբիրինթոսներ ստեղծելու և ընթացակարգային բովանդակության ստեղծման համար:

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

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

Էլլերի ալգորիթմի մասին

Էլլերի ալգորիթմը ներկայացվել է Դեյվիդ Էլլերի կողմից։

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

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

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

Այն տեսականորեն կարող է օգտագործվել անսահման լաբիրինթոսներ ստեղծելու համար, սակայն, որպեսզի համոզվենք, որ ստեղծված լաբիրինթոսն իրականում լուծելի է, անհրաժեշտ է ինչ-որ պահի անցնել «վերջնական շարքի» տրամաբանությանը, որպեսզի ավարտվի լաբիրինթոսը:

Քայլ 1. Նախնականացրեք առաջին շարքը

• Տողի յուրաքանչյուր բջիջ նշանակեք եզակի հավաքածուի ID:

Քայլ 2. Հորիզոնական կերպով միացրեք որոշ հարակից բջիջներ

• Պատահականորեն միաձուլեք հարակից բջիջները՝ դրանք դնելով նույն հավաքածուի ID-ի վրա: Սա ապահովում է հորիզոնական անցումների առկայությունը:

Քայլ 3. Ստեղծեք ուղղահայաց կապեր հաջորդ շարքին

• Յուրաքանչյուր շարքի համար, որը հայտնվում է տողում, առնվազն մեկ բջիջ պետք է միանա դեպի ներքև (միացումն ապահովելու համար):
• Յուրաքանչյուր հավաքածուից պատահականորեն ընտրեք մեկ կամ մի քանի բջիջ՝ հաջորդ շարքին միանալու համար:

Քայլ 4. Անցեք հաջորդ տող

• Փոխանցեք ուղղահայաց կապերը՝ վերագրելով նույն հավաքածուի ID-ն ստորև ներկայացված համապատասխան բջիջներին:
• Նշանակեք նոր հավաքածուի ID-ներ ցանկացած չնշանակված բջիջներին:

Քայլ 5. Կրկնել 2–4 քայլերը, մինչև հասնենք վերջին շարքին

• Շարունակեք մշակել տող առ տող:

Քայլ 6. Մշակել վերջնական շարքը

• Համոզվեք, որ վերջին տողում գտնվող բոլոր բջիջները պատկանում են միևնույն բազմությանը` միացնելով մնացած առանձին խմբերը: