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

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

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

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

Ծառի աճեցման ալգորիթմի մասին

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

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

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

• Սկսեք չայցելված բջիջների ցանցից։
• Ընտրեք պատահական սկզբնական բջիջ և ավելացրեք այն ցանկին։

Քայլ 2. Լաբիրինթոսի գեներացիայի ցիկլ

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

Քայլ 3. Դադարեցում

• Ալգորիթմն ավարտվում է, երբ ցանկում այլևս բջիջներ չկան, ինչը նշանակում է, որ ամբողջ լաբիրինթոսը փորագրված է։

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

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

Ամենանոր բջիջը (ստեկի նման վարքագիծ) – Ռեկուրսիվ հետադարձ հետևորդ։

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

Պատահական բջիջ (Պրիմի պատահականացված ալգորիթմ):

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

Ամենահին բջիջը (հերթի նման վարքագիծ):

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

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

Միավորել ռազմավարությունները լաբիրինթոսի տարբեր բնութագրերի համար։ Օրինակ՝

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

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

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

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