ကြီးထွားနေသော သစ်ပင် မြေဇ် ထုတ်လုပ်သူ

Growing Tree အယ်လဂိုရီသမ်သည် စိတ်ဝင်စားစရာကောင်းသည်၊ အဘယ်ကြောင့်ဆိုသော် ၎င်းသည် မျိုးဆက်တစ်ခုအတွင်း နောက်ဆဲလ်ကို မည်သို့ရွေးချယ်သည်ပေါ် မူတည်၍ အခြားအယ်လဂိုရီသမ်များစွာ၏ အပြုအမူကို တုပနိုင်သောကြောင့်ဖြစ်သည်။ ဤစာမျက်နှာရှိ အကောင်အထည်ဖော်မှုသည် breadth-first၊ queue-like ချဉ်းကပ်မှုကို အသုံးပြုသည်။

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

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

ကြီးထွားလာသော သစ်ပင် အယ်လဂိုရီသမ်အကြောင်း

Growing Tree algorithm သည် ပြီးပြည့်စုံသော maze များဖန်တီးရန်အတွက် ပြောင်းလွယ်ပြင်လွယ်ရှိပြီး အစွမ်းထက်သောနည်းလမ်းတစ်ခုဖြစ်သည်။ ဤ algorithm သည် စိတ်ဝင်စားဖွယ်ကောင်းသည်၊ အဘယ်ကြောင့်ဆိုသော် ၎င်းသည် နောက် cell ကို မည်သို့လုပ်ဆောင်ရမည်ကို ရွေးချယ်ပုံပေါ် မူတည်၍ Prim's algorithm၊ recursive backtracking နှင့် recursive division ကဲ့သို့သော အခြား maze generation algorithms အများအပြား၏ အပြုအမူကို တုပနိုင်သောကြောင့်ဖြစ်သည်။

ကြီးထွားလာသော သစ်ပင် အယ်လဂိုရီသမ် မည်သို့အလုပ်လုပ်သည်

အဆင့် ၁: စတင်ခြင်း

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

အဆင့် ၂: Maze Generation Loop

• ဆဲလ်စာရင်းသည် ဗလာမဟုတ်သည့်အခါ- သတ်မှတ်ထားသော ဗျူဟာတစ်ခုအပေါ် အခြေခံ၍ စာရင်းမှ ဆဲလ်တစ်ခုကို ရွေးချယ်ပါ (အောက်တွင် ရှင်းပြထားသည်)။ ရွေးချယ်ထားသော ဆဲလ်မှ ၎င်း၏ မလာရောက်ရသေးသော အိမ်နီးချင်းများထဲမှ တစ်ခုသို့ စာပိုဒ်တစ်ပိုဒ် ထွင်းပါ (ကျပန်းရွေးချယ်ထားသည်)။ အိမ်နီးချင်းသည် ယခုအခါ ပဟေဠိ၏ အစိတ်အပိုင်းတစ်ခုဖြစ်သောကြောင့် စာရင်းထဲသို့ ထည့်ပါ။ ရွေးချယ်ထားသော ဆဲလ်တွင် မလာရောက်ရသေးသော အိမ်နီးချင်းများ မရှိပါက စာရင်းမှ ဖယ်ရှားပါ။

အဆင့် ၃: ရပ်စဲခြင်း

• စာရင်းထဲမှာ ဆဲလ်တွေ မရှိတော့တဲ့အခါ အယ်လဂိုရီသမ် ပြီးဆုံးသွားပြီး ပဟေဠိတစ်ခုလုံးကို ထွင်းထုပြီးပြီလို့ ဆိုလိုပါတယ်။

ဆဲလ်ရွေးချယ်မှုဗျူဟာများ (အယ်လဂိုရီသမ်၏ ပြောင်းလွယ်ပြင်လွယ်ရှိမှု)

Growing Tree အယ်လဂိုရီသမ်ရဲ့ အဓိကအချက်ကတော့ ဘယ်ဆဲလ်ကို နောက်တစ်ဆင့် လုပ်ဆောင်မလဲဆိုတာ ရွေးချယ်ပုံပါပဲ။ ဒီရွေးချယ်မှုက ပဟေဠိရဲ့ အသွင်အပြင်ကို သိသိသာသာ သက်ရောက်မှုရှိပါတယ်။

အသစ်ဆုံးဆဲလ် (Stack ကဲ့သို့ အပြုအမူ) – Recursive Backtracker:

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

ကျပန်းဆဲလ် (ကျပန်းပြုလုပ်ထားသော Prim ၏ အယ်လဂိုရီသမ်):

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

အเก่าแก่ဆုံးဆဲလ် (တန်းစီခြင်းကဲ့သို့ အပြုအမူ):

• စာရင်းထဲက အเก่าဆုံးဆဲလ်ကို အမြဲရွေးချယ်ပါ။
• breadth-first search pattern ကဲ့သို့ ပိုမိုတပြေးညီ ပျံ့နှံ့မှုရှိသော mazes များကို ဖန်တီးပေးသည်။
• ချိတ်ဆက်မှုထူထပ်သော တိုတောင်းပြီး ချုံပုတ်များပါသည့် လမ်းများ။
• (ဒါက ဒီမှာ အကောင်အထည်ဖော်ထားတဲ့ ဗားရှင်းပါ)

ရောနှောချဉ်းကပ်မှုများ:

မတူညီသော ပဟေဠိဝိသေသလက္ခဏာများအတွက် ဗျူဟာများကို ပေါင်းစပ်ပါ။ ဥပမာ-

• ၉၀% အသစ်ဆုံး၊ ၁၀% ကျပန်း- အများအားဖြင့် နောက်ပြန်လှည့်လမ်းကြောင်းပဟေဠိနှင့်တူသော်လည်း ရံဖန်ရံခါ အကိုင်းအခက်များပါရှိသော ရှည်လျားသောစင်္ကြံများကို ပိုင်းခြားထားသည်။
• ၅၀% အသစ်ဆုံး၊ ၅၀% အဟောင်းဆုံး- ရှည်လျားသော စင်္ကြံများနှင့် ချုံပုတ်များကြီးထွားမှုကို ဟန်ချက်ညီစေသည်။

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

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

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