ဟန်တ် နှင့် ကွယ်လွန် သွားမယ် မြေဇ် ထုတ်လုပ်သူ

Hunt and Kill algorithm သည် Recursive Backtracker ၏ ပြုပြင်မွမ်းမံထားသော ဗားရှင်းတစ်ခုဖြစ်သည်။ ပြုပြင်မွမ်းမံမှုတွင် stack ရှိ ယခင် cell သို့ အမြဲတမ်းပြန်သွားမည့် စစ်မှန်သော recursive search နှင့် ဆန့်ကျင်ဘက်အနေဖြင့် cell အသစ်တစ်ခု ဆက်လက်လုပ်ဆောင်ရန် စနစ်တကျ scan ဖတ်ခြင်း (သို့မဟုတ် "အမဲလိုက်ခြင်း") ပါဝင်သည်။

ထို့ကြောင့် ဤအယ်လဂိုရီသမ်ကို "အမဲလိုက်ခြင်း" မုဒ်ကို မကြာခဏ သို့မဟုတ် သတ်မှတ်ထားသော စည်းမျဉ်းများအရ ဝင်ရောက်ခြင်းဖြင့် မတူညီသော အသွင်အပြင်နှင့် ခံစားချက်ရှိသော ပဟေဠိများကို ဖန်တီးရန် အလွယ်တကူ လိုက်လျောညီထွေဖြစ်အောင် ပြုလုပ်နိုင်ပါသည်။ ဤနေရာတွင် အကောင်အထည်ဖော်ထားသော ဗားရှင်းသည် လက်ရှိဆဲလ်မှ ပိုမိုဝေးဝေးသို့ မသွားနိုင်သည့်အခါတွင်သာ "အမဲလိုက်ခြင်း" မုဒ်သို့ ဝင်ရောက်ပါသည်။

ပြီးပြည့်စုံသော ဝင်္ကပါသည် ဝင်္ကပါရှိ မည်သည့်မှတ်တိုင်မှ အခြားနေရာသို့ လမ်းကြောင်းတစ်ခု အတိအကျ ရှိသည့် ဝင်္ကပါတစ်ခုဖြစ်သည်။ ဆိုလိုတာက သင် လှည့်ပတ်ပြီး နောက်ကြောင်းပြန်ဖို့ တွန်းအားပေးတဲ့ အသေအဆုံးတွေကို မကြာခဏ ကြုံတွေ့ရပါလိမ့်မယ်။

ဤနေရာတွင် ထုတ်လုပ်လိုက်သော ဝင်္ကပါမြေပုံများတွင် မည်သည့်အစမှအဆုံး အနေအထားများ မပါရှိဘဲ မူရင်းဗားရှင်းပါ၀င်သည်၊ ထို့ကြောင့် ၎င်းတို့ကို သင်ကိုယ်တိုင် ဆုံးဖြတ်နိုင်သည်- ဝင်္ကပါရှိ မည်သည့်အမှတ်မှ အခြားအမှတ်အထိ အဖြေတစ်ခု ရှိလိမ့်မည်။ သင်သည် လှုံ့ဆော်မှုကို လိုချင်ပါက၊ အကြံပြုထားသော အစနှင့် အပြီးသတ် အနေအထားကို ဖွင့်နိုင်သည် - နှစ်ခုကြားမှ ဖြေရှင်းချက်ကိုပင် ကြည့်နိုင်သည်။

Hunt and Kill Algorithm အကြောင်း

Hunt and Kill အယ်လဂိုရီသမ်သည် လမ်းကြောင်းများဖန်တီးရန်အတွက် ရိုးရှင်းသော်လည်း ထိရောက်သောနည်းလမ်းတစ်ခုဖြစ်သည်။ ၎င်းသည် အနက်ကိုဦးစွာရှာဖွေခြင်း (ဆိုလိုသည်မှာ Recursive Backtracker အယ်လဂိုရီသမ်) နှင့် အနည်းငယ်ဆင်တူသော်လည်း လက်ရှိနေရာမှ ပိုမိုဝေးဝေးသွား၍မရသည့်အခါတွင် ဆက်လက်လုပ်ဆောင်ရန် လမ်းကြောင်းပေါ်တွင် စနစ်တကျစကင်ဖတ်ခြင်း (သို့မဟုတ် "အမဲလိုက်ခြင်း") ပြုလုပ်သည်။ အယ်လဂိုရီသမ်တွင် အဓိကအဆင့်နှစ်ဆင့်ပါဝင်သည်- လမ်းလျှောက်ခြင်းနှင့် အမဲလိုက်ခြင်း။

Maze Generation အတွက် Hunt and Kill Algorithm ဘယ်လိုအလုပ်လုပ်လဲ

အဆင့် ၁: ကျပန်းဆဲလ်တစ်ခုမှ စတင်ပါ

• grid ထဲက ကျပန်း cell တစ်ခုကို ရှာပြီး visited အဖြစ် mark လုပ်ပါ။

အဆင့် ၂: လမ်းလျှောက်ခြင်းအဆင့် (ကျပန်းလမ်းလျှောက်ခြင်း)

• မရောက်ဖူးသော အိမ်နီးချင်းတစ်ဦးကို ရွေးချယ်ပါ။
• ထိုအိမ်နီးချင်းသို့ ရွှေ့ပါ၊ ၎င်းကို သွားရောက်လည်ပတ်ပြီးဟု မှတ်သားပြီး ယခင်ဆဲလ်နှင့် အသစ်ဆဲလ်ကြားတွင် လမ်းကြောင်းတစ်ခု ထွင်းပါ။
• မလာရောက်သော အိမ်နီးချင်းများ မကျန်တော့သည်အထိ ထပ်ခါတလဲလဲ လုပ်ဆောင်ပါ။

အဆင့် ၃: အမဲလိုက်ခြင်းအဆင့် (စကင်ဖတ်ခြင်းဖြင့် နောက်ပြန်ခြေရာခံခြင်း)

• ဇယားကွက်ကို တစ်တန်းချင်းစီ (သို့မဟုတ် ကော်လံအလိုက်) စကင်ဖတ်ပါ။
• အိမ်နီးချင်းတစ်ဦး အနည်းဆုံး လာရောက်လည်ပတ်သည့် ပထမဆုံး လာရောက်လည်ပတ်ခြင်းမရှိသည့် ဆဲလ်ကို ရှာပါ။
• လမ်းလျှောက်သည့်အဆင့်ကို ပြန်လည်စတင်ရန် ထိုဆဲလ်ကို လာရောက်လည်ပတ်သော အိမ်နီးချင်းနှင့် ချိတ်ဆက်ပါ။
• ဆဲလ်အားလုံးသို့ သွားရောက်ကြည့်ရှုပြီးသည်အထိ ထပ်ခါတလဲလဲ လုပ်ဆောင်ပါ။

နောက်ထပ်စာဖတ်ခြင်း။

ဤပို့စ်ကို သင်နှစ်သက်ပါက၊ ဤအကြံပြုချက်များကို သင်လည်း နှစ်သက်နိုင်ပါသည်-

• Kruskal ၏ Algorithm Maze မီးစက်
• Recursive Backtracker Maze မီးစက်
• အဲလ်လား၏ အယ်လ်ဂိုရီသံ မြေဇ် ထုတ်လုပ်သူ