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

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

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

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

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

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

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

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

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

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

Քայլ 1. Առաջին տողի նախնականացում

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

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

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

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

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

Քայլ 4. Անցում հաջորդ շարքին

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

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

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

Քայլ 6. Վերջնական շարքի մշակում

• Համոզվեք, որ վերջին տողի բոլոր բջիջները պատկանում են նույն հավաքածուին՝ միավորելով մնացած առանձին հավաքածուները։

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

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

• Կրուսկալի ալգորիթմի լաբիրինթոս գեներատոր
• Recursive Backtracker Maze գեներատոր
• Աճող ծառի ալգորիթմ Maze գեներատոր