Աճող ծառի ալգորիթմ Maze գեներատոր

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

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

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

Աճող ծառի ալգորիթմի մասին

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

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

Քայլ 1. Սկզբնավորումը

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

Քայլ 2. Maze Generation Loop

• Մինչ բջիջների ցանկը դատարկ չէ.
  • Ցանկից ընտրեք բջիջ՝ հիմնված կոնկրետ ռազմավարության վրա (բացատրվում է ստորեւ):
  • Ընտրած խցիկից մի հատված փորագրեք դեպի նրա չզտված հարեւաններից մեկը (ընտրված պատահականորեն):
  • Ցուցակին ավելացրեք հարեւանին, քանի որ այն այժմ լաբիրինթոսի մի մասն է:
  • Եթե ընտրված բջիջը չունի չզտված հարեւաններ, հեռացրեք այն ցուցակից:

Քայլ 3: Տերմինատոր

• Ալգորիթմն ավարտվում է, երբ ցուցակում այլեւս բջիջներ չկան, այսինքն՝ ամբողջ լաբիրինթոսը քանդակվել է։

Բջջի ընտրության ստրատեգիաներ (ալգորիթմի ճկունություն)

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

Նորագույն խցիկ (Stack-like Behavior) – Recursive Backtracker.

• Միշտ ընտրեք վերջերս ավելացված բջիջը:
• Առաջացնում է երկար, ոլորապտույտ միջանցքներ, որտեղ կան բազմաթիվ մեռյալ ծայրեր (ինչպես խորությամբ որոնման լաբիրինթոսը)։
• Mazes հակված է երկար անցումներ եւ հեշտ է լուծել.

Պատահական բջջային (Randomized Prim's Algorithm).

• Ամեն անգամ ցուցակից ընտրիր պատահական բջիջ։
• Ստեղծում է ավելի հավասարաչափ բաշխված լաբիրինթոս' բարդ, խճճված արահետներով:
• Ավելի քիչ երկար միջանցքներ եւ ավելի ճյուղավորումներ։

Ամենահին բջիջը (Queue-like Behavior).

• Միշտ ընտրեք ցուցակի ամենահին բջիջը:
• Գեներացնում է լաբիրինթոսներ ավելի միանման տարածմամբ, ինչպես լայնության առաջին որոնման կաղապարը:
• Կարճ, թփուտային անցուղիներ՝ խիտ միացումներով:
• (Սա այն տարբերակն է, որն իրականացվում է այստեղ)

Հիբրիդային մոտեցումներ.

Համակցեք տարբեր լաբիրինթոսային բնութագրերի ռազմավարությունները: Օրինակ:

• 90% նորագույն, 10% պատահական. Հիմնականում նման է կրկնվող հետնամասի լաբիրինթոսին, բայց ժամանակ առ ժամանակ ճյուղերով, որոնք ճեղքում են երկար միջանցքները։
• 50% նորագույն, 50% ամենահին. Հավասարակշռում է երկար միջանցքները թփուտային աճով: