شکار و کشتن ژنراتور پیچ و خم

الگوریتم Hunt and Kill در واقع یک نسخه اصلاح شده از Recursive Backtracker است. این اصلاح شامل اسکن سیستماتیک (یا "شکار") برای یک سلول جدید است تا از زمانی که نمی تواند جلوتر برود ادامه یابد، برخلاف یک جستجوی بازگشتی واقعی، که همیشه به سلول قبلی در پشته باز می گردد.

به همین دلیل، این الگوریتم را می توان به راحتی برای تولید پیچ و خم هایی با ظاهر و احساس متفاوت تطبیق داد، فقط با انتخاب ورود به حالت "شکار" بیشتر یا طبق قوانین خاص. نسخه پیاده سازی شده در اینجا تنها زمانی وارد حالت "شکار" می شود که نتواند از سلول فعلی دورتر شود.

پیچ و خم کامل، پیچ و خم هایی است که در آن دقیقاً یک مسیر از هر نقطه در پیچ و خم به هر نقطه دیگر وجود دارد. این بدان معناست که شما نمی توانید در نهایت به دور زدن در دایره بپردازید، اما اغلب با بن بست هایی روبرو می شوید که شما را وادار می کند که بچرخید و به عقب برگردید.

نقشه های پیچ و خم تولید شده در اینجا شامل یک نسخه پیش فرض بدون هیچ موقعیت شروع و پایان است، بنابراین شما می توانید آن ها را برای خود تصمیم بگیرید: از هر نقطه در پیچ و خم تا هر نقطه دیگر راه حلی وجود خواهد داشت. اگر می خواهید الهام بگیرید، می توانید یک موقعیت پیشنهادی شروع و پایان را فعال کنید - و حتی راه حل بین این دو را ببینید.

درباره الگوریتم شکار و کشتن

الگوریتم Hunt and Kill یک روش ساده و در عین حال موثر برای تولید پیچ و خم است. این تا حدودی شبیه به جستجوی عمق اول (یعنی الگوریتم Recursive Backtracker) است، به جز زمانی که نمی تواند از موقعیت فعلی دورتر شود، به طور سیستماتیک روی پیچ و خم اسکن می کند (یا "شکار") می کند تا سلول جدیدی برای ادامه کار پیدا کند. این الگوریتم از دو مرحله اصلی تشکیل شده است: پیاده روی و شکار.

الگوریتم شکار و کشتن برای تولید پیچ و خم چگونه کار می کند؟

مرحله 1: از یک سلول تصادفی شروع کنید

• یک سلول تصادفی را در شبکه پیدا کنید و آن را به عنوان بازدید شده علامت گذاری کنید.

مرحله 2: مرحله راه رفتن (پیاده روی تصادفی)

• یک همسایه تصادفی بازدید نشده را انتخاب کنید.
• به آن همسایه بروید، آن را به عنوان بازدید شده علامت گذاری کنید و مسیری بین سلول قبلی و جدید ایجاد کنید.
• این کار را تکرار کنید تا هیچ همسایه ای ملاقات نشده باقی نماند.

مرحله 3: مرحله شکار (عقب نشینی از طریق اسکن)

• شبکه را ردیف به ردیف (یا ستون به ستون) اسکن کنید.
• اولین سلول بازدید نشده را پیدا کنید که حداقل یک همسایه بازدید شده داشته باشد.
• آن سلول را به همسایه بازدید شده متصل کنید تا مرحله پیاده روی را از سر بگیرید.
• این کار را تا زمانی که همه سلول ها ویزیت شوند، تکرار کنید.