Լաբիրինթոսի Գեներատոր Հորդարձ և Մահ

Hunt and Kill ալգորիթմը իրականում Recursive Backtracker-ի փոփոխված տարբերակն է: Մոդիֆիկացիան իրենից ներկայացնում է համակարգված սկանավորում (կամ «որսորդություն»), որպեսզի նոր բջիջը շարունակի այն պահից, երբ այն չի կարող ավելի հեռու գնալ, ի տարբերություն իրական կրկնվող որոնման, որը միշտ կվերադառնա նախորդ բջիջը կցվածքի վրա:

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

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

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

Հանտի եւ սպանության ալգորիթմի մասին

Հանթ եւ սպանել ալգորիթմը լաբիրինթոսների գեներացման պարզ, բայց արդյունավետ մեթոդ է: Այն ինչ-որ չափով նման է խորությամբ առաջին որոնումներին (այսինքն՝ Recursive Backtracker ալգորիթմին), բացառությամբ այն դեպքերի, երբ այն չի կարող ավելի հեռու գնալ ներկայիս դիրքից, այն կանոնավորաբար սկանավորում է (կամ «որս») լաբիրինթոսի վրայով, որպեսզի գտնի նոր բջիջ, որից պետք է առաջ ընթանա: Ալգորիթմը բաղկացած է երկու հիմնական փուլերից՝ քայլք եւ որս:

Ինչպես է աշխատում «Որսորդություն եւ սպանություն» ալգորիթմը Maze generation-ի համար

Քայլ 1. Սկսեք պատահական բջջից

• Գտիր ցանցում գտնվող պատահական բջիջը եւ նշիր այն որպես այցելություն։

Քայլ 2: Քայլք փուլ (պատահական քայլք)

• Ընտրեք պատահական չզտված հարեւանին:
• Տեղափոխվեք այդ հարեւանի մոտ, նշեք այն որպես այցեքարտ եւ արահետ փորեք նախորդ եւ նոր բջիջների միջեւ:
• Կրկնեք, մինչեւ չհայտարարված հարեւաններ չմնան:

Քայլ 3. Որսորդության փուլ (backtracking միջոցով scanning)

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